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
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. We make no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>Boost Graph Library: Dijkstra Visitor</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><img src="figs/python.gif" alt="(Python)"/>Dijkstra Visitor Concept</H1>
This concept defines the visitor interface for <a
href="./dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>
and related algorithms. The user can create a class that matches this
interface, and then pass objects of the class into
<tt>dijkstra_shortest_paths()</tt> to augment the actions taken during
the search.
<h3>Refinement of</h3>
<a href="../../utility/CopyConstructible.html">Copy Constructible</a>
(copying a visitor should be a lightweight operation).
<h3>Notation</h3>
<Table>
<TR>
<TD><tt>V</tt></TD>
<TD>A type that is a model of Dijkstra Visitor.</TD>
</TR>
<TR>
<TD><tt>vis</tt></TD>
<TD>An object of type <tt>V</tt>.</TD>
</TR>
<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>s,u,v</tt></TD>
<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
</TR>
<TR>
<TD><tt>DistanceMap</tt></TD>
<TD>A type that is a model of <a href="../../property_map/ReadWritePropertyMap.html">Read/Write Property Map</a>.</TD>
</TR>
<TR>
<TD><tt>d</tt></TD>
<TD>An object of type <tt>DistanceMap</tt>.</TD>
</TR>
<TR>
<TD><tt>WeightMap</tt></TD>
<TD>A type that is a model of <a href="../../property_map/ReadWritePropertyMap.html">Readable Property Map</a>.</TD>
</TR>
<TR>
<TD><tt>w</tt></TD>
<TD>An object of type <tt>DistanceMap</tt>.</TD>
</TR>
</table>
<h3>Associated Types</h3>
none
<p>
<h3>Valid Expressions</h3>
<table border>
<tr>
<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
</tr>
<tr>
<td>Initialize Vertex</td>
<td><tt>vis.initialize_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked one each vertex of the graph when it is initialized.
</td>
</tr>
<tr>
<td>Examine Vertex</td>
<td><tt>vis.examine_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on a vertex as it is popped from the queue. This
happens immediately before <tt>examine_edge()</tt> is invoked
on each of the out-edges of vertex <tt>u</tt>.
</td>
</tr>
<tr>
<td>Examine Edge</td>
<td><tt>vis.examine_edge(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on every out-edge of each vertex after it is discovered.
</td>
</tr>
<tr>
<td>Discover Vertex</td>
<td><tt>vis.discover_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked when a vertex is encountered for the first time.
</td>
</tr>
<tr>
<td>Edge Relaxed</td>
<td><tt>vis.edge_relaxed(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
Upon examination, if the following condition holds then the edge
is relaxed (its distance is reduced), and this method is invoked.<br>
<tt>
tie(u,v) = incident(e, g);<br>
D d_u = get(d, u), d_v = get(d, v);<br>
W w_e = get(w, e);<br>
assert(compare(combine(d_u, w_e), d_v));<br>
</tt>
</td>
</tr>
<tr>
<td>Edge Not Relaxed</td>
<td><tt>vis.edge_not_relaxed(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
Upon examination, if the edge is not relaxed (see above) then
this method is invoked.
</td>
</tr>
<tr>
<td>Finish Vertex</td>
<td><tt>vis.finish_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This invoked on a vertex after all of its out edges have been added to the
search tree and all of the adjacent vertices have been discovered
(but before their out-edges have been examined).
</td>
</tr>
</table>
<h3>Models</h3>
<ul>
<li><a href="./dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>
</ul>
<a name="python"></a>
<h3>Python</h3>
To implement a model of the <tt>DijkstraVisitor</tt> concept in Python,
create a new class that derives from the <tt>DijkstraVisitor</tt> type of
the graph, which will be
named <tt><i>GraphType</i>.DijkstraVisitor</tt>. The events and syntax are
the same as with visitors in C++. Here is an example for the
Python <tt>bgl.Graph</tt> graph type:
<pre>
class count_tree_edges_dijkstra_visitor(bgl.Graph.DijkstraVisitor):
def __init__(self, name_map):
bgl.Graph.DijkstraVisitor.__init__(self)
self.name_map = name_map
def edge_relaxed(self, e, g):
(u, v) = (g.source(e), g.target(e))
print "Relaxed edge ",
print self.name_map[u],
print " -> ",
print self.name_map[v]
</pre>
<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000-2001</TD><TD>
<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
Indiana University (<A
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>
</BODY>
</HTML>
|
