Generated on Wed Apr 29 2015 11:51:40 for GGL-4.1.2 by doxygen 1.8.3.1
Graph_boost.hh
Go to the documentation of this file.
1 #ifndef SGM_GRAPH_BOOST_HH_
2 #define SGM_GRAPH_BOOST_HH_
3 
4 #include "sgm/Graph_Interface.hh"
5 
6 #include <boost/graph/adjacency_list.hpp>
7 
8 #include <vector>
9 #include <utility>
10 
11 
12 namespace sgm {
13 
14 
15 #define SGM_GRAPH_BOOST_TEMPLATE \
16  template < class GRAPH, \
17  typename NODE_LABEL_PROPERTY, \
18  typename EDGE_LABEL_PROPERTY, \
19  typename NODE_INDEX_PROPERTY \
20  >
21 
22 #define SGM_GRAPH_BOOST_TYPE \
23  sgm::Graph_boost < GRAPH \
24  , NODE_LABEL_PROPERTY \
25  , EDGE_LABEL_PROPERTY \
26  , NODE_INDEX_PROPERTY \
27  >
28 
29 
30  /*! @brief Graph_Interface wrapper for boost graphs
31  *
32  * This class implements the Graph interface of a labeled undirected
33  * graph. It is used as an interface of an undirected labeled
34  * boost graph to the sub graph matching algorithms of the sgm library.
35  * The template parameter GRAPH represents the type of the
36  * boost graph to use. The type names NODE_LABEL_PROPERTY and
37  * EDGE_LABEL_PROPERTY are used to generate the node and edge labels of
38  * the graph. The type name NODE_INDEX_PROPERTY is used to derive the
39  * corresponding local node index for a certain vertex in covered graph.
40  *
41  * @author Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/
42  */
43  template < class GRAPH,
44  typename NODE_LABEL_PROPERTY = boost::vertex_name_t,
45  typename EDGE_LABEL_PROPERTY = boost::edge_name_t,
46  typename NODE_INDEX_PROPERTY = boost::vertex_index_t >
47  class Graph_boost : public Graph_Interface {
48 
49  protected:
50 
51  //! the graph to map
52  const GRAPH & graph;
53  //! the number of nodes of graph
54  const size_t graphSize;
55 
56  typedef typename boost::property_map<GRAPH, NODE_INDEX_PROPERTY>::const_type NodeIndexMap;
57  //! node index access
58  NodeIndexMap nodeIndexMap;
59 
60  //! node label access
61  typename boost::property_map<GRAPH, NODE_LABEL_PROPERTY>::const_type
62  nodeLabelMap;
63 
64  typedef typename boost::property_map<GRAPH, EDGE_LABEL_PROPERTY>::const_type EdgeLabelMap;
65  //! edge label access
66  EdgeLabelMap edgeLabelMap;
67 
68  public:
69 
70  typedef GRAPH InternalBoostGraph;
71 
72  //! Construction of the interface graph.
73  //! @param graph the boost graph to use as internal data structure
74  Graph_boost( const GRAPH & graph );
75 
76  //! Destruction
77  virtual
78  ~Graph_boost();
79 
80  //! Access to the number of nodes of the graph
81  //! @return the overall node number
82  virtual
83  size_t
84  getNodeNumber(void) const;
85 
86  //! Access to the label of a specified node
87  //! @param i the index of the node of interest
88  //! @return a string representation of the node label
89  virtual
90  std::string
91  getNodeLabel(const IndexType & i) const;
92 
93  //! Access to the internal GRAPH object
94  //! @return a refence to the graph object
95  const GRAPH &
96  getGraph(void) const;
97 
98  public:
99 
100  /*!
101  * Special edge descriptor to enable the iteration over the edges
102  * contained in the internally used boost graph instance.
103  *
104  */
105  class EdgeDescriptor : public Graph_Interface::EdgeDescriptor {
106  protected:
107  //! the source of the edge described
108  using Graph_Interface::EdgeDescriptor::from;
109  //! the target of the edge described
110  using Graph_Interface::EdgeDescriptor::to;
111  //! the out edge iterator of the current target node within
112  //! the local adjacency list
113  typename GRAPH::out_edge_iterator cur_edge;
114  //! the edge iterator that marks the end of
115  //! the local adjacency list
116  typename GRAPH::out_edge_iterator list_end;
117 
118  //! access to the parent instance for fast graph access
119  const Graph_boost& parent;
120 
121  public:
122 
123  //! Construction of a new edge descriptor given the our edge
124  //! iterators
125  //! @param cur_edge the current boost edge iterator
126  //! @param neigh_end the end of the edge iteration
127  //! @param parent access to the parent instance for graph access
128  EdgeDescriptor( const typename GRAPH::out_edge_iterator& cur_edge,
129  const typename GRAPH::out_edge_iterator& neigh_end,
130  const Graph_boost& parent );
131 
132  //! Destruction
133  virtual
134  ~EdgeDescriptor();
135 
136  //! Access to the label of the edge.
137  //! @return the edge label
138  virtual
139  const std::string&
140  getEdgeLabel(void) const;
141 
142  //! Equality comparison
143  //! @param ed the edge to compare to
144  //! @return true if both descriptors describe the same edge
145  virtual
146  bool
147  operator==(const EdgeDescriptor& ed ) const;
148 
149  //! Inequality comparison
150  //! @param ed the edge to compare to
151  //! @return true if both descriptors describe different edges
152  virtual
153  bool
154  operator!=(const EdgeDescriptor& ed ) const;
155 
156  //! Inequality comparison
157  //! @param ed the edge to compare to
158  //! @return true if both descriptors describe different edges
159  virtual
160  bool
161  operator!=(const Graph_Interface::EdgeDescriptor& ed ) const;
162 
163  //! Iterator support
164  //! @return the next EdgeDescriptor in the adjacency
165  virtual
166  EdgeDescriptor&
167  operator++();
168 
169  //! Create a heap copy of this object. NOTE: this has to be
170  //! removed by the calling function.
171  //! @return a new heap copy of this object
172  virtual
173  EdgeDescriptor *
174  clone() const;
175 
176  };
177 
178  //! Access to iteration begin for the edge in the adjacency list of
179  //! a specified node
180  //! @param i the index of the node of interest
181  //! @return the iterator to the first edge within the adjacency of i
182  virtual
183  OutEdge_iterator
184  getOutEdgesBegin( const IndexType & i ) const;
185 
186  //! Access to iteration end for the edge in the adjacency list of
187  //! a specified node
188  //! @param i the index of the node of interest
189  //! @return the iterator the end of the adjacency iteration of i
190  virtual
191  OutEdge_iterator
192  getOutEdgesEnd( const IndexType & i ) const;
193 
194  //////////////////// STATIC MEMBERS ///////////////////////////////////
195 
196  public:
197 
198  //! Static member function that allows for the indexing of the nodes
199  //! in the graph. It opens the property map for
200  //! NODE_INDEX_PROPERTY and sets an index with [0,num_vertices(g))
201  //! along the ordering defined by the vertex iterators.
202  //! Therefore, this function can be used to set the necessary local
203  //! indexes before creating a Graph_boost object.
204  //! NOTE : The property map is NOT CONSTRUCTED has to be already part
205  //! of the GRAPH definition! It is ONLY FILLED!
206  static
207  void
208  indexGraph ( GRAPH & graph );
209 
210  //! Counts the number of nodes a boost graph represents since the
211  //! number returned by boost::num_vertices might not be correct, e.g.
212  //! for boost::filtered_graph instances.
213  //! @param graph the graph to check
214  //! @return the graph's number of nodes
215  static
216  size_t
217  countRealNodeNumber( const GRAPH & graph );
218 
219  };
220 
221 
222 } // namespace sgm
223 
224 
225  // include template implementation of the class
226 #include "sgm/Graph_boost.icc"
227 
228 
229 #endif /*SGM_GRAPH_BOOST_HH_*/