Generated on Wed Apr 29 2015 11:51:40 for GGL-4.1.2 by doxygen 1.8.3.1
SubGraph.hh
Go to the documentation of this file.
1 #ifndef SGM_SUBGRAPH_HH_
2 #define SGM_SUBGRAPH_HH_
3 
4 #include "sgm/Graph_Interface.hh"
5 #include "sgm/Match.hh"
6 
7 namespace sgm
8 {
9 
10  /*! @brief Subgraph of a Graph_Interface for matching
11  *
12  * Represents only a subset of the nodes of a graph and all edges between
13  * these nodes by wrapping the source graph.
14  *
15  * @author Martin Mann (c) 2009 http://www.bioinf.uni-freiburg.de/~mmann/
16  */
17  class SubGraph : public sgm::Graph_Interface
18  {
19  public:
20 
21  //! Type that defines a node index subset to be present in a subgraph
22  typedef std::vector< IndexType > NodeList;
23 
24  protected:
25 
26  /*!
27  * Special edge descriptor to enable the iteration over the edges
28  * covered by this subgraph.
29  *
30  */
31  class EdgeDescriptor : public sgm::Graph_Interface::EdgeDescriptor {
32  protected:
33 
34  //! the source of the edge described
35  using Graph_Interface::EdgeDescriptor::from;
36  //! the target of the edge described
37  using Graph_Interface::EdgeDescriptor::to;
38 
39  //! the iterator to the current edge
40  OutEdge_iterator curEdge;
41  //! the iterator to the edge iteration end
42  OutEdge_iterator edgeEnd;
43  //! access to the parent class for full subgraph information
44  const SubGraph & parent;
45 
46  public:
47  //! Construction
48  //! @param curEdge the iterator to the current edge
49  //! @param edgeEnd the iterator to the iteration end
50  //! @param parent access to the parent full graph information
51  EdgeDescriptor( const Graph_Interface::OutEdge_iterator & curEdge
52  , const Graph_Interface::OutEdge_iterator & edgeEnd
53  , const SubGraph & parent );
54 
55  //! Destruction
56  virtual
57  ~EdgeDescriptor();
58 
59  //! Access to the label of the edge.
60  //! @return the edge label
61  virtual
62  const std::string&
63  getEdgeLabel(void) const;
64 
65  //! Equality comparison
66  //! @param ed the edge to compare to
67  //! @return true if both descriptors describe the same edge
68  virtual
69  bool
70  operator==(const EdgeDescriptor& ed ) const;
71 
72  //! Inequality comparison
73  //! @param ed the edge to compare to
74  //! @return true if both descriptors describe different edges
75  virtual
76  bool
77  operator!=(const EdgeDescriptor& ed ) const;
78 
79  //! Inequality comparison
80  //! @param ed the edge to compare to
81  //! @return true if both descriptors describe different edges
82  virtual
83  bool
84  operator!=(const Graph_Interface::EdgeDescriptor& ed ) const;
85 
86  //! Iterator support
87  //! @return the next EdgeDescriptor in the adjacency
88  virtual
89  EdgeDescriptor&
90  operator++();
91 
92  //! Create a heap copy of this object. NOTE: this has to be
93  //! removed by the calling function.
94  //! @return a new heap copy of this object
95  virtual
96  EdgeDescriptor *
97  clone() const;
98 
99  };
100 
101 
102  protected:
103 
104  static const IndexType NOT_MAPPED_INDEX;
105 
106  //! The original graph this object is a subgraph of.
107  const Graph_Interface & fullGraph;
108 
109  //! The subset of node indices of fullGraph represented by this graph
110  NodeList nodeList;
111 
112  //! Mapping of global indices of fullGraph to local indices of this
113  //! subgraph
114  Match full2sub;
115 
116  public:
117 
118  /*!
119  * Construction of a subgraph from explicit node list.
120  *
121  * @param fullGraph the original graph this object should be a
122  * subgraph of
123  * @param nodeList the subset of node indices present in the subgraph
124  */
125  SubGraph( const Graph_Interface & fullGraph
126  , const NodeList & nodeList );
127 
128  /*!
129  * Construction of a subgraph from a component labeling.
130  *
131  * @param fullGraph the original graph this object should be a
132  * subgraph of
133  * @param compLabel component labeling of the fullGraph
134  * @param subGraphLabel the label in compLabel that defines the nodes
135  * of this subgraph
136  */
137  SubGraph( const Graph_Interface & fullGraph
138  , const CompLabel & compLabel
139  , const size_t subGraphLabel );
140 
141 
142  //! Destruction of the subgraph
143  virtual ~SubGraph();
144 
145 
146 
147  //! Access to the number of nodes of the subgraph
148  //! @return the overall node number
149  virtual
150  size_t
151  getNodeNumber(void) const;
152 
153  //! Access to iteration begin for the edge in the adjacency list of
154  //! a specified node
155  //! @param i the index of the node of interest
156  //! @return the iterator to the first edge within the adjacency of i
157  virtual
158  OutEdge_iterator
159  getOutEdgesBegin( const IndexType & i ) const;
160 
161  //! Access to iteration end for the edge in the adjacency list of
162  //! a specified node
163  //! @param i the index of the node of interest
164  //! @return the iterator the end of the adjacency iteration of i
165  virtual
166  OutEdge_iterator
167  getOutEdgesEnd( const IndexType & i ) const;
168 
169  //! Access to the label of a specified node
170  //! @param i the index of the node of interest
171  //! @return a string representation of the node label
172  virtual
173  std::string
174  getNodeLabel(const IndexType & i) const;
175 
176 };
177 
178 } // namespace sgm
179 
180 #include "sgm/Pattern.hh"
181 
182 namespace sgm
183 {
184 
185  /*!
186  * A Pattern that represents only a subset of the nodes of a graph and all
187  * edges between these nodes by wrapping the source graph and some
188  * additional constraints
189  *
190  * @author Martin Mann - 2010 - http://www.bioinf.uni-freiburg.de/~mmann/
191  */
192  class SubGraphPattern : public SubGraph, public Pattern
193  {
194  protected:
195 
196  //! the graph to be represented as a pattern
197  using Pattern::graph;
198 
199  //! the additional match constraints to be fulfilled by each match
200  using Pattern::matchConstraints;
201 
202  //! the wildcard string to be used for matching
203  using Pattern::usedWildcard;
204 
205  public:
206 
207  /*!
208  * Construction of a subgraph from explicit node list.
209  *
210  * @param fullGraph the original graph this object should be a
211  * subgraph of
212  * @param nodeList the subset of node indices present in the subgraph
213  */
214  SubGraphPattern( const Graph_Interface & fullGraph
215  , const NodeList & nodeList );
216 
217  /*!
218  * Construction of a subgraph from a component labeling.
219  *
220  * @param fullGraph the original graph this object should be a
221  * subgraph of
222  * @param compLabel component labeling of the fullGraph
223  * @param subGraphLabel the label in compLabel that defines the nodes
224  * of this subgraph
225  */
226  SubGraphPattern( const Graph_Interface & fullGraph
227  , const CompLabel & compLabel
228  , const size_t subGraphLabel );
229 
230 
231  /*!
232  * Construction of a subgraph from explicit node list.
233  *
234  * @param fullGraph the original graph this object should be a
235  * subgraph of
236  * @param nodeList the subset of node indices present in the subgraph
237  * @param matchConstraints the additional matching constraints to be
238  * fulfilled for this pattern, NOTE: indices have to correspond
239  * to the initial fullGraph instance and to be compatible with
240  * the subgraph definition !
241  */
242  SubGraphPattern( const Graph_Interface & fullGraph
243  , const NodeList & nodeList
244  , const ConstraintVec & matchConstraints );
245 
246  /*!
247  * Construction of a subgraph from a component labeling.
248  *
249  * @param fullGraph the original graph this object should be a
250  * subgraph of
251  * @param compLabel component labeling of the fullGraph
252  * @param subGraphLabel the label in compLabel that defines the nodes
253  * of this subgraph
254  * @param matchConstraints the additional matching constraints to be
255  * fulfilled for this pattern, NOTE: indices have to correspond
256  * to the initial fullGraph instance and to be compatible with
257  * the subgraph definition !
258  */
259  SubGraphPattern( const Graph_Interface & fullGraph
260  , const CompLabel & compLabel
261  , const size_t subGraphLabel
262  , const ConstraintVec & matchConstraints );
263 
264  /*!
265  * Construction of a subgraph from explicit node list.
266  *
267  * @param fullGraph the original graph this object should be a
268  * subgraph of
269  * @param nodeList the subset of node indices present in the subgraph
270  * @param wildcardToUse the wildcard to use for matching
271  */
272  SubGraphPattern( const Graph_Interface & fullGraph
273  , const NodeList & nodeList
274  , const std::string & wildcardToUse );
275 
276  /*!
277  * Construction of a subgraph from a component labeling.
278  *
279  * @param fullGraph the original graph this object should be a
280  * subgraph of
281  * @param compLabel component labeling of the fullGraph
282  * @param subGraphLabel the label in compLabel that defines the nodes
283  * of this subgraph
284  * @param wildcardToUse the wildcard to use for matching
285  */
286  SubGraphPattern( const Graph_Interface & fullGraph
287  , const CompLabel & compLabel
288  , const size_t subGraphLabel
289  , const std::string & wildcardToUse );
290 
291 
292  /*!
293  * Construction of a subgraph from explicit node list.
294  *
295  * @param fullGraph the original graph this object should be a
296  * subgraph of
297  * @param nodeList the subset of node indices present in the subgraph
298  * @param matchConstraints the additional matching constraints to be
299  * fulfilled for this pattern, NOTE: indices have to correspond
300  * to the initial fullGraph instance and to be compatible with
301  * the subgraph definition !
302  * @param wildcardToUse the wildcard to use for matching
303  */
304  SubGraphPattern( const Graph_Interface & fullGraph
305  , const NodeList & nodeList
306  , const ConstraintVec & matchConstraints
307  , const std::string & wildcardToUse );
308 
309  /*!
310  * Construction of a subgraph from a component labeling.
311  *
312  * @param fullGraph the original graph this object should be a
313  * subgraph of
314  * @param compLabel component labeling of the fullGraph
315  * @param subGraphLabel the label in compLabel that defines the nodes
316  * of this subgraph
317  * @param matchConstraints the additional matching constraints to be
318  * fulfilled for this pattern, NOTE: indices have to correspond
319  * to the initial fullGraph instance and to be compatible with
320  * the subgraph definition !
321  * @param wildcardToUse the wildcard to use for matching
322  */
323  SubGraphPattern( const Graph_Interface & fullGraph
324  , const CompLabel & compLabel
325  , const size_t subGraphLabel
326  , const ConstraintVec & matchConstraints
327  , const std::string & wildcardToUse );
328 
329 
330  //! Destruction of the subgraph
331  virtual ~SubGraphPattern();
332 
333 
334  protected:
335 
336  /*!
337  * Does the reindexing of the nodes within the given match constraints
338  * onto the new indices within the subgraph, where the index mapping is
339  * given by full2sub.
340  *
341  * @param originalConstraints the matching constraints to be remapped
342  * @param full2sub the mapping of the indices used in the given
343  * constraints onto nodes within the subgraph.
344  * @param remappedConstraints the container that will hold the
345  * remapped matching constraints
346  */
347  static
348  void
349  remapConstraints( const ConstraintVec & originalConstraints
350  , const Match & full2sub
351  , ConstraintVec & remappedConstraints );
352 
353  };
354 
355 } // namespace sgm
356 
357 // inline implementations
358 #include "sgm/SubGraph.icc"
359 
360 #endif /*SUBGRAPH_HH_*/