123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299 |
- <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>MutableGraph</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>
- <H2><A NAME="sec:MutableGraph"></A>
- MutableGraph
- </H2>
- A MutableGraph can be changed via the addition or removal of
- edges and vertices.
- <H3>Refinement of</H3>
- <a href="./Graph.html">Graph</a>
- <h3>Notation</h3>
- <Table>
- <TR>
- <TD><tt>G</tt></TD>
- <TD>A type that is a model of Graph.</TD>
- </TR>
- <TR>
- <TD><tt>g</tt></TD>
- <TD>An object of type <tt>G</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>e</tt></TD>
- <TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>u,v</tt></TD>
- <TD>are objects of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>iter</tt></TD>
- <TD>is an object of type <tt>boost::graph_traits<G>::out_edge_iterator</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>p</tt></TD>
- <TD>is an object of a type that models <a
- href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>
- and whose argument type matches the <tt>edge_descriptor</tt> type.
- </TR>
- </table>
- <H3>Valid Expressions</H3>
- <table border>
- <tr>
- <TD><a name="sec:add-edge"><TT>add_edge(u, v, g)</TT></a></TD>
- <TD>
- Inserts the edge <i>(u,v)</i> into the graph, and returns an edge
- descriptor pointing to the new edge. If the graph disallows parallel
- edges, and the edge <i>(u,v)</i> is already in the graph, then the
- <tt>bool</tt> flag returned is <tt>false</tt> and the returned edge
- descriptor points to the already existing edge. Note that for
- undirected graphs, <i>(u,v)</i> is the same edge as <i>(v,u)</i>, so
- after a call to the function <tt>add_edge()</tt>, this implies that
- edge <i>(u,v)</i> will appear in the out-edges of <i>u</i> and
- <i>(u,v)</i> (or equivalently <i>(v,u)</i>) will appear in the
- out-edges of <i>v</i>. Put another way, <i>v</i> will be adjacent to
- <i>u</i> and <i>u</i> will be adjacent to <i>v</i>.
- <br>
- Return type: <TT>std::pair<edge_descriptor, bool></TT>
- </TD>
- </tr>
- <tr>
- <TD><a name="sec:remove_edge"><TT>remove_edge(u, v, g)</TT></a></TD>
- <TD>
- Remove the edge <i>(u,v)</i> from the graph. If the
- graph allows parallel edges this remove all occurrences of
- <i>(u,v)</i>.<br>
- Return type: <TT>void</TT><br>
- Precondition: <i>u</i> and <i>v</i> are vertices in the graph.<br>
- Postcondition: <i>(u,v)</i> is no longer in the edge set for
- <TT>g</TT>.<br>
- </TD>
- </TR>
- <tr>
- <TD><TT>remove_edge(e, g)</TT></TD>
- <TD>Remove the edge <i>e</i> from the graph.<br>
- Return type: <TT>void</TT><br>
- Precondition: <i>e</i> is an edge in the graph.<br>
- Postcondition: <i>e</i> is no longer in the edge set for <TT>g</TT>.
- </TD>
- </TR>
- <tr>
- <TD><TT>remove_edge(iter, g)</TT></TD>
- <TD>Remove the edge pointed to be <tt>iter</tt> from the graph. This
- expression is only required when the graph also models <a
- href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
- Return type: <TT>void</TT><br>
- Precondition: <tt>*iter</tt> is an edge in the graph.<br>
- Postcondition: <tt>*iter</tt> is no longer in the edge set for <TT>g</TT>.
- </TD>
- </TR>
- <tr>
- <TD><TT>remove_edge_if(p, g)</TT></TD>
- <TD>Remove all the edges from graph <tt>g</tt> for which
- the predicate <tt>p</tt> returns true.<br>
- Return type: <TT>void</TT>
- </TD>
- </TR>
- <tr>
- <TD><TT>remove_out_edge_if(u, p, g)</TT></TD>
- <TD>Remove all the out-edges of vertex <tt>u</tt> for which the
- predicate <tt>p</tt> returns true. This expression is only required
- when the graph also models <a
- href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
- Return type: <TT>void</TT>
- </TD>
- </TR>
- <tr>
- <TD><TT>remove_in_edge_if(u, p, g)</TT></TD>
- <TD>Remove all the in-edges of vertex <tt>u</tt> for which the
- predicate <tt>p</tt> returns true. This expression is only required when the
- graph also models <a
- href="./BidirectionalGraph.html">BidirectionalGraph</a>.<br>
- Return type: <TT>void</TT>
- </TD>
- </TR>
- <tr>
- <TD><a name="sec:add-vertex"><TT>add_vertex(g)</TT></a></TD>
- <TD>
- Add a new vertex to the graph. The <TT>vertex_descriptor</TT> for the
- new vertex is returned.<br>
- Return type: <TT>vertex_descriptor</TT>
- </TD>
- </TR>
- <tr>
- <TD><TT>clear_vertex(u, g)</TT></TD>
- <TD>
- Remove all edges to and from vertex <tt>u</tt> from the graph.<br>
- Return type: <TT>void</TT><br>
- Precondition: <tt>u</tt> is a valid vertex descriptor of <TT>g</TT>.<br>
- Postcondition: <tt>u</tt> does not appear as a source or target of
- any edge in <TT>g</TT>.
- </TD>
- </TR>
- <tr>
- <TD><a name="sec:remove-vertex"><TT>remove_vertex(u, g)</TT></a></TD>
- <TD>
- Remove <i>u</i> from the vertex set of the graph. Note that undefined
- behavior may result if there are edges remaining in the graph who's
- target is <i>u</i>. Typically the <TT>clear_vertex()</TT> function
- should be called first.<br>
- Return type: <TT>void</TT><br>
- Precondition: <TT>u</TT> is a valid vertex descriptor of <TT>g</TT>.<br>
- Postcondition: <TT>num_vertices(g)</TT> is one less, <TT>u</TT>
- no longer appears in the vertex set of the graph and it
- is no longer a valid vertex descriptor.
- </TD>
- </TR>
- </TABLE>
- <P>
- </LI>
- </UL>
- <P>
- <H3>Complexity Guarantees</H3>
- <P>
- <UL>
- <LI>Edge insertion must be either amortized constant time or it
- can be <i>O(log(E/V))</i> if the insertion also checks to
- prevent the addition of parallel edges (which is a ``feature'' of
- some graph types).
- </LI>
- <LI>Edge removal is guaranteed to be <i>O(E)</i>.</LI>
- <LI>Vertex insertion is guaranteed to be amortized constant time.</LI>
- <LI>Clearing a vertex is <i>O(E + V)</i>.</LI>
- <LI>Vertex removal is <i>O(E + V)</i>.</LI>
- </UL>
- <H3>Models</H3>
- <UL>
- <LI><TT>adjacency_list</TT>
- </LI>
- </UL>
- <H3>Concept Checking Class</H3>
- <PRE>
- template <class G>
- struct MutableGraphConcept
- {
- typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
- void constraints() {
- v = add_vertex(g);
- clear_vertex(v, g);
- remove_vertex(v, g);
- e_b = add_edge(u, v, g);
- remove_edge(u, v, g);
- remove_edge(e, g);
- }
- G g;
- edge_descriptor e;
- std::pair<edge_descriptor, bool> e_b;
- typename boost::graph_traits<G>::vertex_descriptor u, v;
- typename boost::graph_traits<G>::out_edge_iterator iter;
- };
- template <class edge_descriptor>
- struct dummy_edge_predicate {
- bool operator()(const edge_descriptor& e) const {
- return false;
- }
- };
- template <class G>
- struct MutableIncidenceGraphConcept
- {
- void constraints() {
- BOOST_CONCEPT_ASSERT(( MutableGraph<G> ));
- remove_edge(iter, g);
- remove_out_edge_if(u, p, g);
- }
- G g;
- typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- typename boost::graph_traits<G>::vertex_descriptor u;
- typename boost::graph_traits<G>::out_edge_iterator iter;
- };
- template <class G>
- struct MutableBidirectionalGraphConcept
- {
- void constraints() {
- BOOST_CONCEPT_ASSERT(( MutableIncidenceGraph<G> ));
- remove_in_edge_if(u, p, g);
- }
- G g;
- typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- typename boost::graph_traits<G>::vertex_descriptor u;
- };
- template <class G>
- struct MutableEdgeListGraphConcept
- {
- void constraints() {
- BOOST_CONCEPT_ASSERT(( MutableGraph<G> ));
- remove_edge_if(p, g);
- }
- G g;
- typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- };
- </PRE>
- <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>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|