1<HTML> 2<!-- 3 Copyright (c) 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 Concepts</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<H1><A NAME="chapter:graph-concepts"></A> 20Graph Concepts 21</H1> 22 23<P> 24The heart of the Boost Graph Library (BGL) is the interface, or 25concepts (in the parlance of generic programming), that define how a 26graph can be examined and manipulated in a data-structure neutral 27fashion. In fact, the BGL interface need not even be implemented using 28a data-structure, as for some problems it is easier or more efficient 29to define a graph implicitly based on some functions. 30 31<P> 32The BGL interface does not appear as a single graph concept. Instead 33it is factored into much smaller pieces. The reason for this is that 34the purpose of a concept is to summarize the requirements for 35<i>particular</i> algorithms. Any one algorithm does not need every 36kind of graph operation, typically only a small subset. Furthermore, 37there are many graph data-structures that can not provide efficient 38implementations of all the operations, but provide highly efficient 39implementations of the operations necessary for a particular algorithm. 40By factoring the graph interface into many smaller concepts we 41provide the graph algorithm writer with a good selection from which to 42choose the concept that is the closest match for their algorithm. 43 44Note that because of the use of traits classes rather than member 45types, it is not safe (and often will not work) to define subclasses of BGL 46graph types; those types may be missing important traits and properties that 47were defined externally to the class definition. 48 49<H2>Graph Structure Concepts Overview</H2> 50 51<P> 52<A HREF="#fig:graph-concepts">Figure 1</A> shows the refinements 53relations between the graph concepts. The reason for factoring the 54graph interface into so many concepts is to encourage algorithm 55interfaces to require and use only the minimum interface of a graph, 56thereby increasing the reusability of the algorithm. 57 58 59<p></p> 60<DIV ALIGN="CENTER"><A NAME="fig:graph-concepts"></A></A> 61<TABLE> 62<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> 63The graph concepts and refinement relationships. 64</CAPTION> 65<TR><TD><IMG SRC="./figs/concepts.gif"></TD></TR> 66</TABLE> 67</DIV> 68<p></p> 69 70<A HREF="#tab:graph-concept-reqs">Table 1</A> 71gives a summary of the valid expressions and associated types for the 72graph concepts and provides links to the detailed descriptions of 73each of the concepts. The notation used in the table is as follows. 74 75<h3>Notation</h3> 76 77<Table> 78<TR> 79<TD><tt>G</tt></TD> 80<TD>A type that is a model of Graph.</TD> 81</TR> 82 83<TR> 84<TD><tt>g</tt></TD> 85<TD>An object of type <tt>G</tt>.</TD> 86</TR> 87 88<TR> 89<TD><tt>e</tt></TD> 90<TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD> 91</TR> 92 93<TR> 94<TD><tt>e_iter</tt></TD> 95<TD>An object of type <tt>boost::graph_traits<G>::out_edge_iterator</tt>.</TD> 96</TR> 97 98<TR> 99<TD><tt>u,v</tt></TD> 100<TD>Are objects of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD> 101</TR> 102 103<TR> 104<TD><TT>ep</TT></TD><TD>is an object of type <TT>G::edge_property_type</TT></TD> 105</TR> 106 107<TR> 108<TD><TT>vp</TT></TD><TD>is an object of type <TT>G::vertex_property_type</TT></TD> 109</TR> 110 111<TR> 112<TD><tt>Property</tt></TD> 113<TD>A type used to specify a vertex or edge property.</TD> 114</TR> 115 116<TR> 117<TD><tt>property</tt></TD> 118<TD>An object of type <tt>Property</tt>.</td> 119</TR> 120 121</table> 122 123 124 125 126<P> 127<BR><P></P> 128<DIV ALIGN="CENTER"><A NAME="tab:graph-concept-reqs"></A> 129<TABLE> 130<CAPTION ALIGN="BOTTOM"><STRONG>Table 1:</STRONG> 131 Summary of the graph concepts. 132 </CAPTION> 133<TR><TD> 134<TABLE border> 135<TR><TH ALIGN="LEFT"> 136<B>Expression</B> </TH> 137<TH ALIGN="LEFT" VALIGN="TOP"> <B>Return Type or Description</B> </TH> 138</TR> 139<TR><TD ALIGN="LEFT" COLSPAN=2> 140 <a href="./Graph.html">Graph</a> </TD> 141</TR> 142<TR><TD ALIGN="LEFT"> 143<TT>boost::graph_traits<G>::vertex_descriptor</TT> </TD> 144<TD ALIGN="LEFT" VALIGN="TOP"> The type for 145 vertex representative objects. </TD> 146</TR> 147<TR><TD ALIGN="LEFT"> 148<TT>boost::graph_traits<G>::edge_descriptor</TT> </TD> 149<TD ALIGN="LEFT" VALIGN="TOP"> The type for 150 edge representative objects. </TD> 151</TR> 152<TR><TD ALIGN="LEFT"> 153<TT>boost::graph_traits<G>::directed_category</TT> </TD> 154<TD ALIGN="LEFT" VALIGN="TOP"> Directed or undirected? </TD> 155</TR> 156<TR><TD ALIGN="LEFT"> 157<TT>boost::graph_traits<G>::edge_parallel_category</TT> </TD> 158<TD ALIGN="LEFT" VALIGN="TOP"> Allow parallel edges? </TD> 159</TR> 160<TR><TD ALIGN="LEFT"> 161<TT>boost::graph_traits<G>::traversal_category</TT> </TD> <TD 162ALIGN="LEFT" VALIGN="TOP">The ways in which the vertices and edges of 163the graph can be visited.</TD> 164</TR> 165<!----------------------------------------------------------------> 166<TR><TD ALIGN="LEFT" COLSPAN=2> 167 <a href="./IncidenceGraph.html">IncidenceGraph</a> refines Graph </TD> 168</TR> 169<TR><TD ALIGN="LEFT"> 170<TT>boost::graph_traits<G>::out_edge_iterator</TT> </TD> 171<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through 172 the out-edges. </TD> 173</TR> 174<TR><TD ALIGN="LEFT"> 175<TT>boost::graph_traits<G>::degree_size_type</TT> </TD> 176<TD ALIGN="LEFT" VALIGN="TOP"> The integer type for 177vertex degree. </TD> 178</TR> 179<TR><TD ALIGN="LEFT"> 180<TT>out_edges(v, g)</TT> </TD> 181<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<out_edge_iterator, out_edge_iterator></TT> </TD> 182</TR> 183<TR><TD ALIGN="LEFT"> 184<TT>source(e, g)</TT> </TD> 185<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD> 186</TR> 187<TR><TD ALIGN="LEFT"> 188<TT>target(e, g)</TT> </TD> 189<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD> 190</TR> 191<TR><TD ALIGN="LEFT"> 192<TT>out_degree(v, g)</TT> </TD> 193<TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD> 194</TR> 195<!----------------------------------------------------------------> 196<TR><TD ALIGN="LEFT" COLSPAN=2> 197 <a href="./BidirectionalGraph.html">BidirectionalGraph</a> refines 198 IncidenceGraph </TD> 199</TR> 200<TR><TD ALIGN="LEFT"> 201<TT>boost::graph_traits<G>::in_edge_iterator</TT> </TD> 202<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the in-edges. </TD> 203</TR> 204<TR><TD ALIGN="LEFT"> 205<TT>in_edges(v, g)</TT> </TD> 206<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<in_edge_iterator, in_edge_iterator></TT> </TD> 207</TR> 208<TR><TD ALIGN="LEFT"> 209<TT>in_degree(v, g)</TT> </TD> 210<TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD> 211</TR> 212<TR><TD ALIGN="LEFT"> 213<TT>degree(e, g)</TT> </TD> 214<TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD> 215</TR> 216<!----------------------------------------------------------------> 217<TR><TD ALIGN="LEFT" COLSPAN=2> 218<a href="./AdjacencyGraph.html">AdjacencyGraph</a> refines Graph</TD> 219</TR> 220<TR><TD ALIGN="LEFT"> 221<TT>boost::graph_traits<G>::adjacency_iterator</TT> </TD> 222<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through 223 adjacent vertices. </TD> 224</TR> 225<TR><TD ALIGN="LEFT"> 226<TT>adjacent_vertices(v, g)</TT> </TD> 227<TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair<adjacency_iterator, adjacency_iterator></TT> </TD> 228</TR> 229<!----------------------------------------------------------------> 230<TR><TD ALIGN="LEFT" COLSPAN=2> 231<a href="./VertexListGraph.html">VertexListGraph</a> refines 232 Graph</TD> 233</TR> 234<TR><TD ALIGN="LEFT"> 235<TT>boost::graph_traits<G>::vertex_iterator</TT> </TD> 236<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the 237 graph's vertex set. </TD> 238</TR> 239<TR><TD ALIGN="LEFT"> 240<TT>boost::graph_traits<G>::vertices_size_type</TT> </TD> 241<TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for 242number of vertices in the graph. </TD> 243</TR> 244<TR><TD ALIGN="LEFT"> 245<TT>vertices(g)</TT> </TD> 246<TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair<vertex_iterator, vertex_iterator></TT> </TD> 247</TR> 248<TR><TD ALIGN="LEFT"> 249<TT>num_vertices(g)</TT> </TD> 250<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertices_size_type</TT> </TD> 251</TR> 252<!----------------------------------------------------------------> 253<TR><TD ALIGN="LEFT" COLSPAN=2> 254<a href="./EdgeListGraph.html">EdgeListGraph</a> refines Graph</TD> 255</TR> 256<TR><TD ALIGN="LEFT"> 257<TT>boost::graph_traits<G>::edge_iterator</TT> </TD> 258<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the graph's 259 edge set. </TD> 260</TR> 261<TR><TD ALIGN="LEFT"> 262<TT>boost::graph_traits<G>::edges_size_type</TT> </TD> 263<TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for 264number of edges in the graph. </TD> 265</TR> 266<TR><TD ALIGN="LEFT"> 267<TT>edges(g)</TT> </TD> 268<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_iterator, edge_iterator></TT> </TD> 269</TR> 270<TR><TD ALIGN="LEFT"> 271<TT>num_edges(g)</TT> </TD> 272<TD ALIGN="LEFT" VALIGN="TOP"> <TT>edges_size_type</TT> </TD> 273</TR> 274<TR><TD ALIGN="LEFT"> 275<TT>source(e, g)</TT> </TD> 276<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD> 277</TR> 278<TR><TD ALIGN="LEFT"> 279<TT>target(e, g)</TT> </TD> 280<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD> 281</TR> 282<!----------------------------------------------------------------> 283<TR><TD ALIGN="LEFT" COLSPAN=2> 284<a href="./AdjacencyMatrix.html">AdjacencyMatrix</a> refines Graph</TD> 285</TR> 286<TR><TD ALIGN="LEFT"> 287<TT>edge(u, v, g)</TT> </TD> 288<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_descriptor, bool></TT> </TD> 289</TR> 290<TR><TD ALIGN="LEFT" COLSPAN=2> 291<a href="./MutableGraph.html">MutableGraph</a> refines 292 Graph</TD> 293</TR> 294<TR><TD ALIGN="LEFT"> 295<TT>add_vertex(g)</TT> </TD> 296<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD> 297</TR> 298<TR><TD ALIGN="LEFT"> 299<TT>clear_vertex(v, g)</TT> </TD> 300<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD> 301</TR> 302<TR><TD ALIGN="LEFT"> 303<TT>remove_vertex(v, g)</TT> </TD> 304<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD> 305</TR> 306<TR><TD ALIGN="LEFT"> 307<TT>add_edge(u, v, g)</TT> </TD> 308<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_descriptor, bool></TT> </TD> 309</TR> 310<TR><TD ALIGN="LEFT"> 311<TT>remove_edge(u, v, g)</TT> </TD> 312<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD> 313</TR> 314<TR><TD ALIGN="LEFT"> 315<TT>remove_edge(e, g)</TT> </TD> 316<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD> 317</TR> 318<TR><TD ALIGN="LEFT"> 319<TT>remove_edge(e_iter, g)</TT> </TD> 320<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD> 321</TR> 322<!----------------------------------------------------------------> 323<TR><TD ALIGN="LEFT" COLSPAN=2> 324<a href="./MutablePropertyGraph.html">MutablePropertyGraph</a> refines 325 Graph</TD> 326</TR> 327<TR><TD ALIGN="LEFT"> 328<TT>add_vertex(vp, g)</TT> </TD> 329<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD> 330</TR> 331<TR><TD ALIGN="LEFT"> 332<TT>add_edge(u, v, ep, g)</TT> </TD> 333<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_descriptor, 334 bool></TT> </TD> 335</TR> 336<!----------------------------------------------------------------> 337<TR> 338<TD ALIGN="LEFT" COLSPAN=2> 339<a href="./PropertyGraph.html">PropertyGraph</a> refines Graph</TD> 340</TR> 341<TR><TD ALIGN="LEFT"> 342<TT>boost::property_map<G, Property>::type</TT> </TD> 343<TD ALIGN="LEFT" VALIGN="TOP">Type for a mutable property map.</TD> 344</TR> 345<TR><TD ALIGN="LEFT"> 346<TT>boost::property_map<G, Property>::const_type</TT> </TD> 347<TD ALIGN="LEFT" VALIGN="TOP">Type for a non-mutable property map.</TD> 348</TR> 349<TR><TD ALIGN="LEFT"> 350<TT>get(property, g)</TT> </TD> 351<TD ALIGN="LEFT" VALIGN="TOP"> Function to get a property map. </TD> 352</TR> 353 354<TR><TD ALIGN="LEFT"> 355<TT>get(property, g, x)</TT> 356</TD> 357<TD ALIGN="LEFT" VALIGN="TOP">Get property value for vertex or edge <tt>x</tt>. </TD> 358</TR> 359 360<TR><TD ALIGN="LEFT"> 361<TT>put(property, g, x, v)</TT> 362</TD> 363<TD ALIGN="LEFT" VALIGN="TOP">Set property value for vertex or edge 364<tt>x</tt> to <tt>v</tt>. </TD> 365</TR> 366 367</table> 368</table> 369</DIV><P></P> 370<BR> 371 372<P> 373 374<H2><A NAME="sec:undirected-graphs"></A> 375Undirected Graphs 376</H2> 377 378<P> 379The interface that the BGL provides for accessing and manipulating an 380undirected graph is the same as the interface for directed graphs 381described in the following sections, however there are some 382differences in the behaviour and semantics. For example, in a 383directed graph we can talk about out-edges and in-edges of a vertex. 384In an undirected graph there is no ``in'' and ``out'', there are just 385edges incident to a vertex. Nevertheless, in the BGL we still use the 386<TT>out_edges()</TT> function (or <TT>in_edges()</TT>) to access the 387incident edges in an undirected graph. Similarly, an undirected edge 388has no ``source'' and ``target'' but merely an unordered pair of 389vertices, but in the BGL we still use <TT>source()</TT> and 390<TT>target()</TT> to access these vertices. The reason the BGL does 391not provide a separate interface for undirected graphs is that many 392algorithms on directed graphs also work on undirected graphs, and it 393would be inconvenient to have to duplicate the algorithms just because 394of an interface difference. When using undirected graphs just mentally 395disregard the directionality in the function names. The example below 396demonstrates using the <TT>out_edges()</TT>, <TT>source()</TT>, and 397<TT>target()</TT> with an undirected graph. The source code for this 398example and the following one can be found in <a 399href="../example/undirected_adjacency_list.cpp"><TT>example/undirected_adjacency_list.cpp</TT></a>. 400 401<P> 402<PRE> 403 const int V = 2; 404 typedef ... UndirectedGraph; 405 UndirectedGraph undigraph(V); 406 407 std::cout << "the edges incident to v: "; 408 boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end; 409 boost::graph_traits<UndirectedGraph>::vertex_descriptor 410 s = vertex(0, undigraph); 411 for (boost::tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e) 412 std::cout << "(" << source(*e, undigraph) 413 << "," << target(*e, undigraph) << ")" << endl; 414</PRE> 415 416<P> 417Even though the interface is the same for undirected graphs, there are 418some behavioral differences because edge equality is defined 419differently. In a directed graph, edge <i>(u,v)</i> is never equal to edge 420<i>(v,u)</i>, but in an undirected graph they may be equal. If the 421undirected graph is a multigraph then <i>(u,v)</i> and <i>(v,u)</i> might be 422parallel edges. If the graph is not a multigraph then <i>(u,v)</i> and 423<i>(v,u)</i> must be the same edge. 424 425<P> 426In the example below the edge equality test will return <TT>false</TT> 427for the directed graph and <TT>true</TT> for the undirected graph. The 428difference also affects the meaning of <TT>add_edge()</TT>. In the 429example below, if we had also written <TT>add_edge(v, u, 430undigraph)</TT>, this would have added a parallel edge between 431<i>u</i> and <i>v</i> (provided the graph type allows parallel 432edges). The difference in edge equality also affects the association 433of edge properties. In the directed graph, the edges <i>(u,v)</i> and 434<i>(v,u)</i> can have distinct weight values, whereas in the 435undirected graph the weight of <i>(u,v)</i> is the same as the weight 436of <i>(v,u)</i> since they are the same edge. 437 438<P> 439<PRE> 440 typedef ... DirectedGraph; 441 DirectedGraph digraph(V); 442 { 443 boost::graph_traits<DirectedGraph>::vertex_descriptor u, v; 444 u = vertex(0, digraph); 445 v = vertex(1, digraph); 446 add_edge(digraph, u, v, Weight(1.2)); 447 add_edge(digraph, v, u, Weight(2.4)); 448 boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2; 449 bool found; 450 boost::tie(e1, found) = edge(u, v, digraph); 451 boost::tie(e2, found) = edge(v, u, digraph); 452 std::cout << "in a directed graph is "; 453 std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl; 454 455 property_map<DirectedGraph, edge_weight_t>::type 456 weight = get(edge_weight, digraph); 457 cout << "weight[(u,v)] = " << get(weight, e1) << endl; 458 cout << "weight[(v,u)] = " << get(weight, e2) << endl; 459 } 460 { 461 boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v; 462 u = vertex(0, undigraph); 463 v = vertex(1, undigraph); 464 add_edge(undigraph, u, v, Weight(3.1)); 465 boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2; 466 bool found; 467 boost::tie(e1, found) = edge(u, v, undigraph); 468 boost::tie(e2, found) = edge(v, u, undigraph); 469 std::cout << "in an undirected graph is "; 470 std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl; 471 472 property_map<UndirectedGraph, edge_weight_t>::type 473 weight = get(edge_weight, undigraph); 474 cout << "weight[(u,v)] = " << get(weight, e1) << endl; 475 cout << "weight[(v,u)] = " << get(weight, e2) << endl; 476 } 477</PRE> 478The output is: 479<PRE> 480in a directed graph is (u,v) == (v,u) ? 0 481weight[(u,v)] = 1.2 482weight[(v,u)] = 2.4 483in an undirected graph is (u,v) == (v,u) ? 1 484weight[(u,v)] = 3.1 485weight[(v,u)] = 3.1 486</PRE> 487 488 489<br> 490<HR> 491<TABLE> 492<TR valign=top> 493<TD nowrap>Copyright © 2000-2001</TD><TD> 494<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) 495</TD></TR></TABLE> 496 497</BODY> 498</HTML> 499
