1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek 2001
-
- 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>Vertex Mutable Graph</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="concept:VertexMutableGraph">
- Vertex Mutable Graph
- </H2>
- A vertex mutable graph can be changed by adding or removing
- vertices. The memory management is the responsibility of the graph
- implementation. The graph user need only make calls to
- <TT>add_vertex</TT> and <TT>remove_vertex</TT> and the graph
- implementation does the rest.
- <H3>Refinement of</H3>
- <a href="./Graph.html">Graph</a> and <a
- href="http://www.boost.org/sgi/stl/DefaultConstructible.html">DefaultConstructible</a>
- <H3>Associated Types</H3>
- No additional associated types.
- <h3>Valid Expressions</h3>
- <ul>
- <li><a name="sec:add_vertex"><TT>add_vertex(g)</TT></a>
- <b>returns</b> <TT>vertex_descriptor</TT>
- <br><br>
- <b>Semantics:</b> Add a new vertex to the graph. The
- <TT>vertex_descriptor</TT> for the new vertex is returned.<br>
- </li>
- <li><a name="sec:remove_vertex"><tt>remove_vertex(u, g)</tt></a>
- <b>returns</b> <tt>void</tt><br><br>
- <b> Semantics:</b> Remove <i>u</i> from the vertex set of the graph.
- <br>
- <b> Preconditions:</b> <i>u</i> is a valid vertex descriptor of graph <i>g</i>
- and there are no edges incident to vertex <i>u</i>. The function
- <TT>clear_vertex</TT> can be used to remove all incident edges.
- <br>
- <b> Postconditions: </b> <TT>num_vertices(g)</TT> is one less; <i>u</i>
- no longer appears in the vertex set of the graph and it
- is no longer a valid vertex descriptor.
- </li>
- </ul>
- <H3>Complexity guarantees</H3>
- <ul>
- <li> Vertex insertion is guaranteed to be amortized constant time.
-
- <li> Vertex removal is at most <TT>O(|E| + |V|)</TT>.
- </ul>
- <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>)
- <A HREF="http://www.boost.org/people/jeremy_siek.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|