MutableGraph

MutableGraph

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

Refinement of

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;
  };

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)