123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298 |
- //=======================================================================
- // Copyright 2002 Indiana University.
- // 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_ARCHETYPES_HPP
- #define BOOST_GRAPH_ARCHETYPES_HPP
- #include <boost/property_map/property_map.hpp>
- #include <boost/concept_archetype.hpp>
- #include <boost/graph/graph_traits.hpp>
- #include <boost/graph/properties.hpp>
- namespace boost { // should use a different namespace for this
- namespace detail {
- struct null_graph_archetype : public null_archetype<> {
- struct traversal_category { };
- };
- }
-
- //===========================================================================
- template <typename Vertex, typename Directed, typename ParallelCategory,
- typename Base = detail::null_graph_archetype >
- struct incidence_graph_archetype : public Base
- {
- typedef typename Base::traversal_category base_trav_cat;
- struct traversal_category
- : public incidence_graph_tag, public base_trav_cat { };
- #if 0
- typedef immutable_graph_tag mutability_category;
- #endif
- typedef Vertex vertex_descriptor;
- typedef unsigned int degree_size_type;
- typedef unsigned int vertices_size_type;
- typedef unsigned int edges_size_type;
- struct edge_descriptor {
- edge_descriptor() { }
- edge_descriptor(const detail::dummy_constructor&) { }
- bool operator==(const edge_descriptor&) const { return false; }
- bool operator!=(const edge_descriptor&) const { return false; }
- };
- typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;
- typedef Directed directed_category;
- typedef ParallelCategory edge_parallel_category;
- typedef void adjacency_iterator;
- typedef void in_edge_iterator;
- typedef void vertex_iterator;
- typedef void edge_iterator;
- static vertex_descriptor null_vertex() {return vertex_descriptor();}
- };
- template <typename V, typename D, typename P, typename B>
- V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
- const incidence_graph_archetype<V,D,P,B>& )
- {
- return V(static_object<detail::dummy_constructor>::get());
- }
- template <typename V, typename D, typename P, typename B>
- V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
- const incidence_graph_archetype<V,D,P,B>& )
- {
- return V(static_object<detail::dummy_constructor>::get());
- }
-
- template <typename V, typename D, typename P, typename B>
- std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,
- typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>
- out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
- {
- typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
- return std::make_pair(Iter(), Iter());
- }
-
- template <typename V, typename D, typename P, typename B>
- typename incidence_graph_archetype<V,D,P,B>::degree_size_type
- out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
- {
- return 0;
- }
- //===========================================================================
- template <typename Vertex, typename Directed, typename ParallelCategory,
- typename Base = detail::null_graph_archetype >
- struct adjacency_graph_archetype : public Base
- {
- typedef typename Base::traversal_category base_trav_cat;
- struct traversal_category
- : public adjacency_graph_tag, public base_trav_cat { };
- typedef Vertex vertex_descriptor;
- typedef unsigned int degree_size_type;
- typedef unsigned int vertices_size_type;
- typedef unsigned int edges_size_type;
- typedef void edge_descriptor;
- typedef input_iterator_archetype<Vertex> adjacency_iterator;
- typedef Directed directed_category;
- typedef ParallelCategory edge_parallel_category;
- typedef void in_edge_iterator;
- typedef void out_edge_iterator;
- typedef void vertex_iterator;
- typedef void edge_iterator;
- static vertex_descriptor null_vertex() {return vertex_descriptor();}
- };
-
- template <typename V, typename D, typename P, typename B>
- std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,
- typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>
- adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
- {
- typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
- return std::make_pair(Iter(), Iter());
- }
- template <typename V, typename D, typename P, typename B>
- typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
- out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
- {
- return 0;
- }
- //===========================================================================
- template <typename Vertex, typename Directed, typename ParallelCategory,
- typename Base = detail::null_graph_archetype >
- struct vertex_list_graph_archetype : public Base
- {
- typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory>
- Incidence;
- typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory>
- Adjacency;
- typedef typename Base::traversal_category base_trav_cat;
- struct traversal_category
- : public vertex_list_graph_tag, public base_trav_cat { };
- #if 0
- typedef immutable_graph_tag mutability_category;
- #endif
- typedef Vertex vertex_descriptor;
- typedef unsigned int degree_size_type;
- typedef typename Incidence::edge_descriptor edge_descriptor;
- typedef typename Incidence::out_edge_iterator out_edge_iterator;
- typedef typename Adjacency::adjacency_iterator adjacency_iterator;
- typedef input_iterator_archetype<Vertex> vertex_iterator;
- typedef unsigned int vertices_size_type;
- typedef unsigned int edges_size_type;
- typedef Directed directed_category;
- typedef ParallelCategory edge_parallel_category;
- typedef void in_edge_iterator;
- typedef void edge_iterator;
- static vertex_descriptor null_vertex() {return vertex_descriptor();}
- };
-
- template <typename V, typename D, typename P, typename B>
- std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,
- typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>
- vertices(const vertex_list_graph_archetype<V,D,P,B>& )
- {
- typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
- return std::make_pair(Iter(), Iter());
- }
- template <typename V, typename D, typename P, typename B>
- typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
- num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
- {
- return 0;
- }
- // ambiguously inherited from incidence graph and adjacency graph
- template <typename V, typename D, typename P, typename B>
- typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type
- out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
- {
- return 0;
- }
- //===========================================================================
- struct property_graph_archetype_tag { };
- template <typename GraphArchetype, typename Property, typename ValueArch>
- struct property_graph_archetype : public GraphArchetype
- {
- typedef property_graph_archetype_tag graph_tag;
- typedef ValueArch vertex_property_type;
- typedef ValueArch edge_property_type;
- };
- struct choose_edge_property_map_archetype {
- template <typename Graph, typename Property, typename Tag>
- struct bind_ {
- typedef mutable_lvalue_property_map_archetype
- <typename Graph::edge_descriptor, Property> type;
- typedef lvalue_property_map_archetype
- <typename Graph::edge_descriptor, Property> const_type;
- };
- };
- template <>
- struct edge_property_selector<property_graph_archetype_tag> {
- typedef choose_edge_property_map_archetype type;
- };
-
- struct choose_vertex_property_map_archetype {
- template <typename Graph, typename Property, typename Tag>
- struct bind_ {
- typedef mutable_lvalue_property_map_archetype
- <typename Graph::vertex_descriptor, Property> type;
- typedef lvalue_property_map_archetype
- <typename Graph::vertex_descriptor, Property> const_type;
- };
- };
- template <>
- struct vertex_property_selector<property_graph_archetype_tag> {
- typedef choose_vertex_property_map_archetype type;
- };
-
- template <typename G, typename P, typename V>
- typename property_map<property_graph_archetype<G, P, V>, P>::type
- get(P, property_graph_archetype<G, P, V>&) {
- typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
- return pmap;
- }
- template <typename G, typename P, typename V>
- typename property_map<property_graph_archetype<G, P, V>, P>::const_type
- get(P, const property_graph_archetype<G, P, V>&) {
- typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
- return pmap;
- }
- template <typename G, typename P, typename K, typename V>
- typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type
- get(P p, const property_graph_archetype<G, P, V>& g, K k) {
- return get( get(p, g), k);
- }
- template <typename G, typename P, typename V, typename Key>
- void
- put(P p, property_graph_archetype<G, P, V>& g,
- const Key& key, const V& value)
- {
- typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;
- Map pmap = get(p, g);
- put(pmap, key, value);
- }
- struct color_value_archetype {
- color_value_archetype() { }
- color_value_archetype(detail::dummy_constructor) { }
- bool operator==(const color_value_archetype& ) const { return true; }
- bool operator!=(const color_value_archetype& ) const { return true; }
- };
- template <>
- struct color_traits<color_value_archetype> {
- static color_value_archetype white()
- {
- return color_value_archetype
- (static_object<detail::dummy_constructor>::get());
- }
- static color_value_archetype gray()
- {
- return color_value_archetype
- (static_object<detail::dummy_constructor>::get());
- }
- static color_value_archetype black()
- {
- return color_value_archetype
- (static_object<detail::dummy_constructor>::get());
- }
- };
- template <typename T>
- class buffer_archetype {
- public:
- void push(const T&) {}
- void pop() {}
- T& top() { return static_object<T>::get(); }
- const T& top() const { return static_object<T>::get(); }
- bool empty() const { return true; }
- };
-
- } // namespace boost
- #endif // BOOST_GRAPH_ARCHETYPES_HPP
|