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> 20MutableGraph 21</H2> 22 23A MutableGraph can be changed via the addition or removal of 24edges 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<G>::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<G>::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<G>::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 61href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a> 62and 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, v, g)</TT></a></TD> 73<TD> 74Inserts the edge <i>(u,v)</i> into the graph, and returns an edge 75descriptor pointing to the new edge. If the graph disallows parallel 76edges, 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 78descriptor points to the already existing edge. Note that for 79undirected graphs, <i>(u,v)</i> is the same edge as <i>(v,u)</i>, so 80after a call to the function <tt>add_edge()</tt>, this implies that 81edge <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 83out-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> 86Return type: <TT>std::pair<edge_descriptor, bool></TT> 87</TD> 88</tr> 89 90<tr> 91<TD><a name="sec:remove_edge"><TT>remove_edge(u, v, g)</TT></a></TD> 92<TD> 93Remove the edge <i>(u,v)</i> from the graph. If the 94graph allows parallel edges this remove all occurrences of 95<i>(u,v)</i>.<br> 96Return type: <TT>void</TT><br> 97Precondition: <i>u</i> and <i>v</i> are vertices in the graph.<br> 98Postcondition: <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, g)</TT></TD> 106<TD>Remove the edge <i>e</i> from the graph.<br> 107Return type: <TT>void</TT><br> 108Precondition: <i>e</i> is an edge in the graph.<br> 109Postcondition: <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, g)</TT></TD> 115<TD>Remove the edge pointed to be <tt>iter</tt> from the graph. This 116expression is only required when the graph also models <a 117href="./IncidenceGraph.html">IncidenceGraph</a>.<br> 118Return type: <TT>void</TT><br> 119Precondition: <tt>*iter</tt> is an edge in the graph.<br> 120Postcondition: <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, g)</TT></TD> 126<TD>Remove all the edges from graph <tt>g</tt> for which 127the predicate <tt>p</tt> returns true.<br> 128Return type: <TT>void</TT> 129</TD> 130</TR> 131 132<tr> 133<TD><TT>remove_out_edge_if(u, p, g)</TT></TD> 134<TD>Remove all the out-edges of vertex <tt>u</tt> for which the 135predicate <tt>p</tt> returns true. This expression is only required 136when the graph also models <a 137href="./IncidenceGraph.html">IncidenceGraph</a>.<br> 138Return type: <TT>void</TT> 139</TD> 140</TR> 141 142<tr> 143<TD><TT>remove_in_edge_if(u, p, g)</TT></TD> 144<TD>Remove all the in-edges of vertex <tt>u</tt> for which the 145predicate <tt>p</tt> returns true. This expression is only required when the 146graph also models <a 147href="./BidirectionalGraph.html">BidirectionalGraph</a>.<br> 148Return 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> 156Add a new vertex to the graph. The <TT>vertex_descriptor</TT> for the 157new vertex is returned.<br> 158Return type: <TT>vertex_descriptor</TT> 159</TD> 160</TR> 161 162 163<tr> 164<TD><TT>clear_vertex(u, g)</TT></TD> 165<TD> 166Remove all edges to and from vertex <tt>u</tt> from the graph.<br> 167Return type: <TT>void</TT><br> 168Precondition: <tt>u</tt> is a valid vertex descriptor of <TT>g</TT>.<br> 169Postcondition: <tt>u</tt> does not appear as a source or target of 170any edge in <TT>g</TT>. 171</TD> 172</TR> 173 174<tr> 175<TD><a name="sec:remove-vertex"><TT>remove_vertex(u, g)</TT></a></TD> 176<TD> 177Remove <i>u</i> from the vertex set of the graph. Note that undefined 178behavior may result if there are edges remaining in the graph who's 179target is <i>u</i>. Typically the <TT>clear_vertex()</TT> function 180should be called first.<br> 181Return type: <TT>void</TT><br> 182Precondition: <TT>u</TT> is a valid vertex descriptor of <TT>g</TT>.<br> 183Postcondition: <TT>num_vertices(g)</TT> is one less, <TT>u</TT> 184no longer appears in the vertex set of the graph and it 185is 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 <class G> 224 struct MutableGraphConcept 225 { 226 typedef typename boost::graph_traits<G>::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<edge_descriptor, bool> e_b; 238 typename boost::graph_traits<G>::vertex_descriptor u, v; 239 typename boost::graph_traits<G>::out_edge_iterator iter; 240 }; 241 242 template <class edge_descriptor> 243 struct dummy_edge_predicate { 244 bool operator()(const edge_descriptor& e) const { 245 return false; 246 } 247 }; 248 249 template <class G> 250 struct MutableIncidenceGraphConcept 251 { 252 void constraints() { 253 BOOST_CONCEPT_ASSERT(( MutableGraph<G> )); 254 remove_edge(iter, g); 255 remove_out_edge_if(u, p, g); 256 } 257 G g; 258 typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; 259 dummy_edge_predicate<edge_descriptor> p; 260 typename boost::graph_traits<G>::vertex_descriptor u; 261 typename boost::graph_traits<G>::out_edge_iterator iter; 262 }; 263 264 template <class G> 265 struct MutableBidirectionalGraphConcept 266 { 267 void constraints() { 268 BOOST_CONCEPT_ASSERT(( MutableIncidenceGraph<G> )); 269 remove_in_edge_if(u, p, g); 270 } 271 G g; 272 typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; 273 dummy_edge_predicate<edge_descriptor> p; 274 typename boost::graph_traits<G>::vertex_descriptor u; 275 }; 276 277 template <class G> 278 struct MutableEdgeListGraphConcept 279 { 280 void constraints() { 281 BOOST_CONCEPT_ASSERT(( MutableGraph<G> )); 282 remove_edge_if(p, g); 283 } 284 G g; 285 typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; 286 dummy_edge_predicate<edge_descriptor> p; 287 }; 288</PRE> 289 290<br> 291<HR> 292<TABLE> 293<TR valign=top> 294<TD nowrap>Copyright © 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> 300
