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

<HTML>
<!--
     Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
    
     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: edge_predecessor_recorder</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>
<pre>
edge_predecessor_recorder&lt;PredEdgeMap, EventTag&gt;
</pre>
</H1>

This is an <a href="./EventVisitor.html">EventVisitor</a> that records
the predecessor (or parent) edge of a vertex in a property
map. This is particularly useful in graph search algorithms where
recording the predecessors is an efficient way to encode the search
tree that was traversed during the search. The edge predecessor recorder is
typically used with the <tt>on_tree_edge</tt> or
<tt>on_relax_edge</tt> events and cannot be used with vertex events.  This
visitor is meant to be used instead of <a
href="predecessor_recorder.html"><tt>predecessor_recorder</tt></a> when a
graph has parallel edges and it is necessary to know which incoming edge a
search algorithm
used to get to a particular vertex.

<p>
<tt>edge_predecessor_recorder</tt> can be used with graph algorithms by
wrapping it with an algorithm-specific adaptor, such as <a
href="./bfs_visitor.html"><tt>bfs_visitor</tt></a> and <a
href="./dfs_visitor.html"><tt>dfs_visitor</tt></a>. Also, this event
visitor can be combined with other event visitors using
<tt>std::pair</tt> to form an EventVisitorList.

<p>
Algorithms such as Dijkstra's and breadth-first search will not assign
a predecessor edge to the source vertex (which is the root of the search
tree). It is often useful to initialize the source vertex's
predecessor to a special value, thereby identifying the root vertex.
When using an algorithm like
depth-first search that creates a forest (multiple search trees) it
is useful to do the same for every vertex. This
way all the root nodes can be distinguished.


<!-- <h3>Example</h3>

See the example for <a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>.
-->

<h3>Model of</h3>

<a href="./EventVisitor.html">EventVisitor</a>


<H3>Where Defined</H3>

<P>
<a href="../../../boost/graph/visitors.hpp">
<TT>boost/graph/visitors.hpp</TT></a>

<H3>Template Parameters</H3>

<P>
<TABLE border>
<TR>
<th>Parameter</th><th>Description</th><th>Default</th>
</tr>

<TR><TD><TT>PredEdgeMap</TT></TD>
<TD>
A <a
href="../../property_map/doc/WritablePropertyMap.html">WritablePropertyMap</a>
where the key and value types are the vertex and edge descriptor types, respectively, of the graph.
</TD>
<TD>&nbsp;</TD>
</TR>

<TR><TD><TT>EventTag</TT></TD>
<TD>
The tag to specify when the <tt>edge_predecessor_recorder</tt> should be
applied during the graph algorithm. <tt>EventTag</tt> must be an
edge event.
</TD>
<TD>&nbsp;</TD>
</TR>

</table>

<H2>Associated Types</H2>

<table border>

<tr>
<th>Type</th><th>Description</th>
</tr>

<tr>
<td><tt>edge_predecessor_recorder::event_filter</tt></td>
<td>
This will be the same type as the template parameter <tt>EventTag</tt>.
</td>
</tr>

</table>

<h3>Member Functions</h3>

<p>

<table border>
<tr>
<th>Member</th><th>Description</th>
</tr>

<tr>
<td><tt>
edge_predecessor_recorder(PredEdgeMap pa);
</tt></td>
<td>
Construct an edge predecessor recorder object with predecessor property map
<tt>pa</tt>.
</td>
</tr>

<tr>
<td><tt>
template &lt;class Edge, class Graph&gt;<br>
void operator()(Edge e, const Graph& g);
</tt></td>
<td>
Given edge <i>e = (u,v)</i>, this records <i>e</i> as the
predecessor (or parent) edge of <i>v</i>.
</td>
</tr>

</table>

<h3>Non-Member Functions</h3>

<table border>
<tr>
<th>Function</th><th>Description</th>
</tr>

<tr><td><tt>
template &lt;class PredEdgeMap, class Tag&gt;<br>
edge_predecessor_recorder&lt;PredEdgeMap, Tag&gt; <br>
record_edge_predecessors(PredEdgeMap pa, Tag);
</tt></td><td>
A convenient way to create a <tt>edge_predecessor_recorder</tt>.
</td></tr>

</table>

<h3>See Also</h3>

<a href="./visitor_concepts.html">Visitor concepts</a>
<p>
The following are other event visitors: <a
<a href="./distance_recorder.html"><tt>distance_recorder</tt></a>,
<a href="./time_stamper.html"><tt>time_stamper</tt></a>,
and <a href="./property_writer.html"><tt>property_writer</tt></a>.


<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2000-2001</TD><TD>
<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>)<br>
<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>
<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> 
<!--  LocalWords:  PredEdgeMap EventTag EventVisitor map bfs dfs const
 -->
<!--  LocalWords:  EventVisitorList WritablePropertyMap Siek Univ Quan
 -->
