http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/graph_concepts.hpp

// //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // #ifndef BOOST_GRAPH_CONCEPTS_HPP #define BOOST_GRAPH_CONCEPTS_HPP #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map.hpp> #include <boost/graph/properties.hpp> #include <boost/concept_check.hpp> #include <boost/detail/workaround.hpp> namespace boost { template <class T> struct MultiPassInputIteratorConcept { void constraints() { function_requires< InputIteratorConcept<T> >(); } }; template <class G> struct GraphConcept { typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor; typedef typename graph_traits<G>::directed_category directed_category; typedef typename graph_traits<G>::edge_parallel_category edge_parallel_category; typedef typename graph_traits<G>::traversal_category traversal_category; void constraints() { function_requires< DefaultConstructibleConcept<vertex_descriptor> >(); function_requires< EqualityComparableConcept<vertex_descriptor> >(); function_requires< AssignableConcept<vertex_descriptor> >(); } G g; }; template <class G> struct IncidenceGraphConcept { typedef typename graph_traits<G>::edge_descriptor edge_descriptor; typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator; typedef typename graph_traits<G>::traversal_category traversal_category; void constraints() { function_requires< GraphConcept<G> >(); function_requires< MultiPassInputIteratorConcept<out_edge_iterator> >(); function_requires< DefaultConstructibleConcept<edge_descriptor> >(); function_requires< EqualityComparableConcept<edge_descriptor> >(); function_requires< AssignableConcept<edge_descriptor> >(); function_requires< ConvertibleConcept<traversal_category, incidence_graph_tag> >(); p = out_edges(u, g); n = out_degree(u, g); e = *p.first; u = source(e, g); v = target(e, g); const_constraints(g); } void const_constraints(const G& cg) { p = out_edges(u, cg); n = out_degree(u, cg); e = *p.first; u = source(e, cg); v = target(e, cg); } std::pair<out_edge_iterator, out_edge_iterator> p; typename graph_traits<G>::vertex_descriptor u, v; typename graph_traits<G>::edge_descriptor e; typename graph_traits<G>::degree_size_type n; G g; }; template <class G> struct BidirectionalGraphConcept { typedef typename graph_traits<G>::in_edge_iterator in_edge_iterator; typedef typename graph_traits<G>::traversal_category traversal_category; void constraints() { function_requires< IncidenceGraphConcept<G> >(); function_requires< MultiPassInputIteratorConcept<in_edge_iterator> >(); function_requires< ConvertibleConcept<traversal_category, bidirectional_graph_tag> >(); p = in_edges(v, g); n = in_degree(v, g); e = *p.first; const_constraints(g); } void const_constraints(const G& cg) { p = in_edges(v, cg); n = in_degree(v, cg); e = *p.first; } std::pair<in_edge_iterator, in_edge_iterator> p; typename graph_traits<G>::vertex_descriptor v; typename graph_traits<G>::edge_descriptor e; typename graph_traits<G>::degree_size_type n; G g; }; template <class G> struct AdjacencyGraphConcept { typedef typename graph_traits<G>::adjacency_iterator adjacency_iterator; typedef typename graph_traits<G>::traversal_category traversal_category; void constraints() { function_requires< GraphConcept<G> >(); function_requires< MultiPassInputIteratorConcept<adjacency_iterator> >(); function_requires< ConvertibleConcept<traversal_category, adjacency_graph_tag> >(); p = adjacent_vertices(v, g); v = *p.first; const_constraints(g); } void const_constraints(const G& cg) { p = adjacent_vertices(v, cg); } std::pair<adjacency_iterator,adjacency_iterator> p; typename graph_traits<G>::vertex_descriptor v; G g; }; // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if // you want to use vector_as_graph, it is! I'm sure the graph // library leaves these out all over the place. Probably a // redesign involving specializing a template with a static // member function is in order :( // // It is needed in order to allow us to write using boost::vertices as // needed for ADL when using vector_as_graph below. #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ && !BOOST_WORKAROUND(__GNUC__, <= 2) \ && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK #endif #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK template <class T> typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); #endif template <class G> struct VertexListGraphConcept { typedef typename graph_traits<G>::vertex_iterator vertex_iterator; typedef typename graph_traits<G>::vertices_size_type vertices_size_type; typedef typename graph_traits<G>::traversal_category traversal_category; void constraints() { function_requires< GraphConcept<G> >(); function_requires< MultiPassInputIteratorConcept<vertex_iterator> >(); function_requires< ConvertibleConcept<traversal_category, vertex_list_graph_tag> >(); #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if // you want to use vector_as_graph, it is! I'm sure the graph // library leaves these out all over the place. Probably a // redesign involving specializing a template with a static // member function is in order :( using boost::vertices; #endif p = vertices(g); v = *p.first; const_constraints(g); } void const_constraints(const G& cg) { #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if // you want to use vector_as_graph, it is! I'm sure the graph // library leaves these out all over the place. Probably a // redesign involving specializing a template with a static // member function is in order :( using boost::vertices; #endif p = vertices(cg); v = *p.first; V = num_vertices(cg); } std::pair<vertex_iterator,vertex_iterator> p; typename graph_traits<G>::vertex_descriptor v; G g; vertices_size_type V; }; template <class G> struct EdgeListGraphConcept { typedef typename graph_traits<G>::edge_descriptor edge_descriptor; typedef typename graph_traits<G>::edge_iterator edge_iterator; typedef typename graph_traits<G>::edges_size_type edges_size_type; typedef typename graph_traits<G>::traversal_category traversal_category; void constraints() { function_requires< GraphConcept<G> >(); function_requires< MultiPassInputIteratorConcept<edge_iterator> >(); function_requires< DefaultConstructibleConcept<edge_descriptor> >(); function_requires< EqualityComparableConcept<edge_descriptor> >(); function_requires< AssignableConcept<edge_descriptor> >(); function_requires< ConvertibleConcept<traversal_category, edge_list_graph_tag> >(); p = edges(g); e = *p.first; u = source(e, g); v = target(e, g); const_constraints(g); } void const_constraints(const G& cg) { p = edges(cg); E = num_edges(cg); e = *p.first; u = source(e, cg); v = target(e, cg); } std::pair<edge_iterator,edge_iterator> p; typename graph_traits<G>::vertex_descriptor u, v; typename graph_traits<G>::edge_descriptor e; edges_size_type E; G g; }; 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& cg) { p = edge(u, v, cg); } 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& cg) { const_Map pmap = get(Property(), cg); pval = get(Property(), cg, 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& cb) { const typename B::value_type& v = cb.top(); n = cb.size(); bool e = cb.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& cA) { const V& elt = cA[i][j]; ignore_unused_variable_warning(elt); } M A; I i, j; }; } // namespace boost #endif /* BOOST_GRAPH_CONCEPTS_H */