[ceph.git] / ceph / src / boost / libs / graph / doc / AStarVisitor.html

<HTML>
<!--
     Copyright (c) 2004 Kris Beevers
    
     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 Library: AStarVisitor</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>AStar Visitor Concept</H1>

This concept defines the visitor interface for <a
href="./astar_search.html"><tt>astar_search()</tt></a>.  Users can
define a class with the AStar Visitor interface and pass an object of
the class to <tt>astar_search()</tt>, thereby augmenting the actions
taken during the graph 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 AStar 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>const G&amp;</tt>.</TD>
</TR>

<TR>
<TD><tt>e</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
</TR>

<TR>
<TD><tt>s,u,v</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</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/doc/ReadablePropertyMap.html">Readable Property
Map</a>.</TD>
</TR>

<TR>
<TD><tt>w</tt></TD>
<TD>An object of type <tt>WeightMap</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 on each vertex of the graph when it is first
initialized (i.e., when its property maps are initialized).
</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 first discovered and is added to the
OPEN list.
</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 (i.e., it
has the lowest cost on the OPEN list). 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
examined.
</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 (the distance of its target vertex is reduced) and this method
is invoked:
<blockquote>
<pre>
tie(u, s) = incident(e, g);
D d_u = get(d, u), d_v = get(d, s);
W w_e = get(w, e);
assert(compare(combine(d_u, w_e), d_s));
</pre>
</blockquote>
</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 an edge is not relaxed (see above) then this
method is invoked.
</td>
</tr>

