adjacency_list.hpp

C++的一个好库。。。现在很流行

// -*- c++ -*-
//=======================================================================
// 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_DETAIL_ADJACENCY_LIST_HPP
#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP

#include <map> // for vertex_map in copy_impl
#include <boost/config.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/operators.hpp>
#include <boost/property_map.hpp>
#include <boost/pending/integer_range.hpp>
#include <boost/graph/graph_traits.hpp>
#include <memory>
#include <algorithm>
#include <boost/limits.hpp>

#include <boost/iterator/iterator_adaptor.hpp>

#include <boost/pending/ct_if.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/pending/container_traits.hpp>
#include <boost/graph/detail/adj_list_edge_iterator.hpp>
#include <boost/graph/properties.hpp>
#include <boost/pending/property.hpp>
#include <boost/graph/adjacency_iterator.hpp>

// Symbol truncation problems with MSVC, trying to shorten names.
#define stored_edge se_
#define stored_edge_property sep_
#define stored_edge_iter sei_

/*
  Outline for this file:

  out_edge_iterator and in_edge_iterator implementation
  edge_iterator for undirected graph
  stored edge types (these object live in the out-edge/in-edge lists)
  directed edges helper class
  directed graph helper class
  undirected graph helper class
  bidirectional graph helper class
  bidirectional graph helper class (without edge properties)
  bidirectional graph helper class (with edge properties)
  adjacency_list helper class
  adj_list_impl class
  vec_adj_list_impl class
  adj_list_gen class
  vertex property map
  edge property map


  Note: it would be nice to merge some of the undirected and
  bidirectional code... it is aweful similar.
 */



namespace boost {

  namespace detail {

    template <typename DirectedS>
    struct directed_category_traits {
      typedef directed_tag directed_category;
    };

    template <>
    struct directed_category_traits<directedS> {
      typedef directed_tag directed_category;
    };
    template <>
    struct directed_category_traits<undirectedS> {
      typedef undirected_tag directed_category;
    };
    template <>
    struct directed_category_traits<bidirectionalS> {
      typedef bidirectional_tag directed_category;
    };

    template <class Vertex>
    struct target_is {
      target_is(const Vertex& v) : m_target(v) { }
      template <class StoredEdge>
      bool operator()(const StoredEdge& e) const {
        return e.get_target() == m_target;
      }
      Vertex m_target;
    };

