ceph/src/boost/libs/graph/doc/BFSVisitor.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: BFSVisitor</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><img src="figs/python.gif" alt="(Python)"/>BFS Visitor Concept</H1>
  19
  20 This concept defines the visitor interface for <a
  21 href="./breadth_first_search.html"><tt>breadth_first_search()</tt></a>.
  22 Users can define a class with the BFS Visitor interface and pass and
  23 object of the class to <tt>breadth_first_search()</tt>, thereby
  24 augmenting the actions 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 BFS 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>G</tt>.</TD>
  53 </TR>
  54
  55 <TR>
  56 <TD><tt>e</tt></TD>
  57 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
  58 </TR>
  59
  60 <TR>
  61 <TD><tt>s,u</tt></TD>
  62 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
  63 </TR>
  64
  65 </table>
  66
  67 <h3>Associated Types</h3>
  68
  69 none
  70 <p>
  71
  72 <h3>Valid Expressions</h3>
  73
  74 <table border>
  75 <tr>
  76 <th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
  77 </tr>
  78
  79 <tr>
  80 <td>Initialize Vertex</td>
  81 <td><tt>vis.initialize_vertex(s, g)</tt></td>
  82 <td><tt>void</tt></td>
  83 <td>
  84 This is invoked on every vertex of the graph before the start of the
  85 graph search.
  86 </td>
  87 </tr>
  88
  89 <tr>
  90 <td>Discover Vertex</td>
  91 <td><tt>vis.discover_vertex(u, g)</tt></td>
  92 <td><tt>void</tt></td>
  93 <td>
  94 This is invoked when a vertex is encountered for the first time.
  95 </td>
  96 </tr>
  97
  98 <tr>
  99 <td>Examine Vertex</td>
 100 <td><tt>vis.examine_vertex(u, g)</tt></td>
 101 <td><tt>void</tt></td>
 102 <td>
 103 This is invoked on a vertex as it is popped from the queue. This
 104 happens immediately before <tt>examine_edge()</tt> is invoked
 105 on each of the out-edges of vertex <tt>u</tt>.
 106 </td>
 107 </tr>
 108
 109 <tr>
 110 <td>Examine Edge</td>
 111 <td><tt>vis.examine_edge(e, g)</tt></td>
 112 <td><tt>void</tt></td>
 113 <td>
 114 This is invoked on every out-edge of each vertex after it is discovered.
 115 </td>
 116 </tr>
 117
 118
 119 <tr>
 120 <td>Tree Edge</td>
 121 <td><tt>vis.tree_edge(e, g)</tt></td>
 122 <td><tt>void</tt></td>
 123 <td>
 124 This is invoked on each edge as it becomes a member of the edges that
 125 form the search tree.</td>
 126 </tr>
 127
 128 <tr>
 129 <td>Non-Tree Edge</td>
 130 <td><tt>vis.non_tree_edge(e, g)</tt></td>
 131 <td><tt>void</tt></td>
 132 <td>
 133 This is invoked on back or cross edges for directed graphs and cross
 134 edges for undirected graphs.
 135 </td>
 136 </tr>
 137
 138 <tr>
 139 <td>Gray Target</td>
 140 <td><tt>vis.gray_target(e, g)</tt></td>
 141 <td><tt>void</tt></td>
 142 <td>
 143 This is invoked on the subset of non-tree edges whose target vertex is
 144 colored gray at the time of examination. The color gray indicates
 145 that the vertex is currently in the queue.
 146 </td>
 147 </tr>
 148
 149 <tr>
 150 <td>Black Target</td>
 151 <td><tt>vis.black_target(e, g)</tt></td>
 152 <td><tt>void</tt></td>
 153 <td>
 154 This is invoked on the subset of non-tree edges whose target vertex is
 155 colored black at the time of examination. The color black indicates
 156 that the vertex has been removed from the queue.
 157 </td>
 158 </tr>
 159
 160 <tr>
 161 <td>Finish Vertex</td>
 162 <td><tt>vis.finish_vertex(u, g)</tt></td>
 163 <td><tt>void</tt></td>
 164 <td>
 165 This invoked on a vertex after all of its out edges have been added to the
 166 search tree and all of the adjacent vertices have been discovered
 167 (but before the out-edges of the adjacent vertices have been examined).
 168 </td>
 169 </tr>
 170
 171 </table>
 172
 173 <h3>Models</h3>
 174
 175 <ul>
 176  <li><a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>
 177 </ul>
 178
 179 <a name="python"></a><h3>Python</h3>
 180 To implement a model of the <tt>BFSVisitor</tt> concept in Python,
 181 create a new class that derives from the <tt>BFSVisitor</tt> type of
 182 the graph, which will be
 183 named <tt><i>GraphType</i>.BFSVisitor</tt>. The events and syntax are
 184 the same as with visitors in C++. Here is an example for the
 185 Python <tt>bgl.Graph</tt> graph type:
 186
 187 <pre>
 188 class count_tree_edges_bfs_visitor(bgl.Graph.BFSVisitor):
 189   def __init__(self, name_map):
 190     bgl.Graph.BFSVisitor.__init__(self)
 191     self.name_map = name_map
 192
 193   def tree_edge(self, e, g):
 194     (u, v) = (g.source(e), g.target(e))
 195     print "Tree edge ",
 196     print self.name_map[u],
 197     print " -> ",
 198     print self.name_map[v]
 199 </pre>
 200
 201 <h3>See also</h3>
 202
 203 <a href="./visitor_concepts.html">Visitor concepts</a>
 204
 205 <br>
 206 <HR>
 207 <TABLE>
 208 <TR valign=top>
 209 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 210 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 211 Indiana University (<A
 212 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 213 <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>
 214 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 215 Indiana University (<A
 216 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 217 </TD></TR></TABLE>
 218
 219 </BODY>
 220 </HTML>