MutableGraph

A MutableGraph can be changed via the addition or removal of edges and vertices.

Refinement of

Graph

Notation

G

A type that is a model of Graph.

g

An object of type G.

e

An object of type boost::graph_traits<G>::edge_descriptor.

u,v

are objects of type boost::graph_traits<G>::vertex_descriptor.

iter

is an object of type boost::graph_traits<G>::out_edge_iterator.

p

is an object of a type that models Predicate and whose argument type matches the edge_descriptor type.

Valid Expressions

add_edge(u, v, g)

Inserts the edge (u,v) into the graph, and returns an edge descriptor pointing to the new edge. If the graph disallows parallel edges, and the edge (u,v) is already in the graph, then the bool flag returned is false and the returned edge descriptor points to the already existing edge. Note that for undirected graphs, (u,v) is the same edge as (v,u), so after a call to the function add_edge(), this implies that edge (u,v) will appear in the out-edges of u and (u,v) (or equivalently (v,u)) will appear in the out-edges of v. Put another way, v will be adjacent to u and u will be adjacent to v.
Return type: std::pair<edge_descriptor, bool>

remove_edge(u, v, g)

Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences of (u,v).
Return type: void
Precondition: u and v are vertices in the graph.
Postcondition: (u,v) is no longer in the edge set for g.

remove_edge(e, g)

Remove the edge e from the graph.
Return type: void
Precondition: e is an edge in the graph.
Postcondition: e is no longer in the edge set for g.

remove_edge(iter, g)

Remove the edge pointed to be iter from the graph. This expression is only required when the graph also models IncidenceGraph.
Return type: void
Precondition: *iter is an edge in the graph.
Postcondition: *iter is no longer in the edge set for g.

remove_edge_if(p, g)

Remove all the edges from graph g for which the predicate p returns true.
Return type: void

remove_out_edge_if(u, p, g)

Remove all the out-edges of vertex u for which the predicate p returns true. This expression is only required when the graph also models IncidenceGraph.
Return type: void

remove_in_edge_if(u, p, g)

Remove all the in-edges of vertex u for which the predicate p returns true. This expression is only required when the graph also models BidirectionalGraph.
Return type: void

add_vertex(g)

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

clear_vertex(u, g)

Remove all edges to and from vertex u from the graph.
Return type: void
Precondition: u is a valid vertex descriptor of g.
Postcondition: u does not appear as a source or target of any edge in g.

remove_vertex(u, g)

Remove u from the vertex set of the graph. Note that undefined behavior may result if there are edges remaining in the graph who’s target is u. Typically the clear_vertex() function should be called first.
Return type: void
Precondition: u is a valid vertex descriptor of g.
Postcondition: 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

Edge insertion must be either amortized constant time or it can be O(log(E/V)) if the insertion also checks to prevent the addition of parallel edges (which is a "feature" of some graph types).
Edge removal is guaranteed to be O(E).
Vertex insertion is guaranteed to be amortized constant time.
Clearing a vertex is O(E + V).
Vertex removal is O(E + V).

Models

adjacency_list

Concept Checking Class

  template <class G>
  struct MutableGraphConcept
  {
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      v = add_vertex(g);
      clear_vertex(v, g);
      remove_vertex(v, g);
      e_b = add_edge(u, v, g);
      remove_edge(u, v, g);
      remove_edge(e, g);
    }
    G g;
    edge_descriptor e;
    std::pair<edge_descriptor, bool> e_b;
    typename boost::graph_traits<G>::vertex_descriptor u, v;
    typename boost::graph_traits<G>::out_edge_iterator iter;
  };

  template <class edge_descriptor>
  struct dummy_edge_predicate {
    bool operator()(const edge_descriptor& e) const {
      return false;
    }
  };

  template <class G>
  struct MutableIncidenceGraphConcept
  {
    void constraints() {
      BOOST_CONCEPT_ASSERT(( MutableGraph<G> ));
      remove_edge(iter, g);
      remove_out_edge_if(u, p, g);
    }
    G g;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
    typename boost::graph_traits<G>::vertex_descriptor u;
    typename boost::graph_traits<G>::out_edge_iterator iter;
  };

  template <class G>
  struct MutableBidirectionalGraphConcept
  {
    void constraints() {
      BOOST_CONCEPT_ASSERT(( MutableIncidenceGraph<G> ));
      remove_in_edge_if(u, p, g);
    }
    G g;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
    typename boost::graph_traits<G>::vertex_descriptor u;
  };

  template <class G>
  struct MutableEdgeListGraphConcept
  {
    void constraints() {
      BOOST_CONCEPT_ASSERT(( MutableGraph<G> ));
      remove_edge_if(p, g);
    }
    G g;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
  };

Edit this Page