<!--  LocalWords:  Lumsdaine
 -->
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_predecessor_recorder</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>
	19	<pre>
	20	edge_predecessor_recorder<PredEdgeMap, EventTag>
	21	</pre>
	22	</H1>
	23
	24	This is an <a href="./EventVisitor.html">EventVisitor</a> that records
	25	the predecessor (or parent) edge of a vertex in a property
	26	map. This is particularly useful in graph search algorithms where
	27	recording the predecessors is an efficient way to encode the search
	28	tree that was traversed during the search. The edge predecessor recorder is
	29	typically used with the <tt>on_tree_edge</tt> or
	30	<tt>on_relax_edge</tt> events and cannot be used with vertex events. This
	31	visitor is meant to be used instead of <a
	32	href="predecessor_recorder.html"><tt>predecessor_recorder</tt></a> when a
	33	graph has parallel edges and it is necessary to know which incoming edge a
	34	search algorithm
	35	used to get to a particular vertex.
	36
	37	<p>
	38	<tt>edge_predecessor_recorder</tt> can be used with graph algorithms by
	39	wrapping it with an algorithm-specific adaptor, such as <a
	40	href="./bfs_visitor.html"><tt>bfs_visitor</tt></a> and <a
	41	href="./dfs_visitor.html"><tt>dfs_visitor</tt></a>. Also, this event
	42	visitor can be combined with other event visitors using
	43	<tt>std::pair</tt> to form an EventVisitorList.
	44
	45	<p>
	46	Algorithms such as Dijkstra's and breadth-first search will not assign
	47	a predecessor edge to the source vertex (which is the root of the search
	48	tree). It is often useful to initialize the source vertex's
	49	predecessor to a special value, thereby identifying the root vertex.
	50	When using an algorithm like
	51	depth-first search that creates a forest (multiple search trees) it
	52	is useful to do the same for every vertex. This
	53	way all the root nodes can be distinguished.
	54
	55
	56	<!-- <h3>Example</h3>
	57
	58	See the example for <a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>.
	59	-->
	60
	61	<h3>Model of</h3>
	62
	63	<a href="./EventVisitor.html">EventVisitor</a>
	64
65
66	<H3>Where Defined</H3>
67
68	<P>
69	<a href="../../../boost/graph/visitors.hpp">
70	<TT>boost/graph/visitors.hpp</TT></a>
71
72	<H3>Template Parameters</H3>
73
74	<P>
75	<TABLE border>
76	<TR>
77	<th>Parameter</th><th>Description</th><th>Default</th>
78	</tr>
79
80	<TR><TD><TT>PredEdgeMap</TT></TD>
81	<TD>
82	A <a
83	href="../../property_map/doc/WritablePropertyMap.html">WritablePropertyMap</a>
84	where the key and value types are the vertex and edge descriptor types, respectively, of the graph.
85	</TD>
86	<TD> </TD>
87	</TR>
88
89	<TR><TD><TT>EventTag</TT></TD>
90	<TD>
91	The tag to specify when the <tt>edge_predecessor_recorder</tt> should be
92	applied during the graph algorithm. <tt>EventTag</tt> must be an
93	edge event.
94	</TD>
95	<TD> </TD>
96	</TR>
97
98	</table>
99
100	<H2>Associated Types</H2>
101
102	<table border>
103
104	<tr>
105	<th>Type</th><th>Description</th>
106	</tr>
107
108	<tr>
109	<td><tt>edge_predecessor_recorder::event_filter</tt></td>
110	<td>
111	This will be the same type as the template parameter <tt>EventTag</tt>.
112	</td>
113	</tr>
114
115	</table>
116
117	<h3>Member Functions</h3>
118
119	<p>
120
121	<table border>
122	<tr>
123	<th>Member</th><th>Description</th>
124	</tr>
125
126	<tr>
127	<td><tt>
128	edge_predecessor_recorder(PredEdgeMap pa);
129	</tt></td>
130	<td>
131	Construct an edge predecessor recorder object with predecessor property map
132	<tt>pa</tt>.
133	</td>
134	</tr>
135
136	<tr>
137	<td><tt>
138	template <class Edge, class Graph><br>
139	void operator()(Edge e, const Graph& g);
140	</tt></td>
141	<td>
142	Given edge <i>e = (u,v)</i>, this records <i>e</i> as the
143	predecessor (or parent) edge of <i>v</i>.
144	</td>
145	</tr>
146
147	</table>
148
149	<h3>Non-Member Functions</h3>
150
151	<table border>
152	<tr>
153	<th>Function</th><th>Description</th>
154	</tr>
155
156	<tr><td><tt>
157	template <class PredEdgeMap, class Tag><br>
158	edge_predecessor_recorder<PredEdgeMap, Tag> <br>
159	record_edge_predecessors(PredEdgeMap pa, Tag);
160	</tt></td><td>
161	A convenient way to create a <tt>edge_predecessor_recorder</tt>.
162	</td></tr>
163
164	</table>
165
166	<h3>See Also</h3>
167
168	<a href="./visitor_concepts.html">Visitor concepts</a>
169	<p>
170	The following are other event visitors: <a
171	<a href="./distance_recorder.html"><tt>distance_recorder</tt></a>,
172	<a href="./time_stamper.html"><tt>time_stamper</tt></a>,
173	and <a href="./property_writer.html"><tt>property_writer</tt></a>.
174
175
176	<br>
177	<HR>
178	<TABLE>
179	<TR valign=top>
180	<TD nowrap>Copyright © 2000-2001</TD><TD>
181	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
182	Indiana University (<A
183	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
184	<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>
185	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
186	Indiana University (<A
187	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
188	</TD></TR></TABLE>
189
190	</BODY>
191	</HTML>
192	<!-- LocalWords: PredEdgeMap EventTag EventVisitor map bfs dfs const
193	-->
194	<!-- LocalWords: EventVisitorList WritablePropertyMap Siek Univ Quan
195	-->
196	<!-- LocalWords: Lumsdaine
197	-->