williamr@2: // williamr@2: //======================================================================= williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: // williamr@2: #ifndef BOOST_GRAPH_CONCEPTS_HPP williamr@2: #define BOOST_GRAPH_CONCEPTS_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: template williamr@2: struct MultiPassInputIteratorConcept { williamr@2: void constraints() { williamr@2: function_requires< InputIteratorConcept >(); williamr@2: } williamr@2: }; williamr@2: williamr@2: template williamr@2: struct GraphConcept williamr@2: { williamr@2: typedef typename graph_traits::vertex_descriptor vertex_descriptor; williamr@2: typedef typename graph_traits::directed_category directed_category; williamr@2: typedef typename graph_traits::edge_parallel_category williamr@2: edge_parallel_category; williamr@2: typedef typename graph_traits::traversal_category williamr@2: traversal_category; williamr@2: void constraints() { williamr@2: function_requires< DefaultConstructibleConcept >(); williamr@2: function_requires< EqualityComparableConcept >(); williamr@2: function_requires< AssignableConcept >(); williamr@2: } williamr@2: G g; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct IncidenceGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: typedef typename graph_traits::out_edge_iterator williamr@2: out_edge_iterator; williamr@2: typedef typename graph_traits::traversal_category williamr@2: traversal_category; williamr@2: void constraints() { williamr@2: function_requires< GraphConcept >(); williamr@2: function_requires< MultiPassInputIteratorConcept >(); williamr@2: function_requires< DefaultConstructibleConcept >(); williamr@2: function_requires< EqualityComparableConcept >(); williamr@2: function_requires< AssignableConcept >(); williamr@2: function_requires< ConvertibleConcept >(); williamr@2: williamr@2: p = out_edges(u, g); williamr@2: n = out_degree(u, g); williamr@2: e = *p.first; williamr@2: u = source(e, g); williamr@2: v = target(e, g); williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: p = out_edges(u, cg); williamr@2: n = out_degree(u, cg); williamr@2: e = *p.first; williamr@2: u = source(e, cg); williamr@2: v = target(e, cg); williamr@2: } williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor u, v; williamr@2: typename graph_traits::edge_descriptor e; williamr@2: typename graph_traits::degree_size_type n; williamr@2: G g; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct BidirectionalGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::in_edge_iterator williamr@2: in_edge_iterator; williamr@2: typedef typename graph_traits::traversal_category williamr@2: traversal_category; williamr@2: void constraints() { williamr@2: function_requires< IncidenceGraphConcept >(); williamr@2: function_requires< MultiPassInputIteratorConcept >(); williamr@2: function_requires< ConvertibleConcept >(); williamr@2: williamr@2: p = in_edges(v, g); williamr@2: n = in_degree(v, g); williamr@2: e = *p.first; williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: p = in_edges(v, cg); williamr@2: n = in_degree(v, cg); williamr@2: e = *p.first; williamr@2: } williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor v; williamr@2: typename graph_traits::edge_descriptor e; williamr@2: typename graph_traits::degree_size_type n; williamr@2: G g; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct AdjacencyGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::adjacency_iterator williamr@2: adjacency_iterator; williamr@2: typedef typename graph_traits::traversal_category williamr@2: traversal_category; williamr@2: void constraints() { williamr@2: function_requires< GraphConcept >(); williamr@2: function_requires< MultiPassInputIteratorConcept >(); williamr@2: function_requires< ConvertibleConcept >(); williamr@2: williamr@2: p = adjacent_vertices(v, g); williamr@2: v = *p.first; williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: p = adjacent_vertices(v, cg); williamr@2: } williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor v; williamr@2: G g; williamr@2: }; williamr@2: williamr@2: // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if williamr@2: // you want to use vector_as_graph, it is! I'm sure the graph williamr@2: // library leaves these out all over the place. Probably a williamr@2: // redesign involving specializing a template with a static williamr@2: // member function is in order :( williamr@2: // williamr@2: // It is needed in order to allow us to write using boost::vertices as williamr@2: // needed for ADL when using vector_as_graph below. williamr@2: #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ williamr@2: && !BOOST_WORKAROUND(__GNUC__, <= 2) \ williamr@2: && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) williamr@2: # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK williamr@2: #endif williamr@2: williamr@2: #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK williamr@2: template williamr@2: typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); williamr@2: #endif williamr@2: williamr@2: template williamr@2: struct VertexListGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::vertex_iterator vertex_iterator; williamr@2: typedef typename graph_traits::vertices_size_type vertices_size_type; williamr@2: typedef typename graph_traits::traversal_category williamr@2: traversal_category; williamr@2: void constraints() { williamr@2: function_requires< GraphConcept >(); williamr@2: function_requires< MultiPassInputIteratorConcept >(); williamr@2: function_requires< ConvertibleConcept >(); williamr@2: williamr@2: #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK williamr@2: // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if williamr@2: // you want to use vector_as_graph, it is! I'm sure the graph williamr@2: // library leaves these out all over the place. Probably a williamr@2: // redesign involving specializing a template with a static williamr@2: // member function is in order :( williamr@2: using boost::vertices; williamr@2: #endif williamr@2: p = vertices(g); williamr@2: v = *p.first; williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK williamr@2: // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if williamr@2: // you want to use vector_as_graph, it is! I'm sure the graph williamr@2: // library leaves these out all over the place. Probably a williamr@2: // redesign involving specializing a template with a static williamr@2: // member function is in order :( williamr@2: using boost::vertices; williamr@2: #endif williamr@2: williamr@2: p = vertices(cg); williamr@2: v = *p.first; williamr@2: V = num_vertices(cg); williamr@2: } williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor v; williamr@2: G g; williamr@2: vertices_size_type V; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct EdgeListGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: typedef typename graph_traits::edge_iterator edge_iterator; williamr@2: typedef typename graph_traits::edges_size_type edges_size_type; williamr@2: typedef typename graph_traits::traversal_category williamr@2: traversal_category; williamr@2: void constraints() { williamr@2: function_requires< GraphConcept >(); williamr@2: function_requires< MultiPassInputIteratorConcept >(); williamr@2: function_requires< DefaultConstructibleConcept >(); williamr@2: function_requires< EqualityComparableConcept >(); williamr@2: function_requires< AssignableConcept >(); williamr@2: function_requires< ConvertibleConcept >(); williamr@2: williamr@2: p = edges(g); williamr@2: e = *p.first; williamr@2: u = source(e, g); williamr@2: v = target(e, g); williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: p = edges(cg); williamr@2: E = num_edges(cg); williamr@2: e = *p.first; williamr@2: u = source(e, cg); williamr@2: v = target(e, cg); williamr@2: } williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor u, v; williamr@2: typename graph_traits::edge_descriptor e; williamr@2: edges_size_type E; williamr@2: G g; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct VertexAndEdgeListGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< VertexListGraphConcept >(); williamr@2: function_requires< EdgeListGraphConcept >(); williamr@2: } williamr@2: }; williamr@2: williamr@2: // Where to put the requirement for this constructor? williamr@2: // G g(n_vertices); williamr@2: // Not in mutable graph, then LEDA graph's can't be models of williamr@2: // MutableGraph. williamr@2: williamr@2: template williamr@2: struct EdgeMutableGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: void constraints() { williamr@2: p = add_edge(u, v, g); williamr@2: remove_edge(u, v, g); williamr@2: remove_edge(e, g); williamr@2: clear_vertex(v, g); williamr@2: } williamr@2: G g; williamr@2: edge_descriptor e; williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor u, v; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct VertexMutableGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: v = add_vertex(g); williamr@2: remove_vertex(v, g); williamr@2: } williamr@2: G g; williamr@2: typename graph_traits::vertex_descriptor u, v; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct MutableGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< EdgeMutableGraphConcept >(); williamr@2: function_requires< VertexMutableGraphConcept >(); williamr@2: } williamr@2: }; williamr@2: williamr@2: template williamr@2: struct dummy_edge_predicate { williamr@2: bool operator()(const edge_descriptor&) const { williamr@2: return false; williamr@2: } williamr@2: }; williamr@2: williamr@2: template williamr@2: struct MutableIncidenceGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< MutableGraphConcept >(); williamr@2: remove_edge(iter, g); williamr@2: remove_out_edge_if(u, p, g); williamr@2: } williamr@2: G g; williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: dummy_edge_predicate p; williamr@2: typename boost::graph_traits::vertex_descriptor u; williamr@2: typename boost::graph_traits::out_edge_iterator iter; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct MutableBidirectionalGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< MutableIncidenceGraphConcept >(); williamr@2: remove_in_edge_if(u, p, g); williamr@2: } williamr@2: G g; williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: dummy_edge_predicate p; williamr@2: typename boost::graph_traits::vertex_descriptor u; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct MutableEdgeListGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< EdgeMutableGraphConcept >(); williamr@2: remove_edge_if(p, g); williamr@2: } williamr@2: G g; williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: dummy_edge_predicate p; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct VertexMutablePropertyGraphConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< VertexMutableGraphConcept >(); williamr@2: v = add_vertex(vp, g); williamr@2: } williamr@2: G g; williamr@2: typename graph_traits::vertex_descriptor v; williamr@2: typename vertex_property::type vp; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct EdgeMutablePropertyGraphConcept williamr@2: { williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: void constraints() { williamr@2: function_requires< EdgeMutableGraphConcept >(); williamr@2: p = add_edge(u, v, ep, g); williamr@2: } williamr@2: G g; williamr@2: std::pair p; williamr@2: typename graph_traits::vertex_descriptor u, v; williamr@2: typename edge_property::type ep; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct AdjacencyMatrixConcept williamr@2: { williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: void constraints() { williamr@2: function_requires< GraphConcept >(); williamr@2: williamr@2: p = edge(u, v, g); williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: p = edge(u, v, cg); williamr@2: } williamr@2: typename graph_traits::vertex_descriptor u, v; williamr@2: std::pair p; williamr@2: G g; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct ReadablePropertyGraphConcept williamr@2: { williamr@2: typedef typename property_map::const_type const_Map; williamr@2: void constraints() { williamr@2: function_requires< GraphConcept >(); williamr@2: function_requires< ReadablePropertyMapConcept >(); williamr@2: williamr@2: const_constraints(g); williamr@2: } williamr@2: void const_constraints(const G& cg) { williamr@2: const_Map pmap = get(Property(), cg); williamr@2: pval = get(Property(), cg, x); williamr@2: ignore_unused_variable_warning(pmap); williamr@2: } williamr@2: G g; williamr@2: X x; williamr@2: typename property_traits::value_type pval; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct PropertyGraphConcept williamr@2: { williamr@2: typedef typename property_map::type Map; williamr@2: void constraints() { williamr@2: function_requires< ReadablePropertyGraphConcept >(); williamr@2: function_requires< ReadWritePropertyMapConcept >(); williamr@2: williamr@2: Map pmap = get(Property(), g); williamr@2: pval = get(Property(), g, x); williamr@2: put(Property(), g, x, pval); williamr@2: ignore_unused_variable_warning(pmap); williamr@2: } williamr@2: G g; williamr@2: X x; williamr@2: typename property_traits::value_type pval; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct LvaluePropertyGraphConcept williamr@2: { williamr@2: typedef typename property_map::type Map; williamr@2: typedef typename property_map::const_type const_Map; williamr@2: void constraints() { williamr@2: function_requires< ReadablePropertyGraphConcept >(); williamr@2: function_requires< LvaluePropertyMapConcept >(); williamr@2: williamr@2: pval = get(Property(), g, x); williamr@2: put(Property(), g, x, pval); williamr@2: } williamr@2: G g; williamr@2: X x; williamr@2: typename property_traits::value_type pval; williamr@2: }; williamr@2: williamr@2: // This needs to move out of the graph library williamr@2: template williamr@2: struct BufferConcept williamr@2: { williamr@2: void constraints() { williamr@2: b.push(t); williamr@2: b.pop(); williamr@2: typename B::value_type& v = b.top(); williamr@2: const_constraints(b); williamr@2: ignore_unused_variable_warning(v); williamr@2: } williamr@2: void const_constraints(const B& cb) { williamr@2: const typename B::value_type& v = cb.top(); williamr@2: n = cb.size(); williamr@2: bool e = cb.empty(); williamr@2: ignore_unused_variable_warning(v); williamr@2: ignore_unused_variable_warning(e); williamr@2: } williamr@2: typename B::size_type n; williamr@2: typename B::value_type t; williamr@2: B b; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct ColorValueConcept williamr@2: { williamr@2: void constraints() { williamr@2: function_requires< EqualityComparableConcept >(); williamr@2: function_requires< DefaultConstructibleConcept >(); williamr@2: williamr@2: c = color_traits::white(); williamr@2: c = color_traits::gray(); williamr@2: c = color_traits::black(); williamr@2: } williamr@2: C c; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct BasicMatrixConcept williamr@2: { williamr@2: void constraints() { williamr@2: V& elt = A[i][j]; williamr@2: const_constraints(A); williamr@2: ignore_unused_variable_warning(elt); williamr@2: } williamr@2: void const_constraints(const M& cA) { williamr@2: const V& elt = cA[i][j]; williamr@2: ignore_unused_variable_warning(elt); williamr@2: } williamr@2: M A; williamr@2: I i, j; williamr@2: }; williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif /* BOOST_GRAPH_CONCEPTS_H */