projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <HTML> |
| 2 | <!-- | |
| 3 | (C) Copyright David Abrahams and Jeremy Siek 2000. | |
| 4 | ||
| 5 | Distributed under the Boost Software License, Version 1.0. | |
| 6 | (See accompanying file LICENSE_1_0.txt or copy at | |
| 7 | http://www.boost.org/LICENSE_1_0.txt) | |
| 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>::edges_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 | <tt>property_map<reverse_graph, edge_underlying_t>::type</tt><br> | |
| 219 | and<br> | |
| 220 | <tt>property_map<reverse_graph, edge_underlying_t>::const_type</tt> | |
| 221 | <br><br> | |
| 222 | An edge property type mapping from edge descriptors in the <tt>reverse_graph</tt> to | |
| 223 | edge descriptors in the underlying <tt>BidirectionalGraph</tt> object. | |
| 224 | ||
| 225 | <hr> | |
| 226 | ||
| 227 | ||
| 228 | <H2>Member Functions</H2> | |
| 229 | ||
| 230 | <hr> | |
| 231 | ||
| 232 | <pre> | |
| 233 | reverse_graph(BidirectionalGraph& g) | |
| 234 | </pre> | |
| 235 | Constructor. Create a reversed (transposed) view of the graph <tt>g</tt>. | |
| 236 | ||
| 237 | <hr> | |
| 238 | ||
| 239 | <H2>Non-Member Functions</H2> | |
| 240 | ||
| 241 | <hr> | |
| 242 | ||
| 243 | <pre> | |
| 244 | template <class BidirectionalGraph> | |
| 245 | reverse_graph<BidirectionalGraph, BidirectionalGraph&> | |
| 246 | make_reverse_graph(BidirectionalGraph& g); | |
| 247 | ||
| 248 | template <class BidirectionalGraph> | |
| 249 | reverse_graph<BidirectionalGraph, const BidirectionalGraph&> | |
| 250 | make_reverse_graph(const BidirectionalGraph& g) | |
| 251 | ||
| 252 | </pre> | |
| 253 | Helper function for creating a <tt>reverse_graph</tt>. | |
| 254 | ||
| 255 | <hr> | |
| 256 | ||
| 257 | <pre> | |
| 258 | std::pair<vertex_iterator, vertex_iterator> | |
| 259 | vertices(const reverse_graph& g) | |
| 260 | </pre> | |
| 261 | Returns an iterator-range providing access to the vertex set of graph | |
| 262 | <tt>g</tt>. | |
| 263 | ||
| 264 | <hr> | |
| 265 | ||
| 266 | <pre> | |
| 267 | std::pair<out_edge_iterator, out_edge_iterator> | |
| 268 | out_edges(vertex_descriptor v, const reverse_graph& g) | |
| 269 | </pre> | |
| 270 | Returns an iterator-range providing access to the out-edges of vertex | |
| 271 | <tt>v</tt> in graph <tt>g</tt>. These out-edges correspond to the | |
| 272 | in-edges of the adapted graph. | |
| 273 | ||
| 274 | <hr> | |
| 275 | ||
| 276 | <pre> | |
| 277 | std::pair<in_edge_iterator, in_edge_iterator> | |
| 278 | in_edges(vertex_descriptor v, const reverse_graph& g) | |
| 279 | </pre> | |
| 280 | Returns an iterator-range providing access to the in-edges of vertex | |
| 281 | <tt>v</tt> in graph <tt>g</tt>. These in-edges correspond to the | |
| 282 | out edges of the adapted graph. | |
| 283 | ||
| 284 | <hr> | |
| 285 | ||
| 286 | <pre> | |
| 287 | std::pair<adjacency_iterator, adjacency__iterator> | |
| 288 | adjacent_vertices(vertex_descriptor v, const reverse_graph& g) | |
| 289 | </pre> | |
| 290 | Returns an iterator-range providing access to the adjacent vertices of vertex | |
| 291 | <tt>v</tt> in graph <tt>g</tt>. | |
| 292 | ||
| 293 | <hr> | |
| 294 | ||
| 295 | <pre> | |
| 296 | vertex_descriptor | |
| 297 | source(edge_descriptor e, const reverse_graph& g) | |
| 298 | </pre> | |
| 299 | Returns the source vertex of edge <tt>e</tt>. | |
| 300 | ||
| 301 | <hr> | |
| 302 | ||
| 303 | <pre> | |
| 304 | vertex_descriptor | |
| 305 | target(edge_descriptor e, const reverse_graph& g) | |
| 306 | </pre> | |
| 307 | Returns the target vertex of edge <tt>e</tt>. | |
| 308 | ||
| 309 | <hr> | |
| 310 | ||
| 311 | <pre> | |
| 312 | degree_size_type | |
| 313 | out_degree(vertex_descriptor u, const reverse_graph& g) | |
| 314 | </pre> | |
| 315 | Returns the number of edges leaving vertex <tt>u</tt>. | |
| 316 | ||
| 317 | <hr> | |
| 318 | ||
| 319 | <pre> | |
| 320 | degree_size_type | |
| 321 | in_degree(vertex_descriptor u, const reverse_graph& g) | |
| 322 | </pre> | |
| 323 | Returns the number of edges entering vertex <tt>u</tt>. This operation | |
| 324 | is only available if <TT>bidirectionalS</TT> was specified for | |
| 325 | the <TT>Directed</TT> template parameter. | |
| 326 | ||
| 327 | <hr> | |
| 328 | ||
| 329 | <pre> | |
| 330 | vertices_size_type | |
| 331 | num_vertices(const reverse_graph& g) | |
| 332 | </pre> | |
| 333 | Returns the number of vertices in the graph <tt>g</tt>. | |
| 334 | ||
| 335 | <hr> | |
| 336 | ||
| 337 | <pre> | |
| 338 | vertex_descriptor | |
| 339 | vertex(vertices_size_type n, const reverse_graph& g) | |
| 340 | </pre> | |
| 341 | Returns the nth vertex in the graph's vertex list. | |
| 342 | ||
| 343 | <hr> | |
| 344 | ||
| 345 | <pre> | |
| 346 | std::pair<edge_descriptor, bool> | |
| 347 | edge(vertex_descriptor u, vertex_descriptor v, | |
| 348 | const reverse_graph& g) | |
| 349 | </pre> | |
| 350 | Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in | |
| 351 | graph <tt>g</tt>. | |
| 352 | ||
| 353 | <hr> | |
| 354 | ||
| 355 | <pre> | |
| 356 | template <class <a href="./PropertyTag.html">PropertyTag</a>> | |
| 357 | property_map<reverse_graph, PropertyTag>::type | |
| 358 | get(PropertyTag, reverse_graph& g) | |
| 359 | ||
| 360 | template <class <a href="./PropertyTag.html">PropertyTag</a>> | |
| 361 | property_map<reverse_graph, Tag>::const_type | |
| 362 | get(PropertyTag, const reverse_graph& g) | |
| 363 | </pre> | |
| 364 | Returns the property map object for the vertex property specified by | |
| 365 | <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the | |
| 366 | properties specified in the graph's <TT>VertexProperty</TT> template | |
| 367 | argument. | |
| 368 | ||
| 369 | <hr> | |
| 370 | ||
| 371 | <pre> | |
| 372 | property_map<reverse_graph, edge_underlying_t>::const_type | |
| 373 | get(PropertyTag, const reverse_graph& g) | |
| 374 | </pre> | |
| 375 | Returns a property map object that converts from edge descriptors in the | |
| 376 | <tt>reverse_graph</tt> to edge descriptors in the underlying | |
| 377 | <tt>BidirectionalGraph</tt> object. | |
| 378 | ||
| 379 | <hr> | |
| 380 | ||
| 381 | <pre> | |
| 382 | template <class <a href="./PropertyTag.html">PropertyTag</a>, class X> | |
| 383 | typename property_traits<property_map<reverse_graph, PropertyTag>::const_type>::value_type | |
| 384 | get(PropertyTag, const reverse_graph& g, X x) | |
| 385 | </pre> | |
| 386 | This returns the property value for <tt>x</tt>, which is either | |
| 387 | a vertex or edge descriptor. | |
| 388 | <hr> | |
| 389 | ||
| 390 | <pre> | |
| 391 | typename graph_traits<BidirectionalGraph>::edge_descriptor | |
| 392 | get(edge_underlying_t, const reverse_graph& g, edge_descriptor e) | |
| 393 | </pre> | |
| 394 | This returns the underlying edge descriptor for the edge <tt>e</tt> in the <tt>reverse_graph</tt>. | |
| 395 | <hr> | |
| 396 | ||
| 397 | <pre> | |
| 398 | template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> | |
| 399 | void | |
| 400 | put(PropertyTag, const reverse_graph& g, X x, const Value& value) | |
| 401 | </pre> | |
| 402 | This sets the property value for <tt>x</tt> to | |
| 403 | <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor. | |
| 404 | <tt>Value</tt> must be convertible to | |
| 405 | <tt>typename property_traits<property_map<reverse_graph, PropertyTag>::type>::value_type</tt> | |
| 406 | ||
| 407 | <hr> | |
| 408 | ||
| 409 | <pre> | |
| 410 | template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> | |
| 411 | typename property_value<GraphProperties, GraphPropertyTag>::type& | |
| 412 | get_property(reverse_graph& g, GraphPropertyTag); | |
| 413 | </pre> | |
| 414 | Return the property specified by <tt>GraphPropertyTag</tt> that is | |
| 415 | attached to the graph object <tt>g</tt>. The <tt>property_value</tt> | |
| 416 | traits class is defined in <a | |
| 417 | href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. | |
| 418 | ||
| 419 | <hr> | |
| 420 | ||
| 421 | <pre> | |
| 422 | template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> | |
| 423 | const typename property_value<GraphProperties, GraphPropertyTag>::type& | |
| 424 | get_property(const reverse_graph& g, GraphPropertyTag); | |
| 425 | </pre> | |
| 426 | Return the property specified by <tt>GraphPropertyTag</tt> that is | |
| 427 | attached to the graph object <tt>g</tt>. The <tt>property_value</tt> | |
| 428 | traits class is defined in <a | |
| 429 | href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. | |
| 430 | ||
| 431 | <hr> | |
| 432 | ||
| 433 | <br> | |
| 434 | <HR> | |
| 435 | <TABLE> | |
| 436 | <TR valign=top> | |
| 437 | <TD nowrap>Copyright © 2000-2001</TD><TD> | |
| 438 | <a HREF="http://www.boost.org/people/dave_abrahams.htm">Dave Abrahams</a> | |
| 439 | (<A HREF="mailto:david.abrahams@rcn.com">david.abrahams@rcn.com</A>)<br> | |
| 440 | <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, | |
| 441 | Indiana University (<A | |
| 442 | HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> | |
| 443 | </TD></TR></TABLE> | |
| 444 | ||
| 445 | </BODY> | |
| 446 | </HTML> |