Generated on Wed Apr 29 2015 11:51:40 for GGL-4.1.2 by doxygen 1.8.3.1
RP_Hanser96.hh
Go to the documentation of this file.
1 
2 #ifndef SGM_RP_HANSER96_HH_
3 #define SGM_RP_HANSER96_HH_
4 
5 
6 #include <boost/graph/adjacency_list.hpp>
7 
8 #include "sgm/RingPerception.hh"
9 
10 #include <limits>
11 #include <set>
12 
13 
14 namespace sgm {
15 
16  /*! @brief Ring enumeration ala Hanser et al.
17  *
18  * Implementation of the exhaustive ring perception algorithm by
19  * Hanser et al. (1996)
20  *
21  * A New Algorithm for Exhaustive Ring Perception in a Molecular Graph
22  * T. Hanser, P. Jauffret, and G. Kaufmann
23  * J. Chem. Inf. Comput. Sci., 1996, 36, 1146-1152
24  *
25  * @author Martin Mann - 2010 - http://www.bioinf.uni-freiburg.de/~mmann/
26  *
27  */
28  class RP_Hanser96 : public RingPerception {
29  public:
30 
31  typedef std::set< std::pair<size_t,size_t> > BondSet;
32 
33  //! construction
34  RP_Hanser96();
35 
36  //! destruction
37  virtual ~RP_Hanser96();
38 
39 
40  /*!
41  * Finds ALL rings within the given graph and reports each found
42  * ring to the assigned reporter. The enumeration can be restricted
43  * to rings up to a given ring size, ie. number of nodes per ring.
44  *
45  * @param graph the graph to be analyzed
46  * @param reporter the RingReporter to report all found rings to
47  * @param maxRingSize the maximal size of rings to report
48  * @return the number of all rings within the gaph
49  */
50  size_t
51  findRings( const Graph_Interface & graph,
52  RingReporter & reporter,
53  const size_t maxRingSize = std::numeric_limits<size_t>::max());
54 
55  /*!
56  * Identifies all bonds participating in rings and stores the
57  * according vertex index pairs in the provided container.
58  *
59  * @param graph the graph to search for ring bonds
60  * @param ringBonds OUT : the container to fill with the ring bonds.
61  * NOTE: the container is cleared at the beginning of the call.
62  * @param maxRingSize the maximal size of rings to consider
63  *
64  * @return the number of ring bonds within the graph
65  */
66  size_t
67  findRingBonds( const Graph_Interface & graph
68  , BondSet & ringBonds
69  , const size_t maxRingSize = std::numeric_limits<size_t>::max() );
70 
71 
72  protected:
73 
74  //! information on the current ring part
75  struct RingInfo {
76  public:
77  RingReporter::RingNodes nodes;
78  RingReporter::RingList path;
79  };
80 
81 
82  //! The properties available for the nodes of the P-graph
83  typedef boost::property< boost::vertex_index_t, size_t >
84  Graph_NodeProperties;
85 
86  //! The properties available for the edges of the P-graph
87  typedef boost::property< boost::edge_name_t, RingInfo >
88  Graph_EdgeProperties;
89 
90  //! the P-graph type that is used to detect all rings
91  typedef boost::adjacency_list<
92  boost::multisetS, // store edges
93  boost::vecS, // store vertices
94  boost::undirectedS, // is an undirected graph
95  Graph_NodeProperties, // index information
96  Graph_EdgeProperties // ring information
97  >
98  P_Graph;
99 
100  protected:
101 
102  //! the P-graph to be compressed during the ring perception
103  P_Graph pGraph;
104 
105  //! the index access for pGraph
106  boost::property_map<P_Graph, boost::vertex_index_t>::type pGraphIndex;
107  //! the edge label access for pGraph, i.e. the according RingList
108  boost::property_map<P_Graph, boost::edge_name_t>::type pGraphPath;
109 
110  //! the degree of each node in pGraph
111  std::vector<size_t> pGraphDegree;
112  //! the nodes to be removed during the ring perception from pGraph
113  std::vector<size_t> toRemove;
114 
115  protected:
116 
117  /*!
118  * Initializes the pGraph member with the given graph. If direct loops
119  * are found, these are directly reported and counted.
120  *
121  * @param graph the graph to be encoded in the pGraph member
122  * @param reporter the RingReporter to report all rings to
123  * @return the number of rings found
124  */
125  size_t
126  initializeP_Graph( const Graph_Interface & graph
127  , RingReporter& reporter);
128 
129  /*!
130  * Virtually removes the vertex nextToRemove from the pGraph and
131  * reports all found rings to the given reporter.
132  * The removal is only virtual, since the node remains within the
133  * pGraph but all adjacent edges are removed, i.e. it is not
134  * accessible anymore in later iterations. This is to ease the
135  * maintenance of the temporary data structures.
136  *
137  * @param nextToRemove the index of the vertex to be removed
138  * @param graph the graph searched (needed for ring report)
139  * @param reporter the RingReporter to report all rings to
140  * @param maxRingSize the maximal ring size to consider
141  * @return the number of rings found
142  */
143  size_t
144  remove_vertex( const size_t nextToRemove
145  , const Graph_Interface& graph
146  , RingReporter& reporter
147  , const size_t maxRingSize);
148 
149  struct degree_sort {
150  const std::vector<size_t> & degree;
151  degree_sort( const std::vector<size_t> & degree_ )
152  : degree(degree_)
153  {}
154  bool operator()(const size_t& i1, const size_t& i2 ) const {
155  return degree[i1] > degree[i2];
156  }
157  };
158 
159 
160  /**
161  * Stores the bond information for loops.
162  */
163  class LoopBondReporter : public RingReporter {
164 
165  protected:
166 
167  BondSet & bondSet;
168 
169  public:
170  //! construction
171  LoopBondReporter( BondSet & bondSet );
172  //! destruction
173  virtual ~LoopBondReporter();
174 
175  /*!
176  * Is called to report a ring.
177  * @param graph the graph that contains the ring
178  * @param ringList the ring to report
179  */
180  virtual
181  void
182  reportRing( const Graph_Interface& graph, const RingList & ringList );
183 
184  };
185 
186  };
187 
188 } // namespace sgm
189 
190 #endif /* SGM_RP_HANSER96_HH_ */