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

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek 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: Filtered Graph</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
  19
  20 <H1><A NAME="sec:filtered-graph-class"></A>
  21 <pre>
  22 filtered_graph&lt;Graph, EdgePredicate, VertexPredicate&gt;
  23 </pre>
  24 </H1>
  25
  26
  27 <P>
  28 The <tt>filtered_graph</tt> class template is an adaptor that creates
  29 a filtered view of a graph. The predicate function objects determine
  30 which edges and vertices of the original graph will show up in the
  31 filtered graph.  If the edge predicate returns <tt>true</tt> for an
  32 edge then it shows up in the filtered graph, and if the predicate
  33 returns <tt>false</tt> then the edge does not appear in the filtered
  34 graph.  Likewise for vertices. The <tt>filtered_graph</tt> class does
  35 not create a copy of the original graph, but uses a reference to the
  36 original graph. The lifetime of the original graph must extend past
  37 any use of the filtered graph. The filtered graph does not change the
  38 structure of the original graph, though vertex and edge properties of
  39 the original graph can be changed through property maps of the
  40 filtered graph. Vertex and edge descriptors of the filtered graph are
  41 the same as, and interchangeable with, the vertex and edge descriptors
  42 of the original graph.
  43
  44 <P>The <a href="#num_vertices"><tt>num_vertices</tt></a> and <a
  45 href="#num_edges"><tt>num_edges</tt></a> functions do not filter
  46 before returning results, so they return the number of vertices or
  47 edges in the underlying graph, unfiltered <a href="#2">[2]</a>.
  48
  49 <H3>Example</H3>
  50
  51 <P>
  52 In this example we will filter a graph's edges based on edge
  53 weight. We will keep all edges with positive edge weight.
  54 First, we create a predicate function object.
  55
  56 <PRE>
  57 template &lt;typename EdgeWeightMap&gt;
  58 struct positive_edge_weight {
  59   positive_edge_weight() { }
  60   positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }
  61   template &lt;typename Edge&gt;
  62   bool operator()(const Edge& e) const {
  63     return 0 &lt; get(m_weight, e);
  64   }
  65   EdgeWeightMap m_weight;
  66 };
  67 </PRE>
  68
  69 Now we create a graph and print out the filtered graph.
  70 <pre>
  71 int main()
  72 {
  73   using namespace boost;
  74
  75   typedef adjacency_list&lt;vecS, vecS, directedS,
  76     no_property, property&lt;edge_weight_t, int&gt; &gt; Graph;
  77   typedef property_map&lt;Graph, edge_weight_t&gt;::type EdgeWeightMap;
  78
  79   enum { A, B, C, D, E, N };
  80   const char* name = "ABCDE";
  81   Graph g(N);
  82   add_edge(A, B, 2, g);
  83   add_edge(A, C, 0, g);
  84   add_edge(C, D, 1, g);
  85   add_edge(C, E, 0, g);
  86   add_edge(D, B, 3, g);
  87   add_edge(E, C, 0, g);
  88
  89   positive_edge_weight&lt;EdgeWeightMap&gt; filter(get(edge_weight, g));
  90   filtered_graph&lt;Graph, positive_edge_weight&lt;EdgeWeightMap&gt; &gt;
  91     fg(g, filter);
  92
  93   std::cout &lt;&lt; "filtered edge set: ";
  94   print_edges(fg, name);
  95
  96   std::cout &lt;&lt; "filtered out-edges:" &lt;&lt; std::endl;
  97   print_graph(fg, name);
  98
  99   return 0;
 100 }
 101 </pre>
 102 The output is:
 103 <PRE>
 104 filtered edge set: (A,B) (C,D) (D,B)
 105 filtered out-edges:
 106 A --> B
 107 B -->
 108 C --> D
 109 D --> B
 110 E -->
 111 </PRE>
 112
 113 <P>
 114
 115 <H3>Template Parameters</H3>
 116
 117 <P>
 118 <TABLE border>
 119 <TR>
 120 <th>Parameter</th><th>Description</th><th>Default</th>
 121 </tr>
 122
 123 <TR><TD><TT>Graph</TT></TD>
 124 <TD>The underlying graph type.</TD>
 125 <TD>&nbsp;</TD>
 126 </TR>
 127
 128 <TR>
 129 <TD><TT>EdgePredicate</TT></TD> <TD>A function object that selects
 130 which edges from the original graph will appear in the filtered
 131 graph. The function object must model <a
 132 href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>. The
 133 argument type for the function object must be the edge descriptor type
 134 of the graph. Also, the predicate must be <a
 135 href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
 136 <TD>&nbsp;</TD>
 137 </TR>
 138
 139 <TR>
 140 <TD><TT>VertexPredicate</TT></TD>
 141 <TD>A function object that selects
 142 which vertices from the original graph will appear in the filtered
 143 graph. The function object must model <a
 144 href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>. The
 145 argument type for the function object must be the vertex descriptor type
 146 of the graph. Also, the predicate must be <a
 147 href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
 148 <TD><TT>keep_all</TT></TD>
 149 </TR>
 150
 151 </TABLE>
 152 <P>
 153
 154 <H3>Model of</H3>
 155
 156 <P>
 157 This depends on the underlying graph type. If the underlying
 158 <tt>Graph</tt> type models <a
 159 href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and <a
 160 href="./PropertyGraph.html">PropertyGraph</a> then so does the
 161 filtered graph. If the underlying <tt>Graph</tt> type models fewer or
 162 smaller concepts than these, then so does the filtered graph.
 163
 164 <P>
 165
 166 <H3>Where Defined</H3>
 167
 168 <P>
 169 <a href="../../../boost/graph/filtered_graph.hpp"><TT>boost/graph/filtered_graph.hpp</TT></a>
 170
 171 <P>
 172
 173 <H2>Associated Types</H2>
 174
 175 <hr>
 176
 177 <tt>graph_traits&lt;filtered_graph&gt;::vertex_descriptor</tt>
 178 <br><br>
 179
 180 The type for the vertex descriptors associated with the
 181 <TT>filtered_graph</TT>, which is the same type as the
 182 <tt>vertex_descriptor</tt> for the original <tt>Graph</tt>.
 183
 184
 185 <hr>
 186
 187 <tt>graph_traits&lt;filtered_graph&gt;::edge_descriptor</tt><br>
 188 <br><br>
 189 The type for the edge descriptors associated with the
 190 <TT>filtered_graph</TT>, which is the same type as the
 191 <tt>edge_descriptor</tt> for the original <tt>Graph</tt>.
 192
 193 <hr>
 194
 195 <tt>graph_traits&lt;filtered_graph&gt;::vertex_iterator</tt><br>
 196 <br><br>
 197 The type for the iterators returned by <TT>vertices()</TT>,
 198 which is:
 199 <pre>
 200 <a href="../../iterator/doc/filter_iterator.html">filter_iterator</a>&lt;VertexPredicate, graph_traits&lt;Graph&gt;::vertex_iterator&gt;
 201 </pre>
 202 The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
 203
 204
 205 <hr>
 206
 207 <tt>graph_traits&lt;filtered_graph&gt;::edge_iterator</tt>
 208 <br><br>
 209 The type for the iterators returned by <TT>edges()</TT>, which is:
 210 <pre>
 211 <a href="../../iterator/doc/filter_iterator.html">filter_iterator</a>&lt;EdgePredicate, graph_traits&lt;Graph&gt;::edge_iterator&gt;
 212 </pre>
 213 The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
 214
 215 <hr>
 216
 217
 218 <tt>graph_traits&lt;filtered_graph&gt;::out_edge_iterator</tt>
 219 <br><br>
 220 The type for the iterators returned by <TT>out_edges()</TT>, which is:
 221 <pre>
 222 <a href="../../iterator/doc/filter_iterator.html">filter_iterator</a>&lt;EdgePredicate, graph_traits&lt;Graph&gt;::out_edge_iterator&gt;
 223 </pre>
 224 The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
 225
 226
 227 <hr>
 228
 229 <tt>graph_traits&lt;filtered_graph&gt;::adjacency_iterator</tt>
 230 <br><br>
 231 The type for the iterators returned by <TT>adjacent_vertices()</TT>.
 232
 233 The <tt>adjacency_iterator</tt> models the same iterator concept as
 234 <tt>out_edge_iterator</tt>.
 235
 236 <hr>
 237
 238 <tt>graph_traits&lt;filtered_graph&gt;::directed_category</tt><br>
 239 <br><br>
 240 Provides information about whether the graph is directed
 241 (<TT>directed_tag</TT>) or undirected (<TT>undirected_tag</TT>).
 242
 243 <hr>
 244
 245 <tt>graph_traits&lt;filtered_graph&gt;::edge_parallel_category</tt><br>
 246 <br><br>
 247 This describes whether the graph class allows the insertion of
 248 parallel edges (edges with the same source and target). The two tags
 249 are <TT>allow_parallel_edge_tag</TT> and
 250 <TT>disallow_parallel_edge_tag</TT>.
 251
 252 <hr>
 253
 254 <tt>graph_traits&lt;filtered_graph&gt;::vertices_size_type</tt>
 255 <br><br>
 256 The type used for dealing with the number of vertices in the graph.
 257
 258 <hr>
 259
 260 <tt>graph_traits&lt;filtered_graph&gt;::edges_size_type</tt>
 261 <br><br>
 262 The type used for dealing with the number of edges in the graph.
 263
 264 <hr>
 265
 266 <tt>graph_traits&lt;filtered_graph&gt;::degree_size_type</tt>
 267 <br><br>
 268 The type used for dealing with the number of edges incident to a vertex
 269 in the graph.
 270
 271 <hr>
 272
 273 <tt>property_map&lt;filtered_graph, Property&gt;::type</tt><br>
 274 and<br>
 275 <tt>property_map&lt;filtered_graph, Property&gt;::const_type</tt>
 276 <br><br>
 277 The property map type for vertex or edge properties in the graph.
 278 The same property maps from the adapted graph are available
 279 in the filtered graph.
 280
 281 <hr>
 282
 283 <H2>Member Functions</H2>
 284
 285 <hr>
 286
 287 <pre>
 288 filtered_graph(Graph&amp;&nbsp;g, EdgePredicate&nbsp;ep, VertexPredicate&nbsp;vp)
 289 </pre>
 290 Create a filtered graph based on the graph <i>g</i> and the
 291 edge filter <i>ep</i> and vertex filter <i>vp</i>.
 292
 293 <hr>
 294
 295 <pre>
 296 filtered_graph(Graph&amp;&nbsp;g, EdgePredicate&nbsp;ep)
 297 </pre>
 298 Create a filtered graph based on the graph <i>g</i> and the
 299 edge filter <i>ep</i>. All vertices from the original graph
 300 are retained.
 301
 302 <hr>
 303
 304 filtered_graph(const&nbsp;filtered_graph&amp;&nbsp;x)
 305 </pre>
 306 This creates a filtered graph for the same underlying graph
 307 as <i>x</i>. Anotherwords, this is a shallow copy.
 308
 309 <hr>
 310
 311 <pre>
 312 filtered_graph&amp; operator=(const&nbsp;filtered_graph&amp;&nbsp;x)
 313 </pre>
 314 This creates a filtered graph for the same underlying graph
 315 as <i>x</i>. Anotherwords, this is a shallow copy.
 316
 317 <hr>
 318
 319 <P>
 320
 321 <H2>Non-Member Functions</H2>
 322
 323 <h4>Structure Access</h4>
 324
 325 <hr>
 326
 327 <pre>
 328 std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
 329 vertices(const filtered_graph&amp; g)
 330 </pre>
 331 Returns an iterator-range providing access to the vertex set of graph
 332 <tt>g</tt>.
 333
 334 <hr>
 335
 336 <pre>
 337 std::pair&lt;edge_iterator,&nbsp;edge_iterator&gt;
 338 edges(const filtered_graph&amp; g)
 339 </pre>
 340 Returns an iterator-range providing access to the edge set of graph
 341 <tt>g</tt>.
 342
 343 <hr>
 344
 345 <pre>
 346 std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;
 347 adjacent_vertices(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
 348 </pre>
 349 Returns an iterator-range providing access to the vertices adjacent to
 350 vertex <tt>u</tt> in graph <tt>g</tt>.
 351
 352 <hr>
 353
 354
 355 <pre>
 356 std::pair&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
 357 out_edges(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
 358 </pre>
 359 Returns an iterator-range providing access to the out-edges of vertex
 360 <tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this
 361 iterator-range provides access to all edges incident on vertex
 362 <tt>u</tt>. For both directed and undirected graphs, for an out-edge
 363 <tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt>
 364 where <tt>v</tt> is a vertex adjacent to <tt>u</tt>.
 365
 366 <hr>
 367
 368 <pre>
 369 std::pair&lt;in_edge_iterator,&nbsp;in_edge_iterator&gt;
 370 in_edges(vertex_descriptor&nbsp;v, const&nbsp;filtered_graph&amp;&nbsp;g)
 371 </pre>
 372 Returns an iterator-range providing access to the in-edges of vertex
 373 <tt>v</tt> in graph <tt>g</tt>.  For an in-edge <tt>e</tt>,
 374 <tt>target(e, g) == v</tt> and <tt>source(e, g) == u</tt> for some
 375 vertex <tt>u</tt> that is adjacent to <tt>v</tt>, whether the graph is
 376 directed or undirected.
 377
 378 <hr>
 379
 380 <pre>
 381 vertex_descriptor
 382 source(edge_descriptor&nbsp;e, const&nbsp;filtered_graph&amp;&nbsp;g)
 383 </pre>
 384 Returns the source vertex of edge <tt>e</tt>.
 385
 386 <hr>
 387
 388 <pre>
 389 vertex_descriptor
 390 target(edge_descriptor&nbsp;e, const&nbsp;filtered_graph&amp;&nbsp;g)
 391 </pre>
 392 Returns the target vertex of edge <tt>e</tt>.
 393
 394 <hr>
 395
 396 <pre>
 397 degree_size_type
 398 out_degree(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
 399 </pre>
 400 Returns the number of edges leaving vertex <tt>u</tt>.
 401
 402 <hr>
 403
 404 <pre>
 405 degree_size_type
 406 in_degree(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
 407 </pre>
 408 Returns the number of edges entering vertex <tt>u</tt>.
 409
 410 <hr>
 411
 412 <pre><a name="num_vertices"></a>
 413 vertices_size_type
 414 num_vertices(const filtered_graph&amp; g)
 415 </pre>
 416 Returns the number of vertices in the underlying graph <a href="#2">[2]</a>.
 417
 418 <hr>
 419
 420 <pre><a name="num_edges"></a>
 421 edges_size_type
 422 num_edges(const filtered_graph&amp; g)
 423 </pre>
 424 Returns the number of edges in the underlying graph <a href="#2">[2]</a>.
 425
 426 <hr>
 427
 428 <pre>
 429 std::pair&lt;edge_descriptor, bool&gt;
 430 edge(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
 431      const&nbsp;filtered_graph&amp;&nbsp;g)
 432 </pre>
 433 Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in
 434 graph <tt>g</tt>.
 435
 436 <hr>
 437
 438 <pre>
 439 template &lt;typename G, typename EP, typename VP&gt;
 440 std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
 441 edge_range(vertex_descriptor u, vertex_descriptor v,
 442            const filtered_graph&amp; g)
 443 </pre>
 444 Returns a pair of out-edge iterators that give the range for all the
 445 parallel edges from <tt>u</tt> to <tt>v</tt>. This function only works
 446 when the underlying graph supports <tt>edge_range</tt>, which requires
 447 that it sorts its out edges according to target vertex and allows
 448 parallel edges. The <tt>adjacency_list</tt> class with
 449 <tt>OutEdgeList=multisetS</tt> is an example of such a graph.
 450
 451
 452 <hr>
 453
 454 <h4>Property Map Access</h4>
 455
 456 <hr>
 457
 458 <pre>
 459 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 460 property_map&lt;filtered_graph, PropertyTag&gt;::type
 461 get(PropertyTag, filtered_graph&amp; g)
 462
 463 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
 464 property_map&lt;filtered_graph, Tag&gt;::const_type
 465 get(PropertyTag, const filtered_graph&amp; g)
 466 </pre>
 467 Returns the property map object for the vertex property specified by
 468 <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the
 469 properties specified in the graph's <TT>VertexProperty</TT> template
 470 argument.
 471
 472 <hr>
 473
 474 <pre>
 475 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X&gt;
 476 typename property_traits&lt;property_map&lt;filtered_graph, PropertyTag&gt;::const_type&gt::value_type
 477 get(PropertyTag, const filtered_graph&amp; g, X x)
 478 </pre>
 479 This returns the property value for <tt>x</tt>, where <tt>x</tt> is either
 480 a vertex or edge descriptor.
 481 <hr>
 482
 483 <pre>
 484 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value&gt;
 485 void
 486 put(PropertyTag, const filtered_graph&amp; g, X x, const Value& value)
 487 </pre>
 488 This sets the property value for <tt>x</tt> to
 489 <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
 490 <tt>Value</tt> must be convertible to
 491 <tt>typename property_traits&lt;property_map&lt;filtered_graph, PropertyTag&gt;::type&gt::value_type</tt>
 492
 493 <hr>
 494
 495 <h3>See Also</h3>
 496
 497 <a href="./property_map.html"><tt>property_map</tt></a>,
 498 <a href="./graph_traits.html"><tt>graph_traits</tt></a>
 499
 500 <h3>Notes</h3>
 501
 502 <p>
 503 <a name="1">[1]</a> The reason for requiring <a
 504 href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default
 505 Constructible</a> in the <tt>EdgePredicate</tt> and
 506 <tt>VertexPredicate</tt> types is that these predicates are stored
 507 by-value (for performance reasons) in the filter iterator adaptor, and
 508 iterators are required to be Default Constructible by the C++
 509 Standard.
 510
 511 <p> <a name="2">[2]</a> It would be nicer to return the number of
 512 vertices (or edges) remaining after the filter has been applied, but
 513 this has two problems. The first is that it would take longer to
 514 calculate, and the second is that it would interact badly with the
 515 underlying vertex/edge index mappings. The index mapping would no
 516 longer fall in the range <tt>[0,num_vertices(g))</tt> (resp. <tt>[0,
 517 num_edges(g))</tt>) which is assumed in many of the algorithms.
 518
 519
 520 <br>
 521 <HR>
 522 <TABLE>
 523 <TR valign=top>
 524 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 525 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 526 Indiana University (<A
 527 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 528 <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>
 529 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 530 Indiana University (<A
 531 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 532 </TD></TR></TABLE>
 533
 534 </BODY>
 535 </HTML>