Vertex Mutable Graph

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|).