adjacency_list.hpp

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

      };

      template <>
      struct remove_undirected_edge_dispatch<no_property> {
        // O(E/V)
        template <class edge_descriptor, class Config>
        static void
        apply(edge_descriptor e,
              undirected_graph_helper<Config>& g_,
              no_property&)
        {
          typedef typename Config::graph_type graph_type;
          graph_type& g = static_cast<graph_type&>(g_);
          no_property* p = (no_property*)e.get_property();
          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
          typename Config::OutEdgeList::iterator out_i = out_el.begin();
          for (; out_i != out_el.end(); ++out_i)
            if (&(*out_i).get_property() == p) {
              out_el.erase(out_i);
              break;
            }
          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
          typename Config::OutEdgeList::iterator in_i = in_el.begin();
          for (; in_i != in_el.end(); ++in_i)
            if (&(*in_i).get_property() == p) {
              g.m_edges.erase((*in_i).get_iter());
              in_el.erase(in_i);
              return;
            }
        }
      };

      // O(E/V)
      template <class Graph, class EdgeList, class Vertex>
      inline void
      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 
                               boost::allow_parallel_edge_tag cat)
      {
        typedef typename EdgeList::value_type StoredEdge;
        typename EdgeList::iterator i = el.begin(), end = el.end();
        for (; i != end; ++i)
          if ((*i).get_target() == v)
            g.m_edges.erase((*i).get_iter());
        detail::erase_from_incidence_list(el, v, cat);
      }
      // O(log(E/V))
      template <class Graph, class EdgeList, class Vertex>
      inline void
      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 
                               boost::disallow_parallel_edge_tag)
      {
        typedef typename EdgeList::value_type StoredEdge;
        typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
        if (i != end) {
          g.m_edges.erase((*i).get_iter());
          el.erase(i);
        }
      }

    } // namespace detail

    template <class Vertex, class EdgeProperty>
    struct list_edge // short name due to VC++ truncation and linker problems
      : public boost::detail::edge_base<boost::undirected_tag, Vertex>
    {
      typedef EdgeProperty property_type;
      typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
      list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
        : Base(u, v), m_property(p) { }
      EdgeProperty& get_property() { return m_property; }
      const EdgeProperty& get_property() const { return m_property; }
      // the following methods should never be used, but are needed
      // to make SGI MIPSpro C++ happy
      list_edge() { }
      bool operator==(const list_edge&) const { return false; }
      bool operator<(const list_edge&) const { return false; }
      EdgeProperty m_property;
    };

    template <class Config>
    struct undirected_graph_helper {

      typedef undir_adj_list_traversal_tag traversal_category;

      // Placement of these overloaded remove_edge() functions
      // inside the class avoids a VC++ bug.

      // O(E/V)
      inline void
      remove_edge(typename Config::edge_descriptor e)
      {
        typedef typename Config::OutEdgeList::value_type::property_type PType;
        detail::remove_undirected_edge_dispatch<PType>::apply
          (e, *this, *(PType*)e.get_property());
      }
      // O(E/V)
      inline void
      remove_edge(typename Config::out_edge_iterator iter)
      {
        this->remove_edge(*iter);
      }
    };

    // O(E/V)
    template <class EdgeOrIter, class Config>
    inline void
    remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
    {
      g_.remove_edge(e);
    }

    // O(E/V) or O(log(E/V))
    template <class Config>
    void
    remove_edge(typename Config::vertex_descriptor u, 
                typename Config::vertex_descriptor v, 
                undirected_graph_helper<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(g.out_edge_list(v), u, Cat());
    }
  
    template <class Config, class Predicate>
    void
    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
                       undirected_graph_helper<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_);

      // First remove the edges from the targets' 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)) {
          typename Config::vertex_descriptor v = target(*out_i, g);
          detail::remove_directed_edge_dispatch
            (*out_i, g.out_edge_list(v), *(PropT*)(*out_i).get_property());
          g.m_edges.erase( (*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());
    }
    template <class Config, class Predicate>
    void
    remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
                      undirected_graph_helper<Config>& g_)
    {
      remove_out_edge_if(u, pred, g_);
    }

    // O(E/V * E) or O(log(E/V) * E)
    template <class Predicate, class Config>
    void
    remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::edge_iterator ei, ei_end, next;
      tie(ei, ei_end) = edges(g);
      for (next = ei; ei != ei_end; ei = next) {
        ++next;
        if (pred(*ei))
          remove_edge(*ei, g);
      }
    }

    // O(1)
    template <class Config>
    inline std::pair<typename Config::edge_iterator, 
                     typename Config::edge_iterator>
    edges(const undirected_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()) );
    }
    // O(1)
    template <class Config>
    inline typename Config::edges_size_type
    num_edges(const undirected_graph_helper<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)
    template <class Config>
    inline void 
    clear_vertex(typename Config::vertex_descriptor u,
                 undirected_graph_helper<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
          (g.out_edge_list((*ei).get_target()), u, Cat());
        g.m_edges.erase((*ei).get_iter());
      }
      g.out_edge_list(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,
             undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::StoredEdge StoredEdge;
      typedef typename Config::edge_descriptor edge_descriptor;
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);

      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(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
        return std::make_pair(edge_descriptor(u, v, &p_iter->get_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, 
             undirected_graph_helper<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 undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      const Graph& g = static_cast<const Graph&>(g_);
      return out_degree(u, g);
    }

    template <class Config>
    inline std::pair<typename Config::in_edge_iterator, 
                     typename Config::in_edge_iterator>
    in_edges(typename Config::vertex_descriptor u, 
             const undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      const Graph& cg = static_cast<const Graph&>(g_);
      Graph& g = const_cast<Graph&>(cg);
      typedef typename Config::in_edge_iterator in_edge_iterator;
      return
        std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
                       in_edge_iterator(g.out_edge_list(u).end(), u));
    }

    //=========================================================================
    // Bidirectional Graph Helper Class

    struct bidir_adj_list_traversal_tag : 
      public virtual vertex_list_graph_tag,
      public virtual incidence_graph_tag,
      public virtual adjacency_graph_tag,
      public virtual edge_list_graph_tag,
      public virtual bidirectional_graph_tag { };

    template <class Config>
    struct bidirectional_graph_helper
      : public directed_edges_helper<Config> {
      typedef bidir_adj_list_traversal_tag traversal_category;
    };

    template <class Predicate, class Config>
    inline void
    remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::edge_iterator ei, ei_end, next;
      tie(ei, ei_end) = edges(g);
      for (next = ei; ei != ei_end; ei = next) {
        ++next;
        if (pred(*ei))
          remove_edge(*ei, g);
      }
    }

    template <class Config>
    inline std::pair<typename Config::in_edge_iterator, 
                     typename Config::in_edge_iterator>
    in_edges(typename Config::vertex_descriptor u, 
             const bidirectional_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      const graph_type& cg = static_cast<const graph_type&>(g_);
      graph_type& g = const_cast<graph_type&>(cg);
      typedef typename Config::in_edge_iterator in_edge_iterator;
      return
        std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
                       in_edge_iterator(in_edge_list(g, u).end(), u));
    }

    // O(1)
    template <class Config>
    inline std::pair<typename Config::edge_iterator,