boost_1_45_0/libs/graph/doc/MutableGraph.html - nest-learning-thermostat/5.0/boost - Git at Google

 <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&lt;G&gt;::edge_descriptor</tt>.</TD>
 </TR>

 <TR>
 <TD><tt>u,v</tt></TD>
 <TD>are objects of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
 </TR>

 <TR>
 <TD><tt>iter</tt></TD>
 <TD>is an object of type <tt>boost::graph_traits&lt;G&gt;::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.sgi.com/tech/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,&nbsp;v,&nbsp;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&lt;edge_descriptor, bool&gt;</TT>
 </TD>
 </tr>

 <tr>
 <TD><a name="sec:remove_edge"><TT>remove_edge(u,&nbsp;v,&nbsp;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,&nbsp;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,&nbsp;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,&nbsp;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,&nbsp;p,&nbsp;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,&nbsp;p,&nbsp;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,&nbsp;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,&nbsp;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 &lt;class G&gt;
   struct MutableGraphConcept
   {
     typedef typename boost::graph_traits&lt;G&gt;::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&lt;edge_descriptor, bool&gt; e_b;
     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u, v;
     typename boost::graph_traits&lt;G&gt;::out_edge_iterator iter;
   };

   template &lt;class edge_descriptor&gt;
   struct dummy_edge_predicate {
     bool operator()(const edge_descriptor& e) const {
       return false;
     }
   };

   template &lt;class G&gt;
   struct MutableIncidenceGraphConcept
   {
     void constraints() {
       function_requires&lt; MutableGraph&lt;G&gt; &gt;();
       remove_edge(iter, g);
       remove_out_edge_if(u, p, g);
     }
     G g;
     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
     dummy_edge_predicate&lt;edge_descriptor&gt; p;
     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u;
     typename boost::graph_traits&lt;G&gt;::out_edge_iterator iter;
   };

   template &lt;class G&gt;
   struct MutableBidirectionalGraphConcept
   {
     void constraints() {
       function_requires&lt; MutableIncidenceGraph&lt;G&gt; &gt;();
       remove_in_edge_if(u, p, g);
     }
     G g;
     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
     dummy_edge_predicate&lt;edge_descriptor&gt; p;
     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u;
   };

   template &lt;class G&gt;
   struct MutableEdgeListGraphConcept
   {
     void constraints() {
       function_requires&lt; MutableGraph&lt;G&gt; &gt;();
       remove_edge_if(p, g);
     }
     G g;
     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
     dummy_edge_predicate&lt;edge_descriptor&gt; p;
   };
 </PRE>

 <br>
 <HR>
 <TABLE>
 <TR valign=top>
 <TD nowrap>Copyright &copy; 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>
	<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.sgi.com/tech/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() {
	function_requires< 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() {
	function_requires< 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() {
	function_requires< 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>