adjacency_list.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

    // Did not use default argument here because that
    // causes Visual C++ to get confused.
    template <class Config>
    inline std::pair<typename Config::edge_descriptor, bool>
    add_edge(typename Config::vertex_descriptor u, 
             typename Config::vertex_descriptor v,
             directed_graph_helper<Config>& g_)
    {
      typename Config::edge_property_type p;
      return add_edge(u, v, p, g_);
    }
    //=========================================================================
    // Undirected Graph Helper Class

    template <class Config>
    struct undirected_graph_helper;

    struct undir_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 { };

    namespace detail {

      // using class with specialization for dispatch is a VC++ workaround.
      template <class StoredProperty>
      struct remove_undirected_edge_dispatch {

        // O(E/V)
        template <class edge_descriptor, class Config>
        static void
        apply(edge_descriptor e, 
              undirected_graph_helper<Config>& g_, 
              StoredProperty& p)
        {
          typedef typename Config::global_edgelist_selector EdgeListS;
          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

          typedef typename Config::graph_type graph_type;
          graph_type& g = static_cast<graph_type&>(g_);
          
          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;
            }
        }
      };

      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::global_edgelist_selector EdgeListS;
          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

          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 Graph::global_edgelist_selector EdgeListS;
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        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 Graph::global_edgelist_selector EdgeListS;
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        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::global_edgelist_selector EdgeListS;
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        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);
      }
    };

    // Had to make these non-members to avoid accidental instantiation
    // on SGI MIPSpro C++
    template <class C>
    inline typename C::InEdgeList& 
    in_edge_list(undirected_graph_helper<C>&, 
                 typename C::vertex_descriptor v)
    {
      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
      return sv->m_out_edges;
    }
    template <class C>
    inline const typename C::InEdgeList& 
    in_edge_list(const undirected_graph_helper<C>&,
                 typename C::vertex_descriptor v) {
      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
      return sv->m_out_edges;
    }

    // O(E/V)
    template <class EdgeOrIter, class Config>
    inline void
    remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      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::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      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::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
        
      typedef typename Config::graph_type graph_type;
      typedef typename Config::OutEdgeList::value_type::property_type PropT;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::out_edge_iterator first, last;
      tie(first, last) = out_edges(u, g);
      typedef typename Config::edge_parallel_category Cat;
      detail::undirected_remove_out_edge_if_dispatch<PropT>
        (g, 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_)
    {
      typedef typename Config::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      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::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      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::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      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);
      typename Config::EdgeContainer::iterator p_iter 
        = graph_detail::push(g.m_edges, e).first;

      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);