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