Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/MutableGraph.html @ 14

Last change on this file since 14 was 12, checked in by landauf, 17 years ago

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