ceph/src/boost/libs/graph/doc/edge_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: 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&lt;PredEdgeMap, EventTag&gt;
  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>&nbsp;</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>&nbsp;</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 &lt;class Edge, class Graph&gt;<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 &lt;class PredEdgeMap, class Tag&gt;<br>
 158 edge_predecessor_recorder&lt;PredEdgeMap, Tag&gt; <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 &copy; 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  -->