graph_concepts.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 509 行 · 第 1/2 页

  template <class G>
  struct VertexAndEdgeListGraphConcept
  {
    void constraints() {
      function_requires< VertexListGraphConcept<G> >();    
      function_requires< EdgeListGraphConcept<G> >();
    }
  };

  // Where to put the requirement for this constructor?
  //      G g(n_vertices);
  // Not in mutable graph, then LEDA graph's can't be models of
  // MutableGraph.

  template <class G>
  struct EdgeMutableGraphConcept
  {
    typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      p = add_edge(u, v, g);
      remove_edge(u, v, g);
      remove_edge(e, g);
      clear_vertex(v, g);
    }
    G g;
    edge_descriptor e;
    std::pair<edge_descriptor, bool> p;
    typename graph_traits<G>::vertex_descriptor u, v;
  };

  template <class G>
  struct VertexMutableGraphConcept
  {
    void constraints() {
      v = add_vertex(g);
      remove_vertex(v, g);
    }
    G g;
    typename graph_traits<G>::vertex_descriptor u, v;
  };

  template <class G>
  struct MutableGraphConcept
  {
    void constraints() {
      function_requires< EdgeMutableGraphConcept<G> >();
      function_requires< VertexMutableGraphConcept<G> >();
    }
  };

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

  template <class G>
  struct MutableIncidenceGraphConcept
  {
    void constraints() {
      function_requires< MutableGraphConcept<G> >();
      remove_edge(iter, g);
      remove_out_edge_if(u, p, g);
    }
    G g;
    typedef typename 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() {
      function_requires< MutableIncidenceGraphConcept<G> >();
      remove_in_edge_if(u, p, g);
    }
    G g;
    typedef typename 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() {
      function_requires< EdgeMutableGraphConcept<G> >();
      remove_edge_if(p, g);
    }
    G g;
    typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
  };

  template <class G>
  struct VertexMutablePropertyGraphConcept
  {
    void constraints() {
      function_requires< VertexMutableGraphConcept<G> >();
      v = add_vertex(vp, g);
    }
    G g;
    typename graph_traits<G>::vertex_descriptor v;
    typename vertex_property<G>::type vp;
  };

  template <class G>
  struct EdgeMutablePropertyGraphConcept
  {
    typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      function_requires< EdgeMutableGraphConcept<G> >();
      p = add_edge(u, v, ep, g);
    }
    G g;
    std::pair<edge_descriptor, bool> p;
    typename graph_traits<G>::vertex_descriptor u, v;
    typename edge_property<G>::type ep;
  };

  template <class G>
  struct AdjacencyMatrixConcept
  {
    typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      function_requires< GraphConcept<G> >();
      
      p = edge(u, v, g);
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = edge(u, v, g);
    }
    typename graph_traits<G>::vertex_descriptor u, v;
    std::pair<edge_descriptor, bool> p;
    G g;
  };

  template <class G, class X, class Property>
  struct ReadablePropertyGraphConcept
  {
    typedef typename property_map<G, Property>::const_type const_Map;
    void constraints() {
      function_requires< GraphConcept<G> >();
      function_requires< ReadablePropertyMapConcept<const_Map, X> >();

      const_constraints(g);
    }
    void const_constraints(const G& g) {
      const_Map pmap = get(Property(), g);
      pval = get(Property(), g, x);
      ignore_unused_variable_warning(pmap);
    }
    G g;
    X x;
    typename property_traits<const_Map>::value_type pval;
  };

  template <class G, class X, class Property>
  struct PropertyGraphConcept
  {
    typedef typename property_map<G, Property>::type Map;
    void constraints() {
      function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
      function_requires< ReadWritePropertyMapConcept<Map, X> >();

      Map pmap = get(Property(), g);
      pval = get(Property(), g, x);
      put(Property(), g, x, pval);
      ignore_unused_variable_warning(pmap);
    }
    G g;
    X x;
    typename property_traits<Map>::value_type pval;
  };

  template <class G, class X, class Property>
  struct LvaluePropertyGraphConcept
  {
    typedef typename property_map<G, Property>::type Map;
    typedef typename property_map<G, Property>::const_type const_Map;
    void constraints() {
      function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
      function_requires< LvaluePropertyMapConcept<const_Map, X> >();

      pval = get(Property(), g, x);
      put(Property(), g, x, pval);
    }
    G g;
    X x;
    typename property_traits<Map>::value_type pval;
  };

  // This needs to move out of the graph library
  template <class B>
  struct BufferConcept
  {
    void constraints() {
      b.push(t);
      b.pop();
      typename B::value_type& v = b.top();
      const_constraints(b);
      ignore_unused_variable_warning(v);
    }
    void const_constraints(const B& b) {
      const typename B::value_type& v = b.top();
      n = b.size();
      bool e = b.empty();
      ignore_unused_variable_warning(v);
      ignore_unused_variable_warning(e);
    }
    typename B::size_type n;
    typename B::value_type t;
    B b;
  };

  template <class C>
  struct ColorValueConcept
  {
    void constraints() {
      function_requires< EqualityComparableConcept<C> >();
      function_requires< DefaultConstructibleConcept<C> >();

      c = color_traits<C>::white();
      c = color_traits<C>::gray();
      c = color_traits<C>::black();
    }
    C c;
  };

  template <class M, class I, class V>
  struct BasicMatrixConcept
  {
    void constraints() {
      V& elt = A[i][j];
      const_constraints(A);
      ignore_unused_variable_warning(elt);      
    }
    void const_constraints(const M& A) {
      const V& elt = A[i][j];
      ignore_unused_variable_warning(elt);      
    }
    M A;
    I i, j;
  };

} // namespace boost

#endif /* BOOST_GRAPH_CONCEPTS_H */