<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.sgi.com/tech/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>