Vertex Mutable Graph

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 add_vertex and remove_vertex and the graph implementation does the rest.

Graph and DefaultConstructible

Associated Types

No additional associated types.

Valid Expressions

add_vertex(g) returns vertex_descriptor

Semantics: Add a new vertex to the graph. The vertex_descriptor for the new vertex is returned.

remove_vertex(u, g) returns void

Semantics: Remove u from the vertex set of the graph.
Preconditions: u is a valid vertex descriptor of graph g and there are no edges incident to vertex u. The function clear_vertex can be used to remove all incident edges.
Postconditions: num_vertices(g) is one less; u no longer appears in the vertex set of the graph and it is no longer a valid vertex descriptor.

Complexity guarantees

Vertex insertion is guaranteed to be amortized constant time.
Vertex removal is at most O(|E| + |V|).

Vertex Mutable Graph