| 1 | <HTML> |
|---|
| 2 | <!-- |
|---|
| 3 | -- (C) Copyright David Abrahams and Jeremy Siek 2000. Permission to copy, |
|---|
| 4 | -- use, modify, sell and distribute this software is granted provided this |
|---|
| 5 | -- copyright notice appears in all copies. This software is provided |
|---|
| 6 | -- "as is" without express or implied warranty, and with no claim as |
|---|
| 7 | -- to its suitability for any purpose. |
|---|
| 8 | --> |
|---|
| 9 | <Head> |
|---|
| 10 | <Title>Boost Graph Library: Reverse Graph Adaptor</Title> |
|---|
| 11 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
|---|
| 12 | ALINK="#ff0000"> |
|---|
| 13 | <IMG SRC="../../../boost.png" |
|---|
| 14 | ALT="C++ Boost" width="277" height="86"> |
|---|
| 15 | |
|---|
| 16 | <BR Clear> |
|---|
| 17 | |
|---|
| 18 | |
|---|
| 19 | |
|---|
| 20 | <H1><A NAME="sec:reverse-graph-adaptor"></A> |
|---|
| 21 | </h1> |
|---|
| 22 | <pre> |
|---|
| 23 | reverse_graph<<a href="./BidirectionalGraph.html">BidirectionalGraph</a>, GraphReference> |
|---|
| 24 | </pre> |
|---|
| 25 | |
|---|
| 26 | The <tt>reverse_graph</tt> adaptor flips the in-edges and out-edges of |
|---|
| 27 | a <a href="./BidirectionalGraph.html">BidirectionalGraph</a>, |
|---|
| 28 | effectively transposing the graph. The construction of the |
|---|
| 29 | <tt>reverse_graph</tt> is constant time, providing a highly efficient |
|---|
| 30 | way to obtain a transposed-view of a graph. |
|---|
| 31 | |
|---|
| 32 | |
|---|
| 33 | <H3>Example</H3> |
|---|
| 34 | |
|---|
| 35 | The example from <a |
|---|
| 36 | href="../example/reverse-graph-eg.cpp"><tt>examples/reverse-graph-eg.cpp</tt></a>. |
|---|
| 37 | |
|---|
| 38 | <pre> |
|---|
| 39 | int |
|---|
| 40 | main() |
|---|
| 41 | { |
|---|
| 42 | typedef boost::adjacency_list< |
|---|
| 43 | boost::vecS, boost::vecS, boost::bidirectionalS, |
|---|
| 44 | > Graph; |
|---|
| 45 | |
|---|
| 46 | Graph G(5); |
|---|
| 47 | boost::add_edge(0, 2, G); |
|---|
| 48 | boost::add_edge(1, 1, G); |
|---|
| 49 | boost::add_edge(1, 3, G); |
|---|
| 50 | boost::add_edge(1, 4, G); |
|---|
| 51 | boost::add_edge(2, 1, G); |
|---|
| 52 | boost::add_edge(2, 3, G); |
|---|
| 53 | boost::add_edge(2, 4, G); |
|---|
| 54 | boost::add_edge(3, 1, G); |
|---|
| 55 | boost::add_edge(3, 4, G); |
|---|
| 56 | boost::add_edge(4, 0, G); |
|---|
| 57 | boost::add_edge(4, 1, G); |
|---|
| 58 | |
|---|
| 59 | std::cout << "original graph:" << std::endl; |
|---|
| 60 | boost::print_graph(G, boost::get(boost::vertex_index, G)); |
|---|
| 61 | |
|---|
| 62 | std::cout << std::endl << "reversed graph:" << std::endl; |
|---|
| 63 | boost::print_graph(boost::make_reverse_graph(G), |
|---|
| 64 | boost::get(boost::vertex_index, G)); |
|---|
| 65 | |
|---|
| 66 | |
|---|
| 67 | return 0; |
|---|
| 68 | } |
|---|
| 69 | </pre> |
|---|
| 70 | The output is: |
|---|
| 71 | <pre> |
|---|
| 72 | original graph: |
|---|
| 73 | 0 --> 2 |
|---|
| 74 | 1 --> 1 3 4 |
|---|
| 75 | 2 --> 1 3 4 |
|---|
| 76 | 3 --> 1 4 |
|---|
| 77 | 4 --> 0 1 |
|---|
| 78 | |
|---|
| 79 | reversed graph: |
|---|
| 80 | 0 --> 4 |
|---|
| 81 | 1 --> 1 2 3 4 |
|---|
| 82 | 2 --> 0 |
|---|
| 83 | 3 --> 1 2 |
|---|
| 84 | 4 --> 1 2 3 |
|---|
| 85 | </pre> |
|---|
| 86 | |
|---|
| 87 | <H3>Template Parameters</H3> |
|---|
| 88 | |
|---|
| 89 | <P> |
|---|
| 90 | <TABLE border> |
|---|
| 91 | <TR> |
|---|
| 92 | <th>Parameter</th><th>Description</th><th>Default</th> |
|---|
| 93 | </tr> |
|---|
| 94 | |
|---|
| 95 | <TR><TD><TT>BidirectionalGraph</TT></TD> |
|---|
| 96 | <TD>The graph type to be adapted.</TD> |
|---|
| 97 | <TD> </TD> |
|---|
| 98 | </TR> |
|---|
| 99 | |
|---|
| 100 | <TR><TD><TT>GraphReference</TT></TD> |
|---|
| 101 | <TD>This type should be <tt>const BidirectionalGraph&</tt> |
|---|
| 102 | if you want to create a const reverse graph, or <tt>BidirectionalGraph&</tt> if you want to create a non-const reverse graph.</TD> |
|---|
| 103 | <TD><tt>const BidirectionalGraph&</tt></TD> |
|---|
| 104 | </TR> |
|---|
| 105 | |
|---|
| 106 | |
|---|
| 107 | </table> |
|---|
| 108 | |
|---|
| 109 | |
|---|
| 110 | <H3>Model of</H3> |
|---|
| 111 | |
|---|
| 112 | <P> |
|---|
| 113 | <a href="./BidirectionalGraph.html">BidirectionalGraph</a> |
|---|
| 114 | and optionally |
|---|
| 115 | <a href="./VertexListGraph.html">VertexListGraph</a> |
|---|
| 116 | and <a href="./PropertyGraph.html">PropertyGraph</a> |
|---|
| 117 | |
|---|
| 118 | |
|---|
| 119 | <H3>Where Defined</H3> |
|---|
| 120 | |
|---|
| 121 | <P> |
|---|
| 122 | <a href="../../../boost/graph/reverse_graph.hpp"><TT>boost/graph/reverse_graph.hpp</TT></a> |
|---|
| 123 | |
|---|
| 124 | |
|---|
| 125 | <H2>Associated Types</H2> |
|---|
| 126 | |
|---|
| 127 | <hr> |
|---|
| 128 | |
|---|
| 129 | <tt>graph_traits<reverse_graph>::vertex_descriptor</tt> |
|---|
| 130 | <br><br> |
|---|
| 131 | The type for the vertex descriptors associated with the |
|---|
| 132 | <TT>reverse_graph</TT>. |
|---|
| 133 | |
|---|
| 134 | <hr> |
|---|
| 135 | |
|---|
| 136 | <tt>graph_traits<reverse_graph>::edge_descriptor</tt> |
|---|
| 137 | <br><br> |
|---|
| 138 | The type for the edge descriptors associated with the |
|---|
| 139 | <TT>reverse_graph</TT>. |
|---|
| 140 | |
|---|
| 141 | <hr> |
|---|
| 142 | |
|---|
| 143 | <tt>graph_traits<reverse_graph>::vertex_iterator</tt> |
|---|
| 144 | <br><br> |
|---|
| 145 | The type for the iterators returned by <TT>vertices()</TT>. |
|---|
| 146 | |
|---|
| 147 | <hr> |
|---|
| 148 | |
|---|
| 149 | <tt>graph_traits<reverse_graph>::edge_iterator</tt> |
|---|
| 150 | <br><br> |
|---|
| 151 | The type for the iterators returned by <TT>edges()</TT>. |
|---|
| 152 | |
|---|
| 153 | <hr> |
|---|
| 154 | |
|---|
| 155 | |
|---|
| 156 | <tt>graph_traits<reverse_graph>::out_edge_iterator</tt> |
|---|
| 157 | <br><br> |
|---|
| 158 | The type for the iterators returned by <TT>out_edges()</TT>. |
|---|
| 159 | |
|---|
| 160 | <hr> |
|---|
| 161 | |
|---|
| 162 | <tt>graph_traits<reverse_graph>::adjacency_iterator</tt> |
|---|
| 163 | <br><br> |
|---|
| 164 | The type for the iterators returned by <TT>adjacent_vertices()</TT>. |
|---|
| 165 | |
|---|
| 166 | <hr> |
|---|
| 167 | |
|---|
| 168 | <tt>graph_traits<reverse_graph>::directed_category</tt> |
|---|
| 169 | <br><br> |
|---|
| 170 | Provides information about whether the graph is |
|---|
| 171 | directed (<TT>directed_tag</TT>) or undirected |
|---|
| 172 | (<TT>undirected_tag</TT>). |
|---|
| 173 | |
|---|
| 174 | <hr> |
|---|
| 175 | |
|---|
| 176 | <tt>graph_traits<reverse_graph>::edge_parallel_category</tt> |
|---|
| 177 | <br><br> |
|---|
| 178 | This describes whether the graph class allows the insertion of |
|---|
| 179 | parallel edges (edges with the same source and target). The two tags |
|---|
| 180 | are <TT>allow_parallel_edge-_tag</TT> and |
|---|
| 181 | <TT>disallow_parallel_edge_tag</TT>. The |
|---|
| 182 | <TT>setS</TT> and <TT>hash_setS</TT> variants disallow |
|---|
| 183 | parallel edges while the others allow parallel edges. |
|---|
| 184 | |
|---|
| 185 | <hr> |
|---|
| 186 | |
|---|
| 187 | <tt>graph_traits<reverse_graph>::vertices_size_type</tt> |
|---|
| 188 | <br><br> |
|---|
| 189 | The type used for dealing with the number of vertices in the graph. |
|---|
| 190 | |
|---|
| 191 | <hr> |
|---|
| 192 | |
|---|
| 193 | <tt>graph_traits<reverse_graph>::edge_size_type</tt> |
|---|
| 194 | <br><br> |
|---|
| 195 | The type used for dealing with the number of edges in the graph. |
|---|
| 196 | |
|---|
| 197 | <hr> |
|---|
| 198 | |
|---|
| 199 | <tt>graph_traits<reverse_graph>::degree_size_type</tt> |
|---|
| 200 | <br><br> |
|---|
| 201 | The type used for dealing with the number of edges incident to a vertex |
|---|
| 202 | in the graph. |
|---|
| 203 | |
|---|
| 204 | <hr> |
|---|
| 205 | |
|---|
| 206 | <tt>property_map<reverse_graph, PropertyTag>::type</tt><br> |
|---|
| 207 | and<br> |
|---|
| 208 | <tt>property_map<reverse_graph, PropertyTag>::const_type</tt> |
|---|
| 209 | <br><br> |
|---|
| 210 | The property map type for vertex or edge properties in the graph. The |
|---|
| 211 | specific property is specified by the <TT>PropertyTag</TT> template argument, |
|---|
| 212 | and must match one of the properties specified in the |
|---|
| 213 | <TT>VertexProperty</TT> or <TT>EdgeProperty</TT> for the graph. |
|---|
| 214 | |
|---|
| 215 | <hr> |
|---|
| 216 | |
|---|
| 217 | |
|---|
| 218 | <H2>Member Functions</H2> |
|---|
| 219 | |
|---|
| 220 | <hr> |
|---|
| 221 | |
|---|
| 222 | <pre> |
|---|
| 223 | reverse_graph(BidirectionalGraph& g) |
|---|
| 224 | </pre> |
|---|
| 225 | Constructor. Create a reversed (transposed) view of the graph <tt>g</tt>. |
|---|
| 226 | |
|---|
| 227 | <hr> |
|---|
| 228 | |
|---|
| 229 | <H2>Non-Member Functions</H2> |
|---|
| 230 | |
|---|
| 231 | <hr> |
|---|
| 232 | |
|---|
| 233 | <pre> |
|---|
| 234 | template <class BidirectionalGraph> |
|---|
| 235 | reverse_graph<BidirectionalGraph, BidirectionalGraph&> |
|---|
| 236 | make_reverse_graph(BidirectionalGraph& g); |
|---|
| 237 | |
|---|
| 238 | template <class BidirectionalGraph> |
|---|
| 239 | reverse_graph<BidirectionalGraph, const BidirectionalGraph&> |
|---|
| 240 | make_reverse_graph(const BidirectionalGraph& g) |
|---|
| 241 | |
|---|
| 242 | </pre> |
|---|
| 243 | Helper function for creating a <tt>reverse_graph</tt>. |
|---|
| 244 | |
|---|
| 245 | <hr> |
|---|
| 246 | |
|---|
| 247 | <pre> |
|---|
| 248 | std::pair<vertex_iterator, vertex_iterator> |
|---|
| 249 | vertices(const reverse_graph& g) |
|---|
| 250 | </pre> |
|---|
| 251 | Returns an iterator-range providing access to the vertex set of graph |
|---|
| 252 | <tt>g</tt>. |
|---|
| 253 | |
|---|
| 254 | <hr> |
|---|
| 255 | |
|---|
| 256 | <pre> |
|---|
| 257 | std::pair<out_edge_iterator, out_edge_iterator> |
|---|
| 258 | out_edges(vertex_descriptor v, const reverse_graph& g) |
|---|
| 259 | </pre> |
|---|
| 260 | Returns an iterator-range providing access to the out-edges of vertex |
|---|
| 261 | <tt>v</tt> in graph <tt>g</tt>. These out-edges correspond to the |
|---|
| 262 | in-edges of the adapted graph. |
|---|
| 263 | |
|---|
| 264 | <hr> |
|---|
| 265 | |
|---|
| 266 | <pre> |
|---|
| 267 | std::pair<in_edge_iterator, in_edge_iterator> |
|---|
| 268 | in_edges(vertex_descriptor v, const reverse_graph& g) |
|---|
| 269 | </pre> |
|---|
| 270 | Returns an iterator-range providing access to the in-edges of vertex |
|---|
| 271 | <tt>v</tt> in graph <tt>g</tt>. These in-edges correspond to the |
|---|
| 272 | out edges of the adapted graph. |
|---|
| 273 | |
|---|
| 274 | <hr> |
|---|
| 275 | |
|---|
| 276 | <pre> |
|---|
| 277 | std::pair<adjacency_iterator, adjacency__iterator> |
|---|
| 278 | adjacent_vertices(vertex_descriptor v, const reverse_graph& g) |
|---|
| 279 | </pre> |
|---|
| 280 | Returns an iterator-range providing access to the adjacent vertices of vertex |
|---|
| 281 | <tt>v</tt> in graph <tt>g</tt>. |
|---|
| 282 | |
|---|
| 283 | <hr> |
|---|
| 284 | |
|---|
| 285 | <pre> |
|---|
| 286 | vertex_descriptor |
|---|
| 287 | source(edge_descriptor e, const reverse_graph& g) |
|---|
| 288 | </pre> |
|---|
| 289 | Returns the source vertex of edge <tt>e</tt>. |
|---|
| 290 | |
|---|
| 291 | <hr> |
|---|
| 292 | |
|---|
| 293 | <pre> |
|---|
| 294 | vertex_descriptor |
|---|
| 295 | target(edge_descriptor e, const reverse_graph& g) |
|---|
| 296 | </pre> |
|---|
| 297 | Returns the target vertex of edge <tt>e</tt>. |
|---|
| 298 | |
|---|
| 299 | <hr> |
|---|
| 300 | |
|---|
| 301 | <pre> |
|---|
| 302 | degree_size_type |
|---|
| 303 | out_degree(vertex_descriptor u, const reverse_graph& g) |
|---|
| 304 | </pre> |
|---|
| 305 | Returns the number of edges leaving vertex <tt>u</tt>. |
|---|
| 306 | |
|---|
| 307 | <hr> |
|---|
| 308 | |
|---|
| 309 | <pre> |
|---|
| 310 | degree_size_type |
|---|
| 311 | in_degree(vertex_descriptor u, const reverse_graph& g) |
|---|
| 312 | </pre> |
|---|
| 313 | Returns the number of edges entering vertex <tt>u</tt>. This operation |
|---|
| 314 | is only available if <TT>bidirectionalS</TT> was specified for |
|---|
| 315 | the <TT>Directed</TT> template parameter. |
|---|
| 316 | |
|---|
| 317 | <hr> |
|---|
| 318 | |
|---|
| 319 | <pre> |
|---|
| 320 | vertices_size_type |
|---|
| 321 | num_vertices(const reverse_graph& g) |
|---|
| 322 | </pre> |
|---|
| 323 | Returns the number of vertices in the graph <tt>g</tt>. |
|---|
| 324 | |
|---|
| 325 | <hr> |
|---|
| 326 | |
|---|
| 327 | <pre> |
|---|
| 328 | vertex_descriptor |
|---|
| 329 | vertex(vertices_size_type n, const reverse_graph& g) |
|---|
| 330 | </pre> |
|---|
| 331 | Returns the nth vertex in the graph's vertex list. |
|---|
| 332 | |
|---|
| 333 | <hr> |
|---|
| 334 | |
|---|
| 335 | <pre> |
|---|
| 336 | std::pair<edge_descriptor, bool> |
|---|
| 337 | edge(vertex_descriptor u, vertex_descriptor v, |
|---|
| 338 | const reverse_graph& g) |
|---|
| 339 | </pre> |
|---|
| 340 | Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in |
|---|
| 341 | graph <tt>g</tt>. |
|---|
| 342 | |
|---|
| 343 | <hr> |
|---|
| 344 | |
|---|
| 345 | <pre> |
|---|
| 346 | template <class <a href="./PropertyTag.html">PropertyTag</a>> |
|---|
| 347 | property_map<reverse_graph, PropertyTag>::type |
|---|
| 348 | get(PropertyTag, reverse_graph& g) |
|---|
| 349 | |
|---|
| 350 | template <class <a href="./PropertyTag.html">PropertyTag</a>> |
|---|
| 351 | property_map<reverse_graph, Tag>::const_type |
|---|
| 352 | get(PropertyTag, const reverse_graph& g) |
|---|
| 353 | </pre> |
|---|
| 354 | Returns the property map object for the vertex property specified by |
|---|
| 355 | <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the |
|---|
| 356 | properties specified in the graph's <TT>VertexProperty</TT> template |
|---|
| 357 | argument. |
|---|
| 358 | |
|---|
| 359 | <hr> |
|---|
| 360 | |
|---|
| 361 | <pre> |
|---|
| 362 | template <class <a href="./PropertyTag.html">PropertyTag</a>, class X> |
|---|
| 363 | typename property_traits<property_map<reverse_graph, PropertyTag>::const_type>::value_type |
|---|
| 364 | get(PropertyTag, const reverse_graph& g, X x) |
|---|
| 365 | </pre> |
|---|
| 366 | This returns the property value for <tt>x</tt>, which is either |
|---|
| 367 | a vertex or edge descriptor. |
|---|
| 368 | <hr> |
|---|
| 369 | |
|---|
| 370 | <pre> |
|---|
| 371 | template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> |
|---|
| 372 | void |
|---|
| 373 | put(PropertyTag, const reverse_graph& g, X x, const Value& value) |
|---|
| 374 | </pre> |
|---|
| 375 | This sets the property value for <tt>x</tt> to |
|---|
| 376 | <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor. |
|---|
| 377 | <tt>Value</tt> must be convertible to |
|---|
| 378 | <tt>typename property_traits<property_map<reverse_graph, PropertyTag>::type>::value_type</tt> |
|---|
| 379 | |
|---|
| 380 | <hr> |
|---|
| 381 | |
|---|
| 382 | <pre> |
|---|
| 383 | template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> |
|---|
| 384 | typename property_value<GraphProperties, GraphPropertyTag>::type& |
|---|
| 385 | get_property(reverse_graph& g, GraphPropertyTag); |
|---|
| 386 | </pre> |
|---|
| 387 | Return the property specified by <tt>GraphPropertyTag</tt> that is |
|---|
| 388 | attached to the graph object <tt>g</tt>. The <tt>property_value</tt> |
|---|
| 389 | traits class is defined in <a |
|---|
| 390 | href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. |
|---|
| 391 | |
|---|
| 392 | <hr> |
|---|
| 393 | |
|---|
| 394 | <pre> |
|---|
| 395 | template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> |
|---|
| 396 | const typename property_value<GraphProperties, GraphPropertyTag>::type& |
|---|
| 397 | get_property(const reverse_graph& g, GraphPropertyTag); |
|---|
| 398 | </pre> |
|---|
| 399 | Return the property specified by <tt>GraphPropertyTag</tt> that is |
|---|
| 400 | attached to the graph object <tt>g</tt>. The <tt>property_value</tt> |
|---|
| 401 | traits class is defined in <a |
|---|
| 402 | href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. |
|---|
| 403 | |
|---|
| 404 | <hr> |
|---|
| 405 | |
|---|
| 406 | <br> |
|---|
| 407 | <HR> |
|---|
| 408 | <TABLE> |
|---|
| 409 | <TR valign=top> |
|---|
| 410 | <TD nowrap>Copyright © 2000-2001</TD><TD> |
|---|
| 411 | <a HREF="../../../people/dave_abrahams.htm">Dave Abrahams</a> |
|---|
| 412 | (<A HREF="mailto:david.abrahams@rcn.com">david.abrahams@rcn.com</A>)<br> |
|---|
| 413 | <A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, |
|---|
| 414 | Indiana University (<A |
|---|
| 415 | HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> |
|---|
| 416 | </TD></TR></TABLE> |
|---|
| 417 | |
|---|
| 418 | </BODY> |
|---|
| 419 | </HTML> |
|---|
