ceph/src/boost/libs/graph/doc/MutableGraph.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>MutableGraph</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 <H2><A NAME="sec:MutableGraph"></A>
  20 MutableGraph
  21 </H2>
  22
  23 A MutableGraph can be changed via the addition or removal of
  24 edges and vertices.
  25
  26 <H3>Refinement of</H3>
  27
  28 <a href="./Graph.html">Graph</a>
  29
  30 <h3>Notation</h3>
  31
  32 <Table>
  33 <TR>
  34 <TD><tt>G</tt></TD>
  35 <TD>A type that is a model of Graph.</TD>
  36 </TR>
  37
  38 <TR>
  39 <TD><tt>g</tt></TD>
  40 <TD>An object of type <tt>G</tt>.</TD>
  41 </TR>
  42
  43 <TR>
  44 <TD><tt>e</tt></TD>
  45 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
  46 </TR>
  47
  48 <TR>
  49 <TD><tt>u,v</tt></TD>
  50 <TD>are objects of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
  51 </TR>
  52
  53 <TR>
  54 <TD><tt>iter</tt></TD>
  55 <TD>is an object of type <tt>boost::graph_traits&lt;G&gt;::out_edge_iterator</tt>.</TD>
  56 </TR>
  57
  58 <TR>
  59 <TD><tt>p</tt></TD>
  60 <TD>is an object of a type that models <a
  61 href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>
  62 and whose argument type matches the <tt>edge_descriptor</tt> type.
  63 </TR>
  64
  65 </table>
  66
  67 <H3>Valid Expressions</H3>
  68
  69 <table border>
  70
  71 <tr>
  72 <TD><a name="sec:add-edge"><TT>add_edge(u,&nbsp;v,&nbsp;g)</TT></a></TD>
  73 <TD>
  74 Inserts the edge <i>(u,v)</i> into the graph, and returns an edge
  75 descriptor pointing to the new edge. If the graph disallows parallel
  76 edges, and the edge <i>(u,v)</i> is already in the graph, then the
  77 <tt>bool</tt> flag returned is <tt>false</tt> and the returned edge
  78 descriptor points to the already existing edge.  Note that for
  79 undirected graphs, <i>(u,v)</i> is the same edge as <i>(v,u)</i>, so
  80 after a call to the function <tt>add_edge()</tt>, this implies that
  81 edge <i>(u,v)</i> will appear in the out-edges of <i>u</i> and
  82 <i>(u,v)</i> (or equivalently <i>(v,u)</i>) will appear in the
  83 out-edges of <i>v</i>.  Put another way, <i>v</i> will be adjacent to
  84 <i>u</i> and <i>u</i> will be adjacent to <i>v</i>.
  85 <br>
  86 Return type: <TT>std::pair&lt;edge_descriptor, bool&gt;</TT>
  87 </TD>
  88 </tr>
  89
  90 <tr>
  91 <TD><a name="sec:remove_edge"><TT>remove_edge(u,&nbsp;v,&nbsp;g)</TT></a></TD>
  92 <TD>
  93 Remove the edge <i>(u,v)</i> from the graph. If the
  94 graph allows parallel edges this remove all occurrences of
  95 <i>(u,v)</i>.<br>
  96 Return type: <TT>void</TT><br>
  97 Precondition: <i>u</i> and <i>v</i> are vertices in the graph.<br>
  98 Postcondition: <i>(u,v)</i> is no longer in the edge set for
  99 <TT>g</TT>.<br>
 100 </TD>
 101 </TR>
 102
 103
 104 <tr>
 105 <TD><TT>remove_edge(e,&nbsp;g)</TT></TD>
 106 <TD>Remove the edge <i>e</i> from the graph.<br>
 107 Return type: <TT>void</TT><br>
 108 Precondition: <i>e</i> is an edge in the graph.<br>
 109 Postcondition: <i>e</i> is no longer in the edge set for <TT>g</TT>.
 110 </TD>
 111 </TR>
 112
 113 <tr>
 114 <TD><TT>remove_edge(iter,&nbsp;g)</TT></TD>
 115 <TD>Remove the edge pointed to be <tt>iter</tt> from the graph.  This
 116 expression is only required when the graph also models <a
 117 href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
 118 Return type: <TT>void</TT><br>
 119 Precondition: <tt>*iter</tt> is an edge in the graph.<br>
 120 Postcondition: <tt>*iter</tt> is no longer in the edge set for <TT>g</TT>.
 121 </TD>
 122 </TR>
 123
 124 <tr>
 125 <TD><TT>remove_edge_if(p,&nbsp;g)</TT></TD>
 126 <TD>Remove all the edges from graph <tt>g</tt> for which
 127 the predicate <tt>p</tt> returns true.<br>
 128 Return type: <TT>void</TT>
 129 </TD>
 130 </TR>
 131
 132 <tr>
 133 <TD><TT>remove_out_edge_if(u,&nbsp;p,&nbsp;g)</TT></TD>
 134 <TD>Remove all the out-edges of vertex <tt>u</tt> for which the
 135 predicate <tt>p</tt> returns true. This expression is only required
 136 when the graph also models <a
 137 href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
 138 Return type: <TT>void</TT>
 139 </TD>
 140 </TR>
 141
 142 <tr>
 143 <TD><TT>remove_in_edge_if(u,&nbsp;p,&nbsp;g)</TT></TD>
 144 <TD>Remove all the in-edges of vertex <tt>u</tt> for which the
 145 predicate <tt>p</tt> returns true. This expression is only required when the
 146 graph also models <a
 147 href="./BidirectionalGraph.html">BidirectionalGraph</a>.<br>
 148 Return type: <TT>void</TT>
 149 </TD>
 150 </TR>
 151
 152
 153 <tr>
 154 <TD><a name="sec:add-vertex"><TT>add_vertex(g)</TT></a></TD>
 155 <TD>
 156 Add a new vertex to the graph. The <TT>vertex_descriptor</TT> for the
 157 new vertex is returned.<br>
 158 Return type: <TT>vertex_descriptor</TT>
 159 </TD>
 160 </TR>
 161
 162
 163 <tr>
 164 <TD><TT>clear_vertex(u,&nbsp;g)</TT></TD>
 165 <TD>
 166 Remove all edges to and from vertex <tt>u</tt> from the graph.<br>
 167 Return type: <TT>void</TT><br>
 168 Precondition: <tt>u</tt> is a valid vertex descriptor of <TT>g</TT>.<br>
 169 Postcondition: <tt>u</tt> does not appear as a source or target of
 170 any edge in <TT>g</TT>.
 171 </TD>
 172 </TR>
 173
 174 <tr>
 175 <TD><a name="sec:remove-vertex"><TT>remove_vertex(u,&nbsp;g)</TT></a></TD>
 176 <TD>
 177 Remove <i>u</i> from the vertex set of the graph. Note that undefined
 178 behavior may result if there are edges remaining in the graph who's
 179 target is <i>u</i>. Typically the <TT>clear_vertex()</TT> function
 180 should be called first.<br>
 181 Return type: <TT>void</TT><br>
 182 Precondition: <TT>u</TT> is a valid vertex descriptor of <TT>g</TT>.<br>
 183 Postcondition: <TT>num_vertices(g)</TT> is one less, <TT>u</TT>
 184 no longer appears in the vertex set of the graph and it
 185 is no longer a valid vertex descriptor.
 186 </TD>
 187 </TR>
 188 </TABLE>
 189
 190 <P>
 191 </LI>
 192 </UL>
 193
 194 <P>
 195
 196 <H3>Complexity Guarantees</H3>
 197
 198 <P>
 199
 200 <UL>
 201 <LI>Edge insertion must be either amortized constant time or it
 202  can be <i>O(log(E/V))</i> if the insertion also checks to
 203   prevent the addition of parallel edges (which is a ``feature'' of
 204   some graph types).
 205 </LI>
 206 <LI>Edge removal is guaranteed to be <i>O(E)</i>.</LI>
 207 <LI>Vertex insertion is guaranteed to be amortized constant time.</LI>
 208 <LI>Clearing a vertex is <i>O(E + V)</i>.</LI>
 209 <LI>Vertex removal is <i>O(E + V)</i>.</LI>
 210 </UL>
 211
 212 <H3>Models</H3>
 213
 214 <UL>
 215 <LI><TT>adjacency_list</TT>
 216 </LI>
 217 </UL>
 218
 219
 220 <H3>Concept Checking Class</H3>
 221
 222 <PRE>
 223   template &lt;class G&gt;
 224   struct MutableGraphConcept
 225   {
 226     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
 227     void constraints() {
 228       v = add_vertex(g);
 229       clear_vertex(v, g);
 230       remove_vertex(v, g);
 231       e_b = add_edge(u, v, g);
 232       remove_edge(u, v, g);
 233       remove_edge(e, g);
 234     }
 235     G g;
 236     edge_descriptor e;
 237     std::pair&lt;edge_descriptor, bool&gt; e_b;
 238     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u, v;
 239     typename boost::graph_traits&lt;G&gt;::out_edge_iterator iter;
 240   };
 241
 242   template &lt;class edge_descriptor&gt;
 243   struct dummy_edge_predicate {
 244     bool operator()(const edge_descriptor& e) const {
 245       return false;
 246     }
 247   };
 248
 249   template &lt;class G&gt;
 250   struct MutableIncidenceGraphConcept
 251   {
 252     void constraints() {
 253       BOOST_CONCEPT_ASSERT(( MutableGraph&lt;G&gt; ));
 254       remove_edge(iter, g);
 255       remove_out_edge_if(u, p, g);
 256     }
 257     G g;
 258     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
 259     dummy_edge_predicate&lt;edge_descriptor&gt; p;
 260     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u;
 261     typename boost::graph_traits&lt;G&gt;::out_edge_iterator iter;
 262   };
 263
 264   template &lt;class G&gt;
 265   struct MutableBidirectionalGraphConcept
 266   {
 267     void constraints() {
 268       BOOST_CONCEPT_ASSERT(( MutableIncidenceGraph&lt;G&gt; ));
 269       remove_in_edge_if(u, p, g);
 270     }
 271     G g;
 272     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
 273     dummy_edge_predicate&lt;edge_descriptor&gt; p;
 274     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u;
 275   };
 276
 277   template &lt;class G&gt;
 278   struct MutableEdgeListGraphConcept
 279   {
 280     void constraints() {
 281       BOOST_CONCEPT_ASSERT(( MutableGraph&lt;G&gt; ));
 282       remove_edge_if(p, g);
 283     }
 284     G g;
 285     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
 286     dummy_edge_predicate&lt;edge_descriptor&gt; p;
 287   };
 288 </PRE>
 289
 290 <br>
 291 <HR>
 292 <TABLE>
 293 <TR valign=top>
 294 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 295 <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>)
 296 </TD></TR></TABLE>
 297
 298 </BODY>
 299 </HTML>