adjacency_list.hpp

boost库提供标准的C++ API 配合dev c++使用,功能更加强大

          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
                                true);
        else
          return std::make_pair(edge_descriptor(u, v, 0), false);
      }
    };

    template <class Config, class Base>
    inline std::pair<typename Config::adjacency_iterator, 
                     typename Config::adjacency_iterator>
    adjacent_vertices(typename Config::vertex_descriptor u, 
                      const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      typedef typename Config::adjacency_iterator adjacency_iterator;
      typename Config::out_edge_iterator first, last;
      boost::tie(first, last) = out_edges(u, g);
      return std::make_pair(adjacency_iterator(first, &g),
                            adjacency_iterator(last, &g));
    }
    template <class Config, class Base>
    inline std::pair<typename Config::inv_adjacency_iterator, 
                     typename Config::inv_adjacency_iterator>
    inv_adjacent_vertices(typename Config::vertex_descriptor u, 
                          const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
      typename Config::in_edge_iterator first, last;
      boost::tie(first, last) = in_edges(u, g);
      return std::make_pair(inv_adjacency_iterator(first, &g),
                            inv_adjacency_iterator(last, &g));
    }
    template <class Config, class Base>
    inline std::pair<typename Config::out_edge_iterator, 
                     typename Config::out_edge_iterator>
    out_edges(typename Config::vertex_descriptor u, 
              const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      typedef typename Config::out_edge_iterator out_edge_iterator;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      return
        std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
                       out_edge_iterator(g.out_edge_list(u).end(), u));
    }
    template <class Config, class Base>
    inline std::pair<typename Config::vertex_iterator, 
                     typename Config::vertex_iterator>
    vertices(const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
    }
    template <class Config, class Base>
    inline typename Config::vertices_size_type
    num_vertices(const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& g = static_cast<const AdjList&>(g_);
      return g.vertex_set().size();
    }
    template <class Config, class Base>
    inline typename Config::degree_size_type
    out_degree(typename Config::vertex_descriptor u, 
               const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& g = static_cast<const AdjList&>(g_);
      return g.out_edge_list(u).size();
    }
    template <class Config, class Base>
    inline std::pair<typename Config::edge_descriptor, bool>
    edge(typename Config::vertex_descriptor u, 
         typename Config::vertex_descriptor v, 
         const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_parallel_category Cat;
      const Graph& g = static_cast<const Graph&>(g_);
      return g_.edge_dispatch(g, u, v, Cat());
    }
    template <class Config, class Base>
    inline std::pair<typename Config::out_edge_iterator,
                     typename Config::out_edge_iterator>
    edge_range(typename Config::vertex_descriptor u,
               typename Config::vertex_descriptor v,
               const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::StoredEdge StoredEdge;
      const Graph& cg = static_cast<const Graph&>(g_);
      Graph& g = const_cast<Graph&>(cg);
      typedef typename Config::out_edge_iterator out_edge_iterator;
      typename Config::OutEdgeList& el = g.out_edge_list(u);
      typename Config::OutEdgeList::iterator first, last;
      tie(first, last) = std::equal_range(el.begin(), el.end(), StoredEdge(v));
      return std::make_pair(out_edge_iterator(first, u),
                            out_edge_iterator(last, u));
    }

    template <class Config, class Base>
    inline typename Config::degree_size_type
    in_degree(typename Config::vertex_descriptor u, 
              const adj_list_helper<Config,Base>& g_)
    {
      typedef typename Config::graph_type Graph;
      const Graph& cg = static_cast<const Graph&>(g_);
      Graph& g = const_cast<Graph&>(cg);
      return in_edge_list(g, u).size();
    }

    namespace detail {
      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type,
        Property>::type
      get_dispatch(adj_list_helper<Config,Base>&, Property, 
                   boost::edge_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::type PA;
        return PA();
      }
      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type, 
        Property>::const_type
      get_dispatch(const adj_list_helper<Config,Base>&, Property, 
                   boost::edge_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::const_type PA;
        return PA();
      }

      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type, 
        Property>::type
      get_dispatch(adj_list_helper<Config,Base>& g, Property, 
                   boost::vertex_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::type PA;
        return PA(&static_cast<Graph&>(g));
      }
      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type,
        Property>::const_type
      get_dispatch(const adj_list_helper<Config, Base>& g, Property, 
                   boost::vertex_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::const_type PA;
        const Graph& cg = static_cast<const Graph&>(g);
        return PA(&cg);
      }

    } // namespace detail

    // Implementation of the PropertyGraph interface
    template <class Config, class Base, class Property>
    inline
    typename boost::property_map<typename Config::graph_type, Property>::type
    get(Property p, adj_list_helper<Config, Base>& g) {
      typedef typename property_kind<Property>::type Kind;
      return detail::get_dispatch(g, p, Kind());
    }
    template <class Config, class Base, class Property>
    inline
    typename boost::property_map<typename Config::graph_type, 
      Property>::const_type
    get(Property p, const adj_list_helper<Config, Base>& g) {
      typedef typename property_kind<Property>::type Kind;
      return detail::get_dispatch(g, p, Kind());
    }

    template <class Config, class Base, class Property, class Key>
    inline
    typename boost::property_traits<
      typename boost::property_map<typename Config::graph_type, 
        Property>::const_type
    >::value_type
    get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
      return get(get(p, g), key);
    }

    template <class Config, class Base, class Property, class Key,class Value>
    inline void
    put(Property p, adj_list_helper<Config, Base>& g, 
        const Key& key, const Value& value)
    {
      typedef typename Config::graph_type Graph;
      typedef typename boost::property_map<Graph, Property>::type Map;
      Map pmap = get(p, static_cast<Graph&>(g));
      put(pmap, key, value);
    }


    //=========================================================================
    // Generalize Adjacency List Implementation

    struct adj_list_tag { };

    template <class Derived, class Config, class Base>
    class adj_list_impl
      : public adj_list_helper<Config, Base>
    {
      typedef typename Config::OutEdgeList OutEdgeList;
      typedef typename Config::InEdgeList InEdgeList;
      typedef typename Config::StoredVertexList StoredVertexList;
    public:
      typedef typename Config::stored_vertex stored_vertex;
      typedef typename Config::EdgeContainer EdgeContainer;
      typedef typename Config::vertex_descriptor vertex_descriptor;
      typedef typename Config::edge_descriptor edge_descriptor;
      typedef typename Config::vertex_iterator vertex_iterator;
      typedef typename Config::edge_iterator edge_iterator;
      typedef typename Config::edge_parallel_category edge_parallel_category;
      typedef typename Config::vertices_size_type vertices_size_type;
      typedef typename Config::edges_size_type edges_size_type;
      typedef typename Config::degree_size_type degree_size_type;
      typedef typename Config::edge_property_type edge_property_type;
      typedef adj_list_tag graph_tag;

      static vertex_descriptor null_vertex()
      {
        return 0;
      }
      
      inline adj_list_impl() { }

      inline adj_list_impl(const adj_list_impl& x) {
        copy_impl(x);
      }
      inline adj_list_impl& operator=(const adj_list_impl& x) {
        this->clear();
        copy_impl(x);
        return *this;
      }
      inline void clear() {
        for (typename StoredVertexList::iterator i = m_vertices.begin();
             i != m_vertices.end(); ++i)
          delete (stored_vertex*)*i;
        m_vertices.clear();
        m_edges.clear();
      }
      inline adj_list_impl(vertices_size_type num_vertices) {
        for (vertices_size_type i = 0; i < num_vertices; ++i)
          add_vertex(static_cast<Derived&>(*this));
      }
      template <class EdgeIterator>
      inline adj_list_impl(vertices_size_type num_vertices,
                           EdgeIterator first, EdgeIterator last)
      {
        vertex_descriptor* v = new vertex_descriptor[num_vertices];
        for (vertices_size_type i = 0; i < num_vertices; ++i)
          v[i] = add_vertex(static_cast<Derived&>(*this));

        while (first != last) {
          add_edge(v[(*first).first], v[(*first).second], *this);
          ++first;
        }
        delete [] v;
      }
      template <class EdgeIterator, class EdgePropertyIterator>
      inline adj_list_impl(vertices_size_type num_vertices,
                           EdgeIterator first, EdgeIterator last,
                           EdgePropertyIterator ep_iter)
      {
        vertex_descriptor* v = new vertex_descriptor[num_vertices];
        for (vertices_size_type i = 0; i < num_vertices; ++i)
          v[i] = add_vertex(static_cast<Derived&>(*this));

        while (first != last) {
          add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
          ++first;
          ++ep_iter;
        }
        delete [] v;
      }
      ~adj_list_impl() {
        for (typename StoredVertexList::iterator i = m_vertices.begin();
             i != m_vertices.end(); ++i)
          delete (stored_vertex*)*i;
      }
      //    protected:
      inline OutEdgeList& out_edge_list(vertex_descriptor v) {
        stored_vertex* sv = (stored_vertex*)v;
        return sv->m_out_edges;
      }
      inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
        stored_vertex* sv = (stored_vertex*)v;
        return sv->m_out_edges;
      }
      inline StoredVertexList& vertex_set() { return m_vertices; }
      inline const StoredVertexList& vertex_set() const { return m_vertices; }

      inline void copy_impl(const adj_list_impl& x_) 
      {
        const Derived& x = static_cast<const Derived&>(x_);

        // Would be better to have a constant time way to get from
        // vertices in x to the corresponding vertices in *this.
        std::map<stored_vertex*,stored_vertex*> vertex_map;

        // Copy the stored vertex objects by adding each vertex
        // and copying its property object.
        vertex_iterator vi, vi_end;
        for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
          stored_vertex* v = (stored_vertex*)add_vertex(*this);
          v->m_property = ((stored_vertex*)*vi)->m_property;
          vertex_map[(stored_vertex*)*vi] = v;
        }
        // Copy the edges by adding each edge and copying its
        // property object.
        edge_iterator ei, ei_end;
        for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
          edge_descriptor e;
          bool inserted; 
          vertex_descriptor s = source(*ei,x), t = target(*ei,x);
          tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], 
                                      vertex_map[(stored_vertex*)t], *this);
          *((edge_property_type*)e.m_eproperty)
            = *((edge_property_type*)(*ei).m_eproperty);
        }
      }