← Back to branch summary

~ubuntu-branches/debian/sid/boost1.49/sid

« back to all changes in this revision

Viewing changes to libs/graph/doc/graph_concepts.html

  • Committer: Package Import Robot
  • Author(s): Steve M. Robbins
  • Date: 2012-02-26 00:31:44 UTC
  • Revision ID: package-import@ubuntu.com-20120226003144-eaytp12cbf6ubpms
Tags: upstream-1.49.0
Import upstream version 1.49.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
libs/graph/doc/graph_concepts.html
 
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>
 
20
Graph Concepts
 
21
</H1>
 
22
 
 
23
<P>
 
24
The heart of the Boost Graph Library (BGL) is the interface, or
 
25
concepts (in the parlance of generic programming), that define how a
 
26
graph can be examined and manipulated in a data-structure neutral
 
27
fashion. In fact, the BGL interface need not even be implemented using
 
28
a data-structure, as for some problems it is easier or more efficient
 
29
to define a graph implicitly based on some functions.
 
30
 
 
31
<P>
 
32
The BGL interface does not appear as a single graph concept.  Instead
 
33
it is factored into much smaller pieces. The reason for this is that
 
34
the purpose of a concept is to summarize the requirements for
 
35
<i>particular</i> algorithms. Any one algorithm does not need every
 
36
kind of graph operation, typically only a small subset.  Furthermore,
 
37
there are many graph data-structures that can not provide efficient
 
38
implementations of all the operations, but provide highly efficient
 
39
implementations of the operations necessary for a particular algorithm.
 
40
By factoring the graph interface into many smaller concepts we
 
41
provide the graph algorithm writer with a good selection from which to
 
42
choose the concept that is the closest match for their algorithm.
 
43
 
 
44
Note that because of the use of traits classes rather than member
 
45
types, it is not safe (and often will not work) to define subclasses of BGL
 
46
graph types; those types may be missing important traits and properties that
 
47
were 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
 
53
relations between the graph concepts. The reason for factoring the
 
54
graph interface into so many concepts is to encourage algorithm
 
55
interfaces to require and use only the minimum interface of a graph,
 
56
thereby 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>
 
63
The 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&nbsp;1</A>
 
71
gives a summary of the valid expressions and associated types for the
 
72
graph concepts and provides links to the detailed descriptions of
 
73
each 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&lt;G&gt;::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&lt;G&gt;::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&lt;G&gt;::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&lt;G&gt;::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&lt;G&gt;::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&lt;G&gt;::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&lt;G&gt;::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&lt;G&gt;::traversal_category</TT> </TD> <TD
 
162
ALIGN="LEFT" VALIGN="TOP">The ways in which the vertices and edges of
 
163
the 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&lt;G&gt;::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&lt;G&gt;::degree_size_type</TT> </TD>
 
176
<TD ALIGN="LEFT" VALIGN="TOP"> The integer type for
 
177
vertex degee. </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&lt;out_edge_iterator, out_edge_iterator&gt;</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&lt;G&gt;::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&lt;in_edge_iterator, in_edge_iterator&gt;</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&lt;G&gt;::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&lt;adjacency_iterator, adjacency_iterator&gt;</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&lt;G&gt;::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&lt;G&gt;::vertices_size_type</TT> </TD>
 
241
<TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
 
242
number 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&lt;vertex_iterator, vertex_iterator&gt;</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&lt;G&gt;::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&lt;G&gt;::edges_size_type</TT> </TD>
 
263
<TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
 
264
number 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&lt;edge_iterator, edge_iterator&gt;</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&lt;edge_descriptor, bool&gt;</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&lt;edge_descriptor, bool&gt;</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&lt;edge_descriptor,
 
334
  bool&gt;</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&lt;G, Property&gt;::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&lt;G, Property&gt;::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,&nbsp;g,&nbsp;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,&nbsp;g,&nbsp;x,&nbsp;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>
 
375
Undirected Graphs
 
376
</H2>
 
377
 
 
378
<P>
 
379
The interface that the BGL provides for accessing and manipulating an
 
380
undirected graph is the same as the interface for directed graphs
 
381
described in the following sections, however there are some
 
382
differences in the behaviour and semantics.  For example, in a
 
383
directed graph we can talk about out-edges and in-edges of a vertex.
 
384
In an undirected graph there is no ``in'' and ``out'', there are just
 
385
edges 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
 
387
incident edges in an undirected graph. Similarly, an undirected edge
 
388
has no ``source'' and ``target'' but merely an unordered pair of
 
389
vertices, but in the BGL we still use <TT>source()</TT> and
 
390
<TT>target()</TT> to access these vertices.  The reason the BGL does
 
391
not provide a separate interface for undirected graphs is that many
 
392
algorithms on directed graphs also work on undirected graphs, and it
 
