123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek 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: Filtered Graph</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><A NAME="sec:filtered-graph-class"></A>
- <pre>
- filtered_graph<Graph, EdgePredicate, VertexPredicate>
- </pre>
- </H1>
- <P>
- The <tt>filtered_graph</tt> class template is an adaptor that creates
- a filtered view of a graph. The predicate function objects determine
- which edges and vertices of the original graph will show up in the
- filtered graph. If the edge predicate returns <tt>true</tt> for an
- edge then it shows up in the filtered graph, and if the predicate
- returns <tt>false</tt> then the edge does not appear in the filtered
- graph. Likewise for vertices. The <tt>filtered_graph</tt> class does
- not create a copy of the original graph, but uses a reference to the
- original graph. The lifetime of the original graph must extend past
- any use of the filtered graph. The filtered graph does not change the
- structure of the original graph, though vertex and edge properties of
- the original graph can be changed through property maps of the
- filtered graph. Vertex and edge descriptors of the filtered graph are
- the same as, and interchangeable with, the vertex and edge descriptors
- of the original graph.
- <P>The <a href="#num_vertices"><tt>num_vertices</tt></a> and <a
- href="#num_edges"><tt>num_edges</tt></a> functions do not filter
- before returning results, so they return the number of vertices or
- edges in the underlying graph, unfiltered <a href="#2">[2]</a>.
- <H3>Example</H3>
- <P>
- In this example we will filter a graph's edges based on edge
- weight. We will keep all edges with positive edge weight.
- First, we create a predicate function object.
- <PRE>
- template <typename EdgeWeightMap>
- struct positive_edge_weight {
- positive_edge_weight() { }
- positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }
- template <typename Edge>
- bool operator()(const Edge& e) const {
- return 0 < get(m_weight, e);
- }
- EdgeWeightMap m_weight;
- };
- </PRE>
- Now we create a graph and print out the filtered graph.
- <pre>
- int main()
- {
- using namespace boost;
-
- typedef adjacency_list<vecS, vecS, directedS,
- no_property, property<edge_weight_t, int> > Graph;
- typedef property_map<Graph, edge_weight_t>::type EdgeWeightMap;
- enum { A, B, C, D, E, N };
- const char* name = "ABCDE";
- Graph g(N);
- add_edge(A, B, 2, g);
- add_edge(A, C, 0, g);
- add_edge(C, D, 1, g);
- add_edge(C, E, 0, g);
- add_edge(D, B, 3, g);
- add_edge(E, C, 0, g);
-
- positive_edge_weight<EdgeWeightMap> filter(get(edge_weight, g));
- filtered_graph<Graph, positive_edge_weight<EdgeWeightMap> >
- fg(g, filter);
- std::cout << "filtered edge set: ";
- print_edges(fg, name);
- std::cout << "filtered out-edges:" << std::endl;
- print_graph(fg, name);
-
- return 0;
- }
- </pre>
- The output is:
- <PRE>
- filtered edge set: (A,B) (C,D) (D,B)
- filtered out-edges:
- A --> B
- B -->
- C --> D
- D --> B
- E -->
- </PRE>
- <P>
- <H3>Template Parameters</H3>
- <P>
- <TABLE border>
- <TR>
- <th>Parameter</th><th>Description</th><th>Default</th>
- </tr>
- <TR><TD><TT>Graph</TT></TD>
- <TD>The underlying graph type.</TD>
- <TD> </TD>
- </TR>
- <TR>
- <TD><TT>EdgePredicate</TT></TD> <TD>A function object that selects
- which edges from the original graph will appear in the filtered
- graph. The function object must model <a
- href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>. The
- argument type for the function object must be the edge descriptor type
- of the graph. Also, the predicate must be <a
- href="http://www.boost.org/sgi/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
- <TD> </TD>
- </TR>
- <TR>
- <TD><TT>VertexPredicate</TT></TD>
- <TD>A function object that selects
- which vertices from the original graph will appear in the filtered
- graph. The function object must model <a
- href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>. The
- argument type for the function object must be the vertex descriptor type
- of the graph. Also, the predicate must be <a
- href="http://www.boost.org/sgi/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
- <TD><TT>keep_all</TT></TD>
- </TR>
- </TABLE>
- <P>
- <H3>Model of</H3>
- <P>
- This depends on the underlying graph type. If the underlying
- <tt>Graph</tt> type models <a
- href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and <a
- href="./PropertyGraph.html">PropertyGraph</a> then so does the
- filtered graph. If the underlying <tt>Graph</tt> type models fewer or
- smaller concepts than these, then so does the filtered graph.
- <P>
- <H3>Where Defined</H3>
- <P>
- <a href="../../../boost/graph/filtered_graph.hpp"><TT>boost/graph/filtered_graph.hpp</TT></a>
- <P>
- <H2>Associated Types</H2>
- <hr>
- <tt>graph_traits<filtered_graph>::vertex_descriptor</tt>
- <br><br>
- The type for the vertex descriptors associated with the
- <TT>filtered_graph</TT>, which is the same type as the
- <tt>vertex_descriptor</tt> for the original <tt>Graph</tt>.
- <hr>
- <tt>graph_traits<filtered_graph>::edge_descriptor</tt><br>
- <br><br>
- The type for the edge descriptors associated with the
- <TT>filtered_graph</TT>, which is the same type as the
- <tt>edge_descriptor</tt> for the original <tt>Graph</tt>.
- <hr>
- <tt>graph_traits<filtered_graph>::vertex_iterator</tt><br>
- <br><br>
- The type for the iterators returned by <TT>vertices()</TT>,
- which is:
- <pre>
- <a href="../../iterator/doc/filter_iterator.html">filter_iterator</a><VertexPredicate, graph_traits<Graph>::vertex_iterator>
- </pre>
- The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
- <hr>
- <tt>graph_traits<filtered_graph>::edge_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>edges()</TT>, which is:
- <pre>
- <a href="../../iterator/doc/filter_iterator.html">filter_iterator</a><EdgePredicate, graph_traits<Graph>::edge_iterator>
- </pre>
- The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
- <hr>
- <tt>graph_traits<filtered_graph>::out_edge_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>out_edges()</TT>, which is:
- <pre>
- <a href="../../iterator/doc/filter_iterator.html">filter_iterator</a><EdgePredicate, graph_traits<Graph>::out_edge_iterator>
- </pre>
- The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
- <hr>
- <tt>graph_traits<filtered_graph>::adjacency_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>adjacent_vertices()</TT>.
- The <tt>adjacency_iterator</tt> models the same iterator concept as
- <tt>out_edge_iterator</tt>.
- <hr>
- <tt>graph_traits<filtered_graph>::directed_category</tt><br>
- <br><br>
- Provides information about whether the graph is directed
- (<TT>directed_tag</TT>) or undirected (<TT>undirected_tag</TT>).
- <hr>
- <tt>graph_traits<filtered_graph>::edge_parallel_category</tt><br>
- <br><br>
- This describes whether the graph class allows the insertion of
- parallel edges (edges with the same source and target). The two tags
- are <TT>allow_parallel_edge_tag</TT> and
- <TT>disallow_parallel_edge_tag</TT>.
- <hr>
- <tt>graph_traits<filtered_graph>::vertices_size_type</tt>
- <br><br>
- The type used for dealing with the number of vertices in the graph.
- <hr>
- <tt>graph_traits<filtered_graph>::edges_size_type</tt>
- <br><br>
- The type used for dealing with the number of edges in the graph.
- <hr>
- <tt>graph_traits<filtered_graph>::degree_size_type</tt>
- <br><br>
- The type used for dealing with the number of edges incident to a vertex
- in the graph.
- <hr>
- <tt>property_map<filtered_graph, Property>::type</tt><br>
- and<br>
- <tt>property_map<filtered_graph, Property>::const_type</tt>
- <br><br>
- The property map type for vertex or edge properties in the graph.
- The same property maps from the adapted graph are available
- in the filtered graph.
- <hr>
- <H2>Member Functions</H2>
- <hr>
- <pre>
- filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp)
- </pre>
- Create a filtered graph based on the graph <i>g</i> and the
- edge filter <i>ep</i> and vertex filter <i>vp</i>.
- <hr>
- <pre>
- filtered_graph(Graph& g, EdgePredicate ep)
- </pre>
- Create a filtered graph based on the graph <i>g</i> and the
- edge filter <i>ep</i>. All vertices from the original graph
- are retained.
- <hr>
- filtered_graph(const filtered_graph& x)
- </pre>
- This creates a filtered graph for the same underlying graph
- as <i>x</i>. Anotherwords, this is a shallow copy.
- <hr>
- <pre>
- filtered_graph& operator=(const filtered_graph& x)
- </pre>
- This creates a filtered graph for the same underlying graph
- as <i>x</i>. Anotherwords, this is a shallow copy.
- <hr>
- <P>
- <H2>Non-Member Functions</H2>
- <h4>Structure Access</h4>
- <hr>
- <pre>
- std::pair<vertex_iterator, vertex_iterator>
- vertices(const filtered_graph& g)
- </pre>
- Returns an iterator-range providing access to the vertex set of graph
- <tt>g</tt>.
- <hr>
- <pre>
- std::pair<edge_iterator, edge_iterator>
- edges(const filtered_graph& g)
- </pre>
- Returns an iterator-range providing access to the edge set of graph
- <tt>g</tt>.
- <hr>
- <pre>
- std::pair<adjacency_iterator, adjacency_iterator>
- adjacent_vertices(vertex_descriptor u, const filtered_graph& g)
- </pre>
- Returns an iterator-range providing access to the vertices adjacent to
- vertex <tt>u</tt> in graph <tt>g</tt>.
- <hr>
- <pre>
- std::pair<out_edge_iterator, out_edge_iterator>
- out_edges(vertex_descriptor u, const filtered_graph& g)
- </pre>
- Returns an iterator-range providing access to the out-edges of vertex
- <tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this
- iterator-range provides access to all edges incident on vertex
- <tt>u</tt>. For both directed and undirected graphs, for an out-edge
- <tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt>
- where <tt>v</tt> is a vertex adjacent to <tt>u</tt>.
- <hr>
- <pre>
- std::pair<in_edge_iterator, in_edge_iterator>
- in_edges(vertex_descriptor v, const filtered_graph& g)
- </pre>
- Returns an iterator-range providing access to the in-edges of vertex
- <tt>v</tt> in graph <tt>g</tt>. For an in-edge <tt>e</tt>,
- <tt>target(e, g) == v</tt> and <tt>source(e, g) == u</tt> for some
- vertex <tt>u</tt> that is adjacent to <tt>v</tt>, whether the graph is
- directed or undirected.
- <hr>
- <pre>
- vertex_descriptor
- source(edge_descriptor e, const filtered_graph& g)
- </pre>
- Returns the source vertex of edge <tt>e</tt>.
- <hr>
- <pre>
- vertex_descriptor
- target(edge_descriptor e, const filtered_graph& g)
- </pre>
- Returns the target vertex of edge <tt>e</tt>.
- <hr>
- <pre>
- degree_size_type
- out_degree(vertex_descriptor u, const filtered_graph& g)
- </pre>
- Returns the number of edges leaving vertex <tt>u</tt>.
- <hr>
- <pre>
- degree_size_type
- in_degree(vertex_descriptor u, const filtered_graph& g)
- </pre>
- Returns the number of edges entering vertex <tt>u</tt>.
- <hr>
- <pre><a name="num_vertices"></a>
- vertices_size_type
- num_vertices(const filtered_graph& g)
- </pre>
- Returns the number of vertices in the underlying graph <a href="#2">[2]</a>.
- <hr>
- <pre><a name="num_edges"></a>
- edges_size_type
- num_edges(const filtered_graph& g)
- </pre>
- Returns the number of edges in the underlying graph <a href="#2">[2]</a>.
- <hr>
- <pre>
- std::pair<edge_descriptor, bool>
- edge(vertex_descriptor u, vertex_descriptor v,
- const filtered_graph& g)
- </pre>
- Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in
- graph <tt>g</tt>.
- <hr>
- <pre>
- template <typename G, typename EP, typename VP>
- std::pair<out_edge_iterator, out_edge_iterator>
- edge_range(vertex_descriptor u, vertex_descriptor v,
- const filtered_graph& g)
- </pre>
- Returns a pair of out-edge iterators that give the range for all the
- parallel edges from <tt>u</tt> to <tt>v</tt>. This function only works
- when the underlying graph supports <tt>edge_range</tt>, which requires
- that it sorts its out edges according to target vertex and allows
- parallel edges. The <tt>adjacency_list</tt> class with
- <tt>OutEdgeList=multisetS</tt> is an example of such a graph.
- <hr>
- <h4>Property Map Access</h4>
- <hr>
- <pre>
- template <class <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<filtered_graph, PropertyTag>::type
- get(PropertyTag, filtered_graph& g)
- template <class <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<filtered_graph, Tag>::const_type
- get(PropertyTag, const filtered_graph& g)
- </pre>
- Returns the property map object for the vertex property specified by
- <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the
- properties specified in the graph's <TT>VertexProperty</TT> template
- argument.
- <hr>
- <pre>
- template <class <a href="./PropertyTag.html">PropertyTag</a>, class X>
- typename property_traits<property_map<filtered_graph, PropertyTag>::const_type>::value_type
- get(PropertyTag, const filtered_graph& g, X x)
- </pre>
- This returns the property value for <tt>x</tt>, where <tt>x</tt> is either
- a vertex or edge descriptor.
- <hr>
- <pre>
- template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
- void
- put(PropertyTag, const filtered_graph& g, X x, const Value& value)
- </pre>
- This sets the property value for <tt>x</tt> to
- <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
- <tt>Value</tt> must be convertible to
- <tt>typename property_traits<property_map<filtered_graph, PropertyTag>::type>::value_type</tt>
- <hr>
- <h3>See Also</h3>
- <a href="./property_map.html"><tt>property_map</tt></a>,
- <a href="./graph_traits.html"><tt>graph_traits</tt></a>
- <h3>Notes</h3>
- <p>
- <a name="1">[1]</a> The reason for requiring <a
- href="http://www.boost.org/sgi/stl/DefaultConstructible.html">Default
- Constructible</a> in the <tt>EdgePredicate</tt> and
- <tt>VertexPredicate</tt> types is that these predicates are stored
- by-value (for performance reasons) in the filter iterator adaptor, and
- iterators are required to be Default Constructible by the C++
- Standard.
- <p> <a name="2">[2]</a> It would be nicer to return the number of
- vertices (or edges) remaining after the filter has been applied, but
- this has two problems. The first is that it would take longer to
- calculate, and the second is that it would interact badly with the
- underlying vertex/edge index mappings. The index mapping would no
- longer fall in the range <tt>[0,num_vertices(g))</tt> (resp. <tt>[0,
- num_edges(g))</tt>) which is assumed in many of the algorithms.
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|