<tr>
<td>Black Target</td>
<td><tt>vis.black_target(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked when a vertex that is on the CLOSED list is
``rediscovered'' via a more efficient path and is re-added to the
OPEN list.
</td>
</tr>

<tr>
<td>Finish Vertex</td>
<td><tt>vis.finish_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on a vertex when it is added to the CLOSED list. This
happens after all of its out-edges have been examined.
</td>
</tr>

</table>

<h3>Models</h3>

<ul>
 <li><a href="./astar_visitor.html"><tt>astar_visitor</tt></a>
</ul>


<h3>See also</h3>

<a href="./visitor_concepts.html">Visitor concepts</a>

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2004</TD><TD>
<A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
Rensselaer Polytechnic Institute (<A
HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	1	<HTML>
	2	<!--
	3	Copyright (c) 2004 Kris Beevers
	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: AStarVisitor</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>AStar Visitor Concept</H1>
	19
	20	This concept defines the visitor interface for <a
	21	href="./astar_search.html"><tt>astar_search()</tt></a>. Users can
	22	define a class with the AStar Visitor interface and pass an object of
	23	the class to <tt>astar_search()</tt>, thereby augmenting the actions
	24	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
	32	<h3>Notation</h3>
	33
	34	<Table>
	35	<TR>
	36	<TD><tt>V</tt></TD>
	37	<TD>A type that is a model of AStar Visitor.</TD>
	38	</TR>
	39
	40	<TR>
	41	<TD><tt>vis</tt></TD>
	42	<TD>An object of type <tt>V</tt>.</TD>
	43	</TR>
	44
	45	<TR>
	46	<TD><tt>G</tt></TD>
	47	<TD>A type that is a model of Graph.</TD>
	48	</TR>
	49
	50	<TR>
	51	<TD><tt>g</tt></TD>
	52	<TD>An object of type <tt>const G&</tt>.</TD>
	53	</TR>
	54
	55	<TR>
	56	<TD><tt>e</tt></TD>
	57	<TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
	58	</TR>
	59
	60	<TR>
	61	<TD><tt>s,u,v</tt></TD>
	62	<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
	63	</TR>
	64
65	<TR>
66	<TD><tt>d</tt></TD>
67	<TD>An object of type <tt>DistanceMap</tt>.</TD>
68	</TR>
69
70	<TR>
71	<TD><tt>WeightMap</tt></TD>
72	<TD>A type that is a model of <a
73	href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
74	Map</a>.</TD>
75	</TR>
76
77	<TR>
78	<TD><tt>w</tt></TD>
79	<TD>An object of type <tt>WeightMap</tt>.</TD>
80	</TR>
81
82	</table>
83
84	<h3>Associated Types</h3>
85
86	none
87	<p>
88
89	<h3>Valid Expressions</h3>
90
91	<table border>
92	<tr>
93	<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
94	</tr>
95
96	<tr>
97	<td>Initialize Vertex</td>
98	<td><tt>vis.initialize_vertex(u, g)</tt></td>
99	<td><tt>void</tt></td>
100	<td>
101	This is invoked on each vertex of the graph when it is first
102	initialized (i.e., when its property maps are initialized).
103	</td>
104	</tr>
105
106	<tr>
107	<td>Discover Vertex</td>
108	<td><tt>vis.discover_vertex(u, g)</tt></td>
109	<td><tt>void</tt></td>
110	<td>
111	This is invoked when a vertex is first discovered and is added to the
112	OPEN list.
113	</td>
114	</tr>
115
116	<tr>
117	<td>Examine Vertex</td>
118	<td><tt>vis.examine_vertex(u, g)</tt></td>
119	<td><tt>void</tt></td>
120	<td>
121	This is invoked on a vertex as it is popped from the queue (i.e., it
122	has the lowest cost on the OPEN list). This happens immediately before
123	<tt>examine_edge()</tt> is invoked on each of the out-edges of vertex
124	<tt>u</tt>.
125	</td>
126	</tr>
127
128	<tr>
129	<td>Examine Edge</td>
130	<td><tt>vis.examine_edge(e, g)</tt></td>
131	<td><tt>void</tt></td>
132	<td>
133	This is invoked on every out-edge of each vertex after it is
134	examined.
135	</td>
136	</tr>
137
138
139	<tr>
140	<td>Edge Relaxed</td>
141	<td><tt>vis.edge_relaxed(e, g)</tt></td>
142	<td><tt>void</tt></td>
143	<td>
144	Upon examination, if the following condition holds then the edge is
145	relaxed (the distance of its target vertex is reduced) and this method
146	is invoked:
147	<blockquote>
148	<pre>
149	tie(u, s) = incident(e, g);
150	D d_u = get(d, u), d_v = get(d, s);
151	W w_e = get(w, e);
152	assert(compare(combine(d_u, w_e), d_s));
153	</pre>
154	</blockquote>
155	</td>
156	</tr>
157
158	<tr>
159	<td>Edge Not Relaxed</td>
160	<td><tt>vis.edge_not_relaxed(e, g)</tt></td>
161	<td><tt>void</tt></td>
162	<td>
163	Upon examination, if an edge is not relaxed (see above) then this
164	method is invoked.
165	</td>
166	</tr>
167
168	<tr>
169	<td>Black Target</td>
170	<td><tt>vis.black_target(e, g)</tt></td>
171	<td><tt>void</tt></td>
172	<td>
173	This is invoked when a vertex that is on the CLOSED list is
174	``rediscovered'' via a more efficient path and is re-added to the
175	OPEN list.
176	</td>
177	</tr>
178
179	<tr>
180	<td>Finish Vertex</td>
181	<td><tt>vis.finish_vertex(u, g)</tt></td>
182	<td><tt>void</tt></td>
183	<td>
184	This is invoked on a vertex when it is added to the CLOSED list. This
185	happens after all of its out-edges have been examined.
186	</td>
187	</tr>
188
189	</table>
190
191	<h3>Models</h3>
192
193	<ul>
194	<li><a href="./astar_visitor.html"><tt>astar_visitor</tt></a>
195	</ul>
196
197
198	<h3>See also</h3>
199
200	<a href="./visitor_concepts.html">Visitor concepts</a>
201
202	<br>
203	<HR>
204	<TABLE>
205	<TR valign=top>
206	<TD nowrap>Copyright © 2004</TD><TD>
207	<A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
208	Rensselaer Polytechnic Institute (<A
209	HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
210	</TD></TR></TABLE>
211
212	</BODY>
213	</HTML>