source: src/Graph/DepthFirstSearchAnalysis.hpp@ 938e62

/*
 * DepthFirstSearchAnalysis.hpp
 *
 *  Created on: Feb 16, 2011
 *      Author: heber
 */

#ifndef DEPTHFIRSTSEARCHANALYSIS_HPP_
#define DEPTHFIRSTSEARCHANALYSIS_HPP_

// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <deque>

#include "Bond/bond.hpp"
#include "ConnectedSubgraph.hpp"

class atom;
class ListOfLocalAtoms_t;
class MoleculeLeafClass;
class molecule;

class DepthFirstSearchAnalysis
{
public:
  /** Constructor of DepthFirstSearchAnalysis.
   */
  DepthFirstSearchAnalysis();

  /** Destructor of DepthFirstSearchAnalysis.
   */
  ~DepthFirstSearchAnalysis();

  /** Performs a Depth-First search on all atoms.
   * Marks bonds in molecule as cyclic, bridge, ... and atoms as
   * articulations points, ...
   * We use the algorithm from [Even, Graph Algorithms, p.62].
   * \param *&BackEdgeStack NULL pointer to std::deque<bond::ptr > with all the found back edges, allocated and filled on return
   * \return list of each disconnected subgraph as an individual molecule class structure
   */
  void operator()();

  /** Scans through all bonds and set bond::Cyclic to true where atom::LowpointNr of both ends is equal: LP criterion.
   * \note Hydrogen bonds can never by cyclic, thus no check for that
   * \return number of cyclic bonds
   */
  unsigned int CyclicBondAnalysis() const;

  /** Removes all molecules and assign anew with known ListOfConnectedSubgraphs.
   *
   */
  void UpdateMoleculeStructure() const;

  /** Creates a chained list of all present molecules.
   *
   * \warning returns allocated chained list as reference, has to be free'd item by item through the list
   *
   * @return start node of chained molecules list
   */
  MoleculeLeafClass *getMoleculeStructure() const;

  /** Picks from a global stack with all back edges the ones in the fragment.
   *
   * Reference is the internal BackEdgeStack.
   *
   * \param ListOfLocalAtoms array of father atom::nr to local atom::nr (reverse of atom::father)
   * \param *LocalStack stack to be filled
   * \return true - everything ok, false - ReferenceStack was empty
   */
  bool PickLocalBackEdges(const ListOfLocalAtoms_t &ListOfLocalAtoms, std::deque<bond::ptr > *&LocalStack) const;

  /** Getter for BackEdgeStack.
   *
   * @return const reference to BackEdgeStack
   */
  const std::deque<bond::ptr >& getBackEdgeStack() const;

private:
  /** Resets GraphNodeInfo::ComponentNr and GraphNodeInfo::GraphrNr.
   *
   */
  void Init();

  /** Returns next unused bond for this atom \a *vertex or NULL of none exists.
   * \param *vertex atom to regard
   * \return bond class or NULL
   */
  bond::ptr FindNextUnused(atom *vertex) const;

  /** Resets bond::Used flag of all bonds in this molecule.
   * \return true - success, false - -failure
   */
  void ResetAllBondsToUnused() const;

  /** Sets the next component number.
   * This is O(N) as the number of bonds per atom is bound.
   * \param *vertex atom whose next atom::*ComponentNr is to be set
   * \param nr number to use
   */
  void SetNextComponentNumber(atom *vertex, int nr) const;

  /** Sets atom::GraphNr and atom::LowpointNr to CurrentGraphNr.
   * \param *Walker current node
   */
  void SetWalkersGraphNr(atom *&Walker);

  /** During DFS goes along unvisited bond and touches other atom.
   * Sets bond::type, if
   *  -# BackEdge: set atom::LowpointNr and push on \a BackEdgeStack
   *  -# TreeEgde: set atom::Ancestor and continue with Walker along this edge
   * Continue until molecule::FindNextUnused() finds no more unused bonds.
   * \param *&Walker current node
   * \param *&Binder current edge
   */
  void ProbeAlongUnusedBond(atom *&Walker, bond::ptr &Binder);

  /** Checks whether we have a new component.
   * if atom::LowpointNr of \a *&Walker is greater than atom::GraphNr of its atom::Ancestor, we have a new component.
   * Meaning that if we touch upon a node who suddenly has a smaller atom::LowpointNr than its ancestor, then we
   * have a found a new branch in the graph tree.
   * \param *&Walker current node
   * \param &LeafWalker contains reference to destination subgraph
   */
  void CheckForaNewComponent(atom *&Walker, ConnectedSubgraph &LeafWalker);

  /** Cleans the root stack when we have found a component.
   * If we are not BackStepping, then we clear the root stack by putting everything into a
   * component down till we meet Root.
   * \param *&Walker current node
   * \param *&Binder current edge
   * \param &LeafWalker contains reference to destination subgraph
   */
  void CleanRootStackDownTillWalker(atom *&Walker, bond::ptr &Binder, ConnectedSubgraph &LeafWalker);

  /** Output graph information per atom.
   */
  void OutputGraphInfoPerAtom() const;

  /** Output graph information per bond.
   */
  void OutputGraphInfoPerBond() const;

  std::deque<atom *> AtomStack;
  std::deque<bond::ptr > BackEdgeStack;
  int CurrentGraphNr;
  int ComponentNumber;
  atom *Root;
  bool BackStepping;

  typedef std::list< ConnectedSubgraph > ConnectedSubgraphList;

  ConnectedSubgraphList ListOfConnectedSubgraphs;
};

#endif /* DEPTHFIRSTSEARCHANALYSIS_HPP_ */