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