Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/MutableGraph.html @ 45

Last change on this file since 45 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 8.0 KB
Line 
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&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
61href="http://www.sgi.com/tech/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,&nbsp;v,&nbsp;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&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>
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,&nbsp;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,&nbsp;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,&nbsp;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,&nbsp;p,&nbsp;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,&nbsp;p,&nbsp;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,&nbsp;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,&nbsp;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 &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      function_requires&lt; MutableGraph&lt;G&gt; &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      function_requires&lt; MutableIncidenceGraph&lt;G&gt; &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      function_requires&lt; MutableGraph&lt;G&gt; &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="../../../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> 
Note: See TracBrowser for help on using the repository browser.