adjacency_list.hpp

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

                     typename Config::edge_iterator>
    edges(const bidirectional_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::edge_iterator edge_iterator;
      const graph_type& cg = static_cast<const graph_type&>(g_);
      graph_type& g = const_cast<graph_type&>(cg);
      return std::make_pair( edge_iterator(g.m_edges.begin()),
                             edge_iterator(g.m_edges.end()) );
    }

    //=========================================================================
    // Bidirectional Graph Helper Class (with edge properties)


    template <class Config>
    struct bidirectional_graph_helper_with_property
      : public bidirectional_graph_helper<Config>
    {
      // Placement of these overloaded remove_edge() functions
      // inside the class avoids a VC++ bug.
      
      void
      remove_edge(typename Config::edge_descriptor e);

      inline void
      remove_edge(typename Config::out_edge_iterator iter)
      {
        this->remove_edge(*iter);
      }
    };

    // O(E/V) for allow_parallel_edge_tag
    // O(log(E/V)) for disallow_parallel_edge_tag
    template <class Config>
    inline void
    remove_edge(typename Config::vertex_descriptor u, 
                typename Config::vertex_descriptor v, 
                bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);
      typedef typename Config::edge_parallel_category Cat;
      detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
      detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
    }

    // O(E/V) or O(log(E/V))
    template <class Config>
    inline void
    bidirectional_graph_helper_with_property<Config>::remove_edge(typename Config::edge_descriptor e)
    {
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(*this);
      boost::remove_edge(source(e, g), target(e, g), *this);
    }
    // O(E/V) or O(log(E/V))
    template <class EdgeOrIter, class Config>
    inline void
    remove_edge(EdgeOrIter e,
                bidirectional_graph_helper_with_property<Config>& g_)
    {
      g_.remove_edge(e);
    }

    template <class Config, class Predicate>
    inline void
    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
                       bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::OutEdgeList::value_type::property_type PropT;
      graph_type& g = static_cast<graph_type&>(g_);
      
      typedef typename Config::EdgeIter EdgeIter;
      typedef std::vector<EdgeIter> Garbage;
      Garbage garbage;

      // First remove the edges from the targets' in-edge lists and
      // from the graph's edge set list.
      typename Config::out_edge_iterator out_i, out_end;
      for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
        if (pred(*out_i)) {
          detail::remove_directed_edge_dispatch
            (*out_i, in_edge_list(g, target(*out_i, g)),
             *(PropT*)(*out_i).get_property());
          // Put in garbage to delete later. Will need the properties
          // for the remove_if of the out-edges.
          garbage.push_back((*out_i.base()).get_iter());
        }

      // Now remove the edges from this out-edge list.
      typename Config::out_edge_iterator first, last;
      tie(first, last) = out_edges(u, g);
      typedef typename Config::edge_parallel_category Cat;
      detail::remove_directed_edge_if_dispatch
        (first, last, g.out_edge_list(u), pred, Cat());

      // Now delete the edge properties from the g.m_edges list
      for (typename Garbage::iterator i = garbage.begin();
           i != garbage.end(); ++i)
        g.m_edges.erase(*i);
    }
    template <class Config, class Predicate>
    inline void
    remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
                      bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::OutEdgeList::value_type::property_type PropT;
      graph_type& g = static_cast<graph_type&>(g_);

      typedef typename Config::EdgeIter EdgeIter;
      typedef std::vector<EdgeIter> Garbage;
      Garbage garbage;

      // First remove the edges from the sources' out-edge lists and
      // from the graph's edge set list.
      typename Config::in_edge_iterator in_i, in_end;
      for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
        if (pred(*in_i)) {
          typename Config::vertex_descriptor u = source(*in_i, g);
          detail::remove_directed_edge_dispatch
            (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
          // Put in garbage to delete later. Will need the properties
          // for the remove_if of the out-edges.
          garbage.push_back((*in_i.base()).get_iter());
        }
      // Now remove the edges from this in-edge list.
      typename Config::in_edge_iterator first, last;
      tie(first, last) = in_edges(v, g);
      typedef typename Config::edge_parallel_category Cat;
      detail::remove_directed_edge_if_dispatch
        (first, last, in_edge_list(g, v), pred, Cat());

      // Now delete the edge properties from the g.m_edges list
      for (typename Garbage::iterator i = garbage.begin();
           i != garbage.end(); ++i)
        g.m_edges.erase(*i);
    }

    // O(1)
    template <class Config>
    inline typename Config::edges_size_type
    num_edges(const bidirectional_graph_helper_with_property<Config>& g_) 
    {
      typedef typename Config::graph_type graph_type;
      const graph_type& g = static_cast<const graph_type&>(g_);
      return g.m_edges.size();
    }
    // O(E/V * E/V) for allow_parallel_edge_tag
    // O(E/V * log(E/V)) for disallow_parallel_edge_tag
    template <class Config>
    inline void
    clear_vertex(typename Config::vertex_descriptor u,
                 bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::edge_parallel_category Cat;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::OutEdgeList& el = g.out_edge_list(u);
      typename Config::OutEdgeList::iterator 
        ei = el.begin(), ei_end = el.end();
      for (; ei != ei_end; ++ei) {
        detail::erase_from_incidence_list
          (in_edge_list(g, (*ei).get_target()), u, Cat());
        g.m_edges.erase((*ei).get_iter());
      }      
      typename Config::InEdgeList& in_el = in_edge_list(g, u);
      typename Config::InEdgeList::iterator 
        in_ei = in_el.begin(), in_ei_end = in_el.end();
      for (; in_ei != in_ei_end; ++in_ei) {
        detail::erase_from_incidence_list
          (g.out_edge_list((*in_ei).get_target()), u, Cat());
        g.m_edges.erase((*in_ei).get_iter());   
      }
      g.out_edge_list(u).clear();
      in_edge_list(g, u).clear();
    }

    template <class Config>
    inline void
    clear_out_edges(typename Config::vertex_descriptor u,
                    bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::edge_parallel_category Cat;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::OutEdgeList& el = g.out_edge_list(u);
      typename Config::OutEdgeList::iterator 
        ei = el.begin(), ei_end = el.end();
      for (; ei != ei_end; ++ei) {
        detail::erase_from_incidence_list
          (in_edge_list(g, (*ei).get_target()), u, Cat());
        g.m_edges.erase((*ei).get_iter());
      }      
      g.out_edge_list(u).clear();
    }

    template <class Config>
    inline void
    clear_in_edges(typename Config::vertex_descriptor u,
                   bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::edge_parallel_category Cat;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::InEdgeList& in_el = in_edge_list(g, u);
      typename Config::InEdgeList::iterator 
        in_ei = in_el.begin(), in_ei_end = in_el.end();
      for (; in_ei != in_ei_end; ++in_ei) {
        detail::erase_from_incidence_list
          (g.out_edge_list((*in_ei).get_target()), u, Cat());
        g.m_edges.erase((*in_ei).get_iter());   
      }
      in_edge_list(g, u).clear();
    }

    // O(1) for allow_parallel_edge_tag
    // O(log(E/V)) for disallow_parallel_edge_tag
    template <class Config>
    inline std::pair<typename Config::edge_descriptor, bool>
    add_edge(typename Config::vertex_descriptor u,
             typename Config::vertex_descriptor v, 
             const typename Config::edge_property_type& p,
             bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);
      typedef typename Config::edge_descriptor edge_descriptor;
      typedef typename Config::StoredEdge StoredEdge;
      bool inserted;
      typename Config::EdgeContainer::value_type e(u, v, p);
      g.m_edges.push_back(e);
      typename Config::EdgeContainer::iterator p_iter 
        = boost::prior(g.m_edges.end());
      typename Config::OutEdgeList::iterator i;
      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
                                        StoredEdge(v, p_iter, &g.m_edges));
      if (inserted) {
        boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
        return std::make_pair(edge_descriptor(u, v, &p_iter->m_property), 
                              true);
      } else {
        g.m_edges.erase(p_iter);
        return std::make_pair(edge_descriptor(u, v, 
                                     &i->get_iter()->get_property()), 
                              false);
      }
    }

    template <class Config>
    inline std::pair<typename Config::edge_descriptor, bool>
    add_edge(typename Config::vertex_descriptor u,
             typename Config::vertex_descriptor v,
             bidirectional_graph_helper_with_property<Config>& g_)
    {
      typename Config::edge_property_type p;
      return add_edge(u, v, p, g_);
    }
    // O(1)
    template <class Config>
    inline typename Config::degree_size_type
    degree(typename Config::vertex_descriptor u, 
           const bidirectional_graph_helper_with_property<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      const graph_type& g = static_cast<const graph_type&>(g_);
      return in_degree(u, g) + out_degree(u, g);
    }

    //=========================================================================
    // Adjacency List Helper Class

    template <class Config, class Base>
    struct adj_list_helper : public Base
    {
      typedef typename Config::graph_type AdjList;
      typedef typename Config::vertex_descriptor vertex_descriptor;
      typedef typename Config::edge_descriptor edge_descriptor;
      typedef typename Config::out_edge_iterator out_edge_iterator;
      typedef typename Config::in_edge_iterator in_edge_iterator;
      typedef typename Config::adjacency_iterator adjacency_iterator;
      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
      typedef typename Config::vertex_iterator vertex_iterator;
      typedef typename Config::edge_iterator edge_iterator;
      typedef typename Config::directed_category directed_category;
      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::StoredEdge StoredEdge;
      typedef typename Config::edge_property_type edge_property_type;

      //    protected:

      // The edge_dispatch() functions should be static, but
      // Borland gets confused about constness.

      // O(E/V)
      inline std::pair<edge_descriptor,bool>      
      edge_dispatch(const AdjList& g, 
                    vertex_descriptor u, vertex_descriptor v, 
                    boost::allow_parallel_edge_tag) const
      {
        bool found;
        const typename Config::OutEdgeList& el = g.out_edge_list(u);
        typename Config::OutEdgeList::const_iterator 
          i = std::find_if(el.begin(), el.end(), 
                           detail::target_is<vertex_descriptor>(v));
        found = (i != g.out_edge_list(u).end());
        if (found)
          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
                                true);
        else
          return std::make_pair(edge_descriptor(u, v, 0), false);
      }
      // O(log(E/V))
      inline std::pair<edge_descriptor,bool>      
      edge_dispatch(const AdjList& g, 
                    vertex_descriptor u, vertex_descriptor v, 
                    boost::disallow_parallel_edge_tag) const
      {
        bool found;
        /* According to the standard, this should be iterator, not const_iterator,
           but the VC++ std::set::find() const returns const_iterator.
           And since iterator should be convertible to const_iterator, the
           following should work everywhere. -Jeremy */
        typename Config::OutEdgeList::const_iterator 
          i = g.out_edge_list(u).find(StoredEdge(v)),
          end = g.out_edge_list(u).end();
        found = (i != end);
        if (found)