393
would be inconvenient to have to duplicate the algorithms just because
 
394
of an interface difference. When using undirected graphs just mentally
 
395
disregard the directionality in the function names. The example below
 
396
demonstrates using the <TT>out_edges()</TT>, <TT>source()</TT>, and
 
397
<TT>target()</TT> with an undirected graph. The source code for this
 
398
example and the following one can be found in <a
 
399
href="../example/undirected.cpp"><TT>examples/undirected.cpp</TT></a>.
 
400
 
 
401
<P>
 
402
<PRE>
 
403
  const int V = 2;
 
404
  typedef ... UndirectedGraph;
 
405
  UndirectedGraph undigraph(V);
 
406
 
 
407
  std::cout &lt;&lt; "the edges incident to v: ";
 
408
  boost::graph_traits&lt;UndirectedGraph&gt;::out_edge_iterator e, e_end;
 
409
  boost::graph_traits&lt;UndirectedGraph&gt;::vertex_descriptor 
 
410
    s = vertex(0, undigraph);
 
411
  for (tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
 
412
    std::cout &lt;&lt; "(" &lt;&lt; source(*e, undigraph) 
 
413
              &lt;&lt; "," &lt;&lt; target(*e, undigraph) &lt;&lt; ")" &lt;&lt; endl;
 
414
</PRE>
 
415
 
 
416
<P>
 
417
Even though the interface is the same for undirected graphs, there are
 
418
some behavioral differences because edge equality is defined
 
419
differently. 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
 
421
undirected graph is a multigraph then <i>(u,v)</i> and <i>(v,u)</i> might be
 
422
parallel 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>
 
426
In the example below the edge equality test will return <TT>false</TT>
 
427
for the directed graph and <TT>true</TT> for the undirected graph. The
 
428
difference also affects the meaning of <TT>add_edge()</TT>. In the
 
429
example below, if we had also written <TT>add_edge(v, u,
 
430
undigraph)</TT>, this would have added a parallel edge between
 
431
<i>u</i> and <i>v</i> (provided the graph type allows parallel
 
432
edges). The difference in edge equality also affects the association
 
433
of 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
 
435
undirected graph the weight of <i>(u,v)</i> is the same as the weight
 
436
of <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&lt;DirectedGraph&gt;::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&lt;DirectedGraph&gt;::edge_descriptor e1, e2;
 
449
    bool found;
 
450
    tie(e1, found) = edge(u, v, digraph);
 
451
    tie(e2, found) = edge(v, u, digraph);
 
452
    std::cout &lt;&lt; "in a directed graph is ";
 
453
    std::cout &lt;&lt; "(u,v) == (v,u) ? " &lt;&lt; (e1 == e2) &lt;&lt; std::endl;
 
454
 
 
455
    property_map&lt;DirectedGraph, edge_weight_t&gt;::type
 
456
      weight = get(edge_weight, digraph);
 
457
    cout &lt;&lt; "weight[(u,v)] = " &lt;&lt; get(weight, e1) &lt;&lt; endl;
 
458
    cout &lt;&lt; "weight[(v,u)] = " &lt;&lt; get(weight, e2) &lt;&lt; endl;
 
459
  }
 
460
  {
 
461
    boost::graph_traits&lt;UndirectedGraph&gt;::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&lt;UndirectedGraph&gt;::edge_descriptor e1, e2;
 
466
    bool found;
 
467
    tie(e1, found) = edge(u, v, undigraph);
 
468
    tie(e2, found) = edge(v, u, undigraph);
 
469
    std::cout &lt;&lt; "in an undirected graph is ";
 
470
    std::cout &lt;&lt; "(u,v) == (v,u) ? " &lt;&lt; (e1 == e2) &lt;&lt; std::endl;
 
471
 
 
472
    property_map&lt;UndirectedGraph, edge_weight_t&gt;::type
 
473
      weight = get(edge_weight, undigraph);
 
474
    cout &lt;&lt; "weight[(u,v)] = " &lt;&lt; get(weight, e1) &lt;&lt; endl;
 
475
    cout &lt;&lt; "weight[(v,u)] = " &lt;&lt; get(weight, e2) &lt;&lt; endl;
 
476
  }
 
477
</PRE>
 
478
The output is:
 
479
<PRE>
 
480
in a directed graph is (u,v) == (v,u) ? 0
 
481
weight[(u,v)] = 1.2
 
482
weight[(v,u)] = 2.4
 
483
in an undirected graph is (u,v) == (v,u) ? 1
 
484
weight[(u,v)] = 3.1
 
485
weight[(v,u)] = 3.1
 
486
</PRE>
 
487
 
 
488
 
 
489
<br>
 
490
<HR>
 
491
<TABLE>
 
492
<TR valign=top>
 
493
<TD nowrap>Copyright &copy; 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>