graph_archetypes.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 305 行

//=======================================================================
// Copyright 2002 Indiana University.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// This file is part of the Boost Graph Library
//
// You should have received a copy of the License Agreement for the
// Boost Graph Library along with the software; see the file LICENSE.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================

#ifndef BOOST_GRAPH_ARCHETYPES_HPP
#define BOOST_GRAPH_ARCHETYPES_HPP

#include <boost/property_map.hpp>
#include <boost/concept_archetype.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