Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/graph_concepts.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

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