ceph/src/boost/libs/graph/doc/reverse_graph.html

   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&lt;<a href="./BidirectionalGraph.html">BidirectionalGraph</a>, GraphReference&gt;
  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&lt;
  43     boost::vecS, boost::vecS, boost::bidirectionalS,
  44   &gt; 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 &lt;&lt; &quot;original graph:&quot; &lt;&lt; std::endl;
  60   boost::print_graph(G, boost::get(boost::vertex_index, G));
  61
  62   std::cout &lt;&lt; std::endl &lt;&lt; &quot;reversed graph:&quot; &lt;&lt; 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 --&gt; 2
  74 1 --&gt; 1 3 4
  75 2 --&gt; 1 3 4
  76 3 --&gt; 1 4
  77 4 --&gt; 0 1
  78
  79 reversed graph:
  80 0 --&gt; 4
  81 1 --&gt; 1 2 3 4
  82 2 --&gt; 0
  83 3 --&gt; 1 2
  84 4 --&gt; 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>&nbsp;</TD>
  98 </TR>
  99
 100 <TR><TD><TT>GraphReference</TT></TD>
 101 <TD>This type should be <tt>const&nbsp;BidirectionalGraph&amp;</tt>
 102 if you want to create a const reverse graph, or <tt>BidirectionalGraph&amp;</tt> if you want to create a non-const reverse graph.</TD>
 103 <TD><tt>const&nbsp;BidirectionalGraph&amp;</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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph&gt;::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&lt;reverse_graph, PropertyTag&gt;::type</tt><br>
 207 and<br>
 208 <tt>property_map&lt;reverse_graph, PropertyTag&gt;::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&lt;reverse_graph, edge_underlying_t&gt;::type</tt><br>
 219 and<br>
 220 <tt>property_map&lt;reverse_graph, edge_underlying_t&gt;::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&amp;&nbsp;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 &lt;class BidirectionalGraph&gt;
 245 reverse_graph&lt;BidirectionalGraph, BidirectionalGraph&amp;&gt;
 246 make_reverse_graph(BidirectionalGraph&amp; g);
 247
 248 template &lt;class BidirectionalGraph&gt;
 249 reverse_graph&lt;BidirectionalGraph, const BidirectionalGraph&amp;&gt;
 250 make_reverse_graph(const BidirectionalGraph&amp; g)
 251
 252 </pre>
 253 Helper function for creating a <tt>reverse_graph</tt>.
 254
 255 <hr>
 256
 257 <pre>
 258 std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
 259 vertices(const reverse_graph&amp; 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&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
 268 out_edges(vertex_descriptor&nbsp;v, const&nbsp;reverse_graph&amp;&nbsp;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&lt;in_edge_iterator,&nbsp;in_edge_iterator&gt;
 278 in_edges(vertex_descriptor&nbsp;v, const&nbsp;reverse_graph&amp;&nbsp;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&lt;adjacency_iterator,&nbsp;adjacency__iterator&gt;
 288 adjacent_vertices(vertex_descriptor&nbsp;v, const&nbsp;reverse_graph&amp;&nbsp;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&nbsp;e, const&nbsp;reverse_graph&amp;&nbsp;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&nbsp;e, const&nbsp;reverse_graph&amp;&nbsp;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&nbsp;u, const&nbsp;reverse_graph&amp;&nbsp;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&nbsp;u, const&nbsp;reverse_graph&amp;&nbsp;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&amp; 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&nbsp;n, const&nbsp;reverse_graph&amp;&nbsp;g)
 340 </pre>
 341 Returns the nth vertex in the graph's vertex list.
 342
 343 <hr>
 344
 345 <pre>
 346 std::pair&lt;edge_descriptor, bool&gt;
 347 edge(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
 348      const&nbsp;reverse_graph&amp;&nbsp;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 &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 357 property_map&lt;reverse_graph, PropertyTag&gt;::type
 358 get(PropertyTag, reverse_graph&amp; g)
 359
 360 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 361 property_map&lt;reverse_graph, Tag&gt;::const_type
 362 get(PropertyTag, const reverse_graph&amp; 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&lt;reverse_graph, edge_underlying_t&gt;::const_type
 373 get(PropertyTag, const reverse_graph&amp; 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 &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X&gt;
 383 typename property_traits&lt;property_map&lt;reverse_graph, PropertyTag&gt;::const_type&gt;::value_type
 384 get(PropertyTag, const reverse_graph&amp; 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&lt;BidirectionalGraph&gt;::edge_descriptor
 392 get(edge_underlying_t, const reverse_graph&amp; 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 &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value&gt;
 399 void
 400 put(PropertyTag, const reverse_graph&amp; g, X x, const Value&amp; 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&lt;property_map&lt;reverse_graph, PropertyTag&gt;::type&gt::value_type</tt>
 406
 407 <hr>
 408
 409 <pre>
 410 template &lt;class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>&gt;
 411 typename property_value&lt;GraphProperties, GraphPropertyTag&gt;::type&amp;
 412 get_property(reverse_graph&amp; 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 &lt;class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>&gt;
 423 const typename property_value&lt;GraphProperties, GraphPropertyTag&gt;::type&amp;
 424 get_property(const reverse_graph&amp; 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 &copy; 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>