[ceph.git] / ceph / src / boost / libs / graph / doc / 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: 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>
predecessor_recorder&lt;PredecessorMap, EventTag&gt;
</pre>
</H1>

This is an <a href="./EventVisitor.html">EventVisitor</a> that records
the predecessor (or parent) of a vertex in a predecessor 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 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.

<p>
<tt>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 to the source vertex (which is the root of the search
tree). It is often useful to initialize the source vertex's
predecessor to itself, thereby identifying the root vertex as the only
vertex which is its own parent. When using an algorithm like
depth-first search that creates a forest (multiple search trees) it
is useful to initialize the predecessor of every vertex to itself. 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>PredecessorMap</TT></TD>
<TD>
A <a
href="../../property_map/doc/WritablePropertyMap.html">WritablePropertyMap</a>
where the key type and the value type are the vertex descriptor type
of the graph.
</TD>
<TD>&nbsp;</TD>
</TR>

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