Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/BellmanFordVisitor.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: 4.5 KB
Line 
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: Bellman Ford Visitor</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<H1><img src="figs/python.gif" alt="(Python)"/>Bellman Ford Visitor Concept</H1>
19
20This concept defines the visitor interface for <a
21href="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths()</tt></a>.
22Users can define a class with the Bellman Ford Visitor interface and
23pass and object of the class to <tt>bellman_ford_shortest_paths()</tt>,
24thereby augmenting the actions taken during the graph search.
25
26<h3>Refinement of</h3>
27
28<a href="../../utility/CopyConstructible.html">Copy Constructible</a>
29(copying a visitor should be a lightweight operation).
30
31<h3>Notation</h3>
32
33<Table>
34<TR>
35<TD><tt>V</tt></TD>
36<TD>A type that is a model of Bellman Ford Visitor.</TD>
37</TR>
38
39<TR>
40<TD><tt>vis</tt></TD>
41<TD>An object of type <tt>V</tt>.</TD>
42</TR>
43
44<TR>
45<TD><tt>G</tt></TD>
46<TD>A type that is a model of Graph.</TD>
47</TR>
48
49<TR>
50<TD><tt>g</tt></TD>
51<TD>An object of type <tt>G</tt>.</TD>
52</TR>
53
54<TR>
55<TD><tt>e</tt></TD>
56<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
57</TR>
58
59<TR>
60<TD><tt>s,u</tt></TD>
61<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
62</TR>
63
64</table>
65
66<h3>Associated Types</h3>
67
68none
69<p>
70
71<h3>Valid Expressions</h3>
72
73<table border>
74<tr>
75<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
76</tr>
77
78<tr>
79<td>Examine Edge</td>
80<td><tt>vis.examine_edge(e, g)</tt></td>
81<td><tt>void</tt></td>
82<td>
83This is invoked on every edge in the graph <tt>num_vertices(g)</tt> times.
84</td>
85</tr>
86
87
88<tr>
89<td>Edge Relaxed</td>
90<td><tt>vis.edge_relaxed(e, g)</tt></td>
91<td><tt>void</tt></td>
92<td>
93Upon examination, if the following condition holds then the edge
94is relaxed (its distance is reduced), and this method is invoked.<br>
95<tt>
96tie(u,v) = incident(e, g);<br>
97D d_u = get(d, u), d_v = get(d, v);<br>
98W w_e = get(w, e);<br>
99assert(compare(combine(d_u, w_e), d_v));<br>
100</tt>
101</td>
102</tr>
103
104<tr>
105<td>Edge Not Relaxed</td>
106<td><tt>edge_not_relaxed(e, g)</tt></td>
107<td><tt>void</tt></td>
108<td>
109Upon examination, if the edge is not relaxed (see above) then
110this method is invoked.
111</td>
112</tr>
113
114<tr>
115<td>Edge Minimized</td>
116<td><tt>vis.edge_minimized(e, g)</tt></td>
117<td><tt>void</tt></td>
118<td>
119After the <tt>num_vertices(g)</tt> iterations through the edge set
120of the graph is complete, one last iteration is made to test whether
121each edge was minimized. If the edge is minimized then this function
122is invoked.
123</td>
124</tr>
125
126<tr>
127<td>Edge Not Minimized</td>
128<td><tt>edge_not_minimized(e, g)</tt></td>
129<td><tt>void</tt></td>
130<td>
131If the edge is not minimized, this function is invoked. This happens
132when there is a negative cycle in the graph.
133</td>
134</tr>
135
136</table>
137
138
139<h3>Models</h3>
140
141<ul>
142  <li><a href="./bellman_visitor.html"><tt>bellman_visitor</tt></a>
143</ul>
144
145<a name="python"></a>
146<h3>Python</h3>
147
148To implement a model of the <tt>BellmanFordVisitor</tt> concept in Python,
149create a new class that derives from the <tt>BellmanFordVisitor</tt> type of
150the graph, which will be
151named <tt><i>GraphType</i>.BellmanFordVisitor</tt>. The events and syntax are
152the same as with visitors in C++. Here is an example for the
153Python <tt>bgl.Graph</tt> graph type:
154
155<pre>
156class count_tree_edges_bellman_ford_visitor(bgl.Graph.BellmanFordVisitor):
157  def __init__(self, name_map):
158    bgl.Graph.BellmanFordVisitor.__init__(self)
159    self.name_map = name_map
160
161  def edge_relaxed(self, e, g):
162    (u, v) = (g.source(e), g.target(e))
163    print "Relaxed edge ",
164    print self.name_map[u],
165    print " -> ",
166    print self.name_map[v]
167</pre>
168
169<br>
170<HR>
171<TABLE>
172<TR valign=top>
173<TD nowrap>Copyright &copy 2000-2001</TD><TD>
174<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
175Indiana University (<A
176HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
177<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>
178<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
179Indiana University (<A
180HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
181</TD></TR></TABLE>
182
183</BODY>
184</HTML> 
Note: See TracBrowser for help on using the repository browser.