    // O(E/V)
    template <class EdgeList, class vertex_descriptor>
    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
                                   allow_parallel_edge_tag)
    {
      boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
    }
    // O(log(E/V))
    template <class EdgeList, class vertex_descriptor>
    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
                                   disallow_parallel_edge_tag)
    {
      typedef typename EdgeList::value_type StoredEdge;
      el.erase(StoredEdge(v));
    }

    //=========================================================================
    // Out-Edge and In-Edge Iterator Implementation

    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
    struct out_edge_iter
      : iterator_adaptor<
            out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
          , BaseIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , Difference
        >
    {
      typedef iterator_adaptor<
          out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
        , BaseIter
        , EdgeDescriptor
        , use_default
        , EdgeDescriptor
        , Difference
      > super_t;
        
      inline out_edge_iter() { }
        inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
          : super_t(i), m_src(src) { }

      inline EdgeDescriptor
      dereference() const
      {
        return EdgeDescriptor(m_src, (*this->base()).get_target(), 
                              &(*this->base()).get_property());
      }
      VertexDescriptor m_src;
    };
  
    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
    struct in_edge_iter
      : iterator_adaptor<
            in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
          , BaseIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , Difference
        >
    {
      typedef iterator_adaptor<
          in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
        , BaseIter
        , EdgeDescriptor
        , use_default
        , EdgeDescriptor
        , Difference
      > super_t;
        
      inline in_edge_iter() { }
      inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) 
        : super_t(i), m_src(src) { }

      inline EdgeDescriptor
      dereference() const
      {
        return EdgeDescriptor((*this->base()).get_target(), m_src,
                              &this->base()->get_property());
      }
      VertexDescriptor m_src;
    };

    //=========================================================================
    // Undirected Edge Iterator Implementation

    template <class EdgeIter, class EdgeDescriptor, class Difference>
    struct undirected_edge_iter
      : iterator_adaptor<
            undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
          , EdgeIter
          , EdgeDescriptor
          , use_default
          , EdgeDescriptor
          , Difference
        >
    {
      typedef iterator_adaptor<
          undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
        , EdgeIter
        , EdgeDescriptor
        , use_default
        , EdgeDescriptor
        , Difference
      > super_t;

      undirected_edge_iter() {}
        
      explicit undirected_edge_iter(EdgeIter i)
          : super_t(i) {}
        
      inline EdgeDescriptor
      dereference() const {
        return EdgeDescriptor(
            (*this->base()).m_source
          , (*this->base()).m_target
          , &this->base()->get_property());
      }
    };

    //=========================================================================
    // Edge Storage Types (stored in the out-edge/in-edge lists)

    template <class Vertex>
    class stored_edge
      : public boost::equality_comparable1< stored_edge<Vertex>,
        boost::less_than_comparable1< stored_edge<Vertex> > >
    {
    public:
      typedef no_property property_type;
      inline stored_edge() { }
      inline stored_edge(Vertex target, const no_property& = no_property())
        : m_target(target) { }
      // Need to write this explicitly so stored_edge_property can
      // invoke Base::operator= (at least, for SGI MIPSPro compiler)
      inline stored_edge& operator=(const stored_edge& x) {
        m_target = x.m_target;
        return *this;
      }
      inline Vertex& get_target() const { return m_target; }
      inline const no_property& get_property() const { return s_prop; }
      inline bool operator==(const stored_edge& x) const
        { return m_target == x.get_target(); }
      inline bool operator<(const stored_edge& x) const
        { return m_target < x.get_target(); }
      //protected: need to add hash<> as a friend
      static no_property s_prop;
      // Sometimes target not used as key in the set, and in that case
      // it is ok to change the target.
      mutable Vertex m_target;
    };
    template <class Vertex>
    no_property stored_edge<Vertex>::s_prop;

    template <class Vertex, class Property>
    class stored_edge_property : public stored_edge<Vertex> {
      typedef stored_edge_property self;
      typedef stored_edge<Vertex> Base;
    public:
      typedef Property property_type;
      inline stored_edge_property() { }
      inline stored_edge_property(Vertex target,
                                  const Property& p = Property())
        : stored_edge<Vertex>(target), m_property(new Property(p)) { }
      stored_edge_property(const self& x) 
        : Base(x), m_property(const_cast<self&>(x).m_property) { }
      self& operator=(const self& x) {
        Base::operator=(x);
        m_property = const_cast<self&>(x).m_property; 
        return *this;
      }
      inline Property& get_property() { return *m_property; }
      inline const Property& get_property() const { return *m_property; }
    protected:
      // Holding the property by-value causes edge-descriptor
      // invalidation for add_edge() with EdgeList=vecS. Instead we
      // hold a pointer to the property. std::auto_ptr is not
      // a perfect fit for the job, but it is darn close.
      std::auto_ptr<Property> m_property;
    };


    template <class Vertex, class Iter, class Property>
    class stored_edge_iter
      : public stored_edge<Vertex>
    {
    public:
      typedef Property property_type;
      inline stored_edge_iter() { }
      inline stored_edge_iter(Vertex v)
        : stored_edge<Vertex>(v) { }
      inline stored_edge_iter(Vertex v, Iter i, void* = 0)
        : stored_edge<Vertex>(v), m_iter(i) { }
      inline Property& get_property() { return m_iter->get_property(); }
      inline const Property& get_property() const { 
        return m_iter->get_property();
      }
      inline Iter get_iter() const { return m_iter; }
    protected:
      Iter m_iter;
    };

    // For when the EdgeList is a std::vector.
    // Want to make the iterator stable, so use an offset
    // instead of an iterator into a std::vector
    template <class Vertex, class EdgeVec, class Property>
    class stored_ra_edge_iter
      : public stored_edge<Vertex>
    {
      typedef typename EdgeVec::iterator Iter;
    public:
      typedef Property property_type;
      inline stored_ra_edge_iter() { }
      inline stored_ra_edge_iter(Vertex v, Iter i = Iter(), 
                                 EdgeVec* edge_vec = 0)
        : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
      inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
      inline const Property& get_property() const { 
        return (*m_vec)[m_i].get_property();
      }
      inline Iter get_iter() const { return m_vec->begin() + m_i; }
    protected:
      std::size_t m_i;
      EdgeVec* m_vec;
    };

  } // namespace detail
    
  template <class Tag, class Vertex, class Property>
  const typename property_value<Property,Tag>::type&
  get(Tag property_tag,
      const detail::stored_edge_property<Vertex, Property>& e)
  {
    return get_property_value(e.get_property(), property_tag);
  }