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> 23reverse_graph<<a href="./BidirectionalGraph.html">BidirectionalGraph</a>, GraphReference> 24</pre> 25 26The <tt>reverse_graph</tt> adaptor flips the in-edges and out-edges of 27a <a href="./BidirectionalGraph.html">BidirectionalGraph</a>, 28effectively transposing the graph. The construction of the 29<tt>reverse_graph</tt> is constant time, providing a highly efficient 30way to obtain a transposed view of a graph. 31 32 33<H3>Example</H3> 34 35The example from <a 36href="../example/reverse-graph-eg.cpp"><tt>examples/reverse-graph-eg.cpp</tt></a>. 37 38<pre> 39int 40main() 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> 70The output is: 71<pre> 72original graph: 730 --> 2 741 --> 1 3 4 752 --> 1 3 4 763 --> 1 4 774 --> 0 1 78 79reversed graph: 800 --> 4 811 --> 1 2 3 4 822 --> 0 833 --> 1 2 844 --> 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> 102if 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> 114and optionally 115<a href="./VertexListGraph.html">VertexListGraph</a> 116and <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> 131The 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> 138The 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> 145The 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> 151The 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> 158The 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> 164The 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> 170Provides information about whether the graph is 171directed (<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> 178This describes whether the graph class allows the insertion of 179parallel edges (edges with the same source and target). The two tags 180are <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 183parallel edges while the others allow parallel edges. 184 185<hr> 186 187<tt>graph_traits<reverse_graph>::vertices_size_type</tt> 188<br><br> 189The 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> 195The 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> 201The type used for dealing with the number of edges incident to a vertex 202in the graph. 203 204<hr> 205 206<tt>property_map<reverse_graph, PropertyTag>::type</tt><br> 207and<br> 208<tt>property_map<reverse_graph, PropertyTag>::const_type</tt> 209<br><br> 210The property map type for vertex or edge properties in the graph. The 211specific property is specified by the <TT>PropertyTag</TT> template argument, 212and 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> 219and<br> 220<tt>property_map<reverse_graph, edge_underlying_t>::const_type</tt> 221<br><br> 222An edge property type mapping from edge descriptors in the <tt>reverse_graph</tt> to 223edge descriptors in the underlying <tt>BidirectionalGraph</tt> object. 224 225<hr> 226 227 228<H2>Member Functions</H2> 229 230<hr> 231 232<pre> 233reverse_graph(BidirectionalGraph& g) 234</pre> 235Constructor. 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> 244template <class BidirectionalGraph> 245reverse_graph<BidirectionalGraph, BidirectionalGraph&> 246make_reverse_graph(BidirectionalGraph& g); 247 248template <class BidirectionalGraph> 249reverse_graph<BidirectionalGraph, const BidirectionalGraph&> 250make_reverse_graph(const BidirectionalGraph& g) 251 252</pre> 253Helper function for creating a <tt>reverse_graph</tt>. 254 255<hr> 256 257<pre> 258std::pair<vertex_iterator, vertex_iterator> 259vertices(const reverse_graph& g) 260</pre> 261Returns an iterator-range providing access to the vertex set of graph 262<tt>g</tt>. 263 264<hr> 265 266<pre> 267std::pair<out_edge_iterator, out_edge_iterator> 268out_edges(vertex_descriptor v, const reverse_graph& g) 269</pre> 270Returns 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 272in-edges of the adapted graph. 273 274<hr> 275 276<pre> 277std::pair<in_edge_iterator, in_edge_iterator> 278in_edges(vertex_descriptor v, const reverse_graph& g) 279</pre> 280Returns 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 282out edges of the adapted graph. 283 284<hr> 285 286<pre> 287std::pair<adjacency_iterator, adjacency__iterator> 288adjacent_vertices(vertex_descriptor v, const reverse_graph& g) 289</pre> 290Returns 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> 296vertex_descriptor 297source(edge_descriptor e, const reverse_graph& g) 298</pre> 299Returns the source vertex of edge <tt>e</tt>. 300 301<hr> 302 303<pre> 304vertex_descriptor 305target(edge_descriptor e, const reverse_graph& g) 306</pre> 307Returns the target vertex of edge <tt>e</tt>. 308 309<hr> 310 311<pre> 312degree_size_type 313out_degree(vertex_descriptor u, const reverse_graph& g) 314</pre> 315Returns the number of edges leaving vertex <tt>u</tt>. 316 317<hr> 318 319<pre> 320degree_size_type 321in_degree(vertex_descriptor u, const reverse_graph& g) 322</pre> 323Returns the number of edges entering vertex <tt>u</tt>. This operation 324is only available if <TT>bidirectionalS</TT> was specified for 325the <TT>Directed</TT> template parameter. 326 327<hr> 328 329<pre> 330vertices_size_type 331num_vertices(const reverse_graph& g) 332</pre> 333Returns the number of vertices in the graph <tt>g</tt>. 334 335<hr> 336 337<pre> 338vertex_descriptor 339vertex(vertices_size_type n, const reverse_graph& g) 340</pre> 341Returns the nth vertex in the graph's vertex list. 342 343<hr> 344 345<pre> 346std::pair<edge_descriptor, bool> 347edge(vertex_descriptor u, vertex_descriptor v, 348 const reverse_graph& g) 349</pre> 350Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in 351graph <tt>g</tt>. 352 353<hr> 354 355<pre> 356template <class <a href="./PropertyTag.html">PropertyTag</a>> 357property_map<reverse_graph, PropertyTag>::type 358get(PropertyTag, reverse_graph& g) 359 360template <class <a href="./PropertyTag.html">PropertyTag</a>> 361property_map<reverse_graph, Tag>::const_type 362get(PropertyTag, const reverse_graph& g) 363</pre> 364Returns the property map object for the vertex property specified by 365<TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the 366properties specified in the graph's <TT>VertexProperty</TT> template 367argument. 368 369<hr> 370 371<pre> 372property_map<reverse_graph, edge_underlying_t>::const_type 373get(PropertyTag, const reverse_graph& g) 374</pre> 375Returns 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> 382template <class <a href="./PropertyTag.html">PropertyTag</a>, class X> 383typename property_traits<property_map<reverse_graph, PropertyTag>::const_type>::value_type 384get(PropertyTag, const reverse_graph& g, X x) 385</pre> 386This returns the property value for <tt>x</tt>, which is either 387a vertex or edge descriptor. 388<hr> 389 390<pre> 391typename graph_traits<BidirectionalGraph>::edge_descriptor 392get(edge_underlying_t, const reverse_graph& g, edge_descriptor e) 393</pre> 394This returns the underlying edge descriptor for the edge <tt>e</tt> in the <tt>reverse_graph</tt>. 395<hr> 396 397<pre> 398template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> 399void 400put(PropertyTag, const reverse_graph& g, X x, const Value& value) 401</pre> 402This 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> 410template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 411typename property_value<GraphProperties, GraphPropertyTag>::type& 412get_property(reverse_graph& g, GraphPropertyTag); 413</pre> 414Return the property specified by <tt>GraphPropertyTag</tt> that is 415attached to the graph object <tt>g</tt>. The <tt>property_value</tt> 416traits class is defined in <a 417href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. 418 419<hr> 420 421<pre> 422template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 423const typename property_value<GraphProperties, GraphPropertyTag>::type& 424get_property(const reverse_graph& g, GraphPropertyTag); 425</pre> 426Return the property specified by <tt>GraphPropertyTag</tt> that is 427attached to the graph object <tt>g</tt>. The <tt>property_value</tt> 428traits class is defined in <a 429href="../../../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>, 441Indiana University (<A 442HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 443</TD></TR></TABLE> 444 445</BODY> 446</HTML> 447
