]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <HTML> |
2 | <!-- | |
3 | Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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: Edge List Class</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="sec:edge-list-class"></A> | |
20 | <PRE> | |
21 | edge_list<EdgeIterator, ValueType, DiffType> | |
22 | </PRE> | |
23 | </H1> | |
24 | ||
25 | <P> | |
26 | The <TT>edge_list</TT> class is an adaptor that turns a pair of edge | |
27 | iterators into a class that models <TT>EdgeListGraph</TT>. The | |
28 | <TT>value_type</TT> of the edge iterator must be a <TT>std::pair</TT> (or | |
29 | at least have <TT>first</TT> and <TT>second</TT> members). The | |
30 | <TT>first_type</TT> and <TT>second_type</TT> of the pair must be the | |
31 | same and they will be used for the graph's <TT>vertex_descriptor</TT>. | |
32 | The <TT>ValueType</TT> and <TT>DiffType</TT> template parameters are only | |
33 | needed if your compiler does not support partial | |
34 | specialization. Otherwise they default to the correct types. | |
35 | ||
36 | <P> | |
37 | ||
38 | <H3>Example</H3> | |
39 | ||
40 | <P> | |
41 | Applying the Bellman-Ford shortest paths algorithm to an | |
42 | <TT>edge_list</TT>. | |
43 | ||
44 | <P> | |
45 | <PRE> | |
46 | enum { u, v, x, y, z, N }; | |
47 | char name[] = { 'u', 'v', 'x', 'y', 'z' }; | |
48 | ||
49 | typedef std::pair<int,int> E; | |
50 | E edges[] = { E(u,y), E(u,x), E(u,v), | |
51 | E(v,u), | |
52 | E(x,y), E(x,v), | |
53 | E(y,v), E(y,z), | |
54 | E(z,u), E(z,x) }; | |
55 | ||
56 | int weight[] = { -4, 8, 5, | |
57 | -2, | |
58 | 9, -3, | |
59 | 7, 2, | |
60 | 6, 7 }; | |
61 | ||
62 | typedef boost::edge_list<E*> Graph; | |
63 | Graph g(edges, edges + sizeof(edges) / sizeof(E)); | |
64 | ||
65 | std::vector<int> distance(N, std::numeric_limits<short>::max()); | |
66 | std::vector<int> parent(N,-1); | |
67 | ||
68 | distance[z] = 0; | |
69 | parent[z] = z; | |
70 | bool r = boost::bellman_ford_shortest_paths(g, int(N), weight, | |
71 | distance.begin(), | |
72 | parent.begin()); | |
73 | if (r) | |
74 | for (int i = 0; i < N; ++i) | |
75 | std::cout << name[i] << ": " << distance[i] | |
76 | << " " << name[parent[i]] << std::endl; | |
77 | else | |
78 | std::cout << "negative cycle" << std::endl; | |
79 | </PRE> | |
80 | The output is the distance from the root and the parent | |
81 | of each vertex in the shortest paths tree. | |
82 | <PRE> | |
83 | u: 2 v | |
84 | v: 4 x | |
85 | x: 7 z | |
86 | y: -2 u | |
87 | z: 0 z | |
88 | </PRE> | |
89 | ||
90 | <P> | |
91 | <p> | |
92 | ||
93 | <H3>Where Defined</H3> | |
94 | ||
95 | <a href="../../../boost/graph/edge_list.hpp"><TT>boost/graph/edge_list.hpp</TT></a> | |
96 | ||
97 | <P> | |
98 | <H3>Template Parameters</H3> | |
99 | ||
100 | <P> | |
101 | <TABLE border> | |
102 | <TR> | |
103 | <th>Parameter</th><th>Description</th> | |
104 | </tr> | |
105 | ||
106 | <TR><TD><TT>EdgeIterator</TT></TD> <TD>Must be model of <a | |
107 | href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a> | |
108 | who's <TT>value_type</TT> must be a pair of vertex descriptors.</TD> | |
109 | </TR> | |
110 | ||
111 | <TR><TD><TT>ValueType</TT></TD> | |
112 | <TD>The <TT>value_type</TT> of the <TT>EdgeIterator</TT>.<br> | |
113 | Default: <TT>std::iterator_traits<EdgeIterator>::value_type</TT></TD> | |
114 | </TR> | |
115 | ||
116 | <TR><TD><TT>DiffType</TT></TD> | |
117 | <TD>The <TT>difference_type</TT> of the <TT>EdgeIterator</TT>.<br> | |
118 | Default: <TT>std::iterator_traits<EdgeIterator>::difference_type</TT></TD> | |
119 | </TR> | |
120 | ||
121 | </TABLE> | |
122 | <P> | |
123 | ||
124 | <H3>Model of</H3> | |
125 | ||
126 | <a href="./EdgeListGraph.html">EdgeListGraph</a> | |
127 | ||
128 | <P> | |
129 | ||
130 | ||
131 | <H3>Associated Types</H3> | |
132 | ||
133 | <hr> | |
134 | ||
135 | <tt>boost::graph_traits<edge_list>::vertex_descriptor</tt> | |
136 | <br><br> | |
137 | The type for the vertex descriptors associated with the | |
138 | <TT>edge_list</TT>. This will be the same type as | |
139 | <TT>std::iterator_traits<EdgeIterator>::value_type::first_type</TT>. | |
140 | ||
141 | <hr> | |
142 | ||
143 | <tt> | |
144 | boost::graph_traits<edge_list>::edge_descriptor | |
145 | </tt> | |
146 | <br><br> | |
147 | The type for the edge descriptors associated with the | |
148 | <TT>edge_list</TT>. | |
149 | ||
150 | <hr> | |
151 | ||
152 | <tt> | |
153 | boost::graph_traits<edge_list>::edge_iterator | |
154 | </tt> | |
155 | <br><br> | |
156 | The type for the iterators returned by <TT>edges()</TT>. The iterator | |
157 | category of the <TT>edge_iterator</TT> will be the same as that of the | |
158 | <TT>EdgeIterator</TT>. | |
159 | ||
160 | <hr> | |
161 | ||
162 | <h3>Member Functions</h3> | |
163 | ||
164 | <hr> | |
165 | ||
166 | <tt> | |
167 | edge_list(EdgeIterator first, EdgeIterator last) | |
168 | </tt> | |
169 | <br><br> | |
170 | Creates a graph object with <TT>n</TT> vertices and with the | |
171 | edges specified in the edge list given by the range <TT>[first,last)</TT>. | |
172 | ||
173 | <hr> | |
174 | ||
175 | <H3>Non-Member Functions</H3> | |
176 | ||
177 | <hr> | |
178 | ||
179 | <tt> | |
180 | std::pair<edge_iterator, edge_iterator><br> | |
181 | edges(const edge_list& g) | |
182 | </tt> | |
183 | <br><br> | |
184 | Returns an iterator-range providing access to the edge set of graph <TT>g</TT>. | |
185 | ||
186 | <hr> | |
187 | ||
188 | <tt> | |
189 | vertex_descriptor<br> | |
190 | source(edge_descriptor e, const edge_list& g) | |
191 | </tt> | |
192 | <br><br> | |
193 | Returns the source vertex of edge <TT>e</TT>. | |
194 | ||
195 | <hr> | |
196 | ||
197 | <tt> | |
198 | vertex_descriptor<br> | |
199 | target(edge_descriptor e, const edge_list& g) | |
200 | </tt> | |
201 | <br><br> | |
202 | Returns the target vertex of edge <TT>e</TT>. | |
203 | ||
204 | <hr> | |
205 | ||
206 | <br> | |
207 | <HR> | |
208 | <TABLE> | |
209 | <TR valign=top> | |
210 | <TD nowrap>Copyright © 2000-2001</TD><TD> | |
211 | <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, | |
212 | Indiana University (<A | |
213 | HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> | |
214 | <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br> | |
215 | <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, | |
216 | Indiana University (<A | |
217 | HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) | |
218 | </TD></TR></TABLE> | |
219 | ||
220 | </BODY> | |
221 | </HTML> |