ceph/src/boost/libs/graph/doc/predecessor_recorder.html

   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&lt;PredecessorMap, EventTag&gt;
  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>&nbsp;</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>&nbsp;</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 &lt;class Edge, class Graph&gt;<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 &lt;class PredecessorMap, class Tag&gt;<br>
 153 predecessor_recorder&lt;PredecessorMap, Tag&gt; <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 &copy; 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  -->