adjacency_list.hpp

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

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

  template <class Tag, class Vertex, class EdgeVec, class Property>
  const typename property_value<Property,Tag>::type&
  get(Tag property_tag,
      const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
  {
    return get_property_value(e.get_property(), property_tag);
  }
    
    //=========================================================================
    // Directed Edges Helper Class

    namespace detail {

      // O(E/V)
      template <class edge_descriptor, class EdgeList, class StoredProperty>
      inline void
      remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
                                    StoredProperty& p)
      {
        for (typename EdgeList::iterator i = el.begin();
             i != el.end(); ++i)
          if (&(*i).get_property() == &p) {
            el.erase(i);
            return;
          }
      }

      template <class incidence_iterator, class EdgeList, class Predicate>
      inline void
      remove_directed_edge_if_dispatch(incidence_iterator first,
                                       incidence_iterator last, 
                                       EdgeList& el, Predicate pred,
                                       boost::allow_parallel_edge_tag)
      {
        // remove_if
        while (first != last && !pred(*first))
          ++first;
        incidence_iterator i = first;
        if (first != last)
          for (; i != last; ++i)
            if (!pred(*i)) {
              *first.base() = *i.base();
              ++first;
            }
        el.erase(first.base(), el.end());
      }
      template <class incidence_iterator, class EdgeList, class Predicate>
      inline void
      remove_directed_edge_if_dispatch(incidence_iterator first,
                                       incidence_iterator last, 
                                       EdgeList& el, 
                                       Predicate pred,
                                       boost::disallow_parallel_edge_tag)
      {
        for (incidence_iterator next = first;
             first != last; first = next) {
          ++next;
          if (pred(*first))
            el.erase( first.base() );
        }
      }

      template <class PropT, class Graph, class incidence_iterator, 
                class EdgeList, class Predicate>
      inline void
      undirected_remove_out_edge_if_dispatch(Graph& g, 
                                             incidence_iterator first,
                                             incidence_iterator last, 
                                             EdgeList& el, Predicate pred,
                                             boost::allow_parallel_edge_tag)
      {
        typedef typename Graph::global_edgelist_selector EdgeListS;
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        // remove_if
        while (first != last && !pred(*first))
          ++first;
        incidence_iterator i = first;
        bool self_loop_removed = false;
        if (first != last)
          for (; i != last; ++i) {
            if (self_loop_removed) {
              /* With self loops, the descriptor will show up
               * twice. The first time it will be removed, and now it
               * will be skipped.
               */
              self_loop_removed = false;
            }
            else if (!pred(*i)) {
              *first.base() = *i.base();
              ++first;
            } else {
              if (source(*i, g) == target(*i, g)) self_loop_removed = true;
              else {
                // Remove the edge from the target
                detail::remove_directed_edge_dispatch
                  (*i, 
                   g.out_edge_list(target(*i, g)), 
                   *(PropT*)(*i).get_property());
              }

              // Erase the edge property
              g.m_edges.erase( (*i.base()).get_iter() );
            }
          }
        el.erase(first.base(), el.end());
      }
      template <class PropT, class Graph, class incidence_iterator, 
                class EdgeList, class Predicate>
      inline void
      undirected_remove_out_edge_if_dispatch(Graph& g, 
                                             incidence_iterator first,
                                             incidence_iterator last, 
                                             EdgeList& el, 
                                             Predicate pred,
                                             boost::disallow_parallel_edge_tag)
      {
        typedef typename Graph::global_edgelist_selector EdgeListS;
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        for (incidence_iterator next = first;
             first != last; first = next) {
          ++next;
          if (pred(*first)) {
            if (source(*first, g) != target(*first, g)) {
              // Remove the edge from the target
              detail::remove_directed_edge_dispatch
                (*first, 
                 g.out_edge_list(target(*first, g)), 
                 *(PropT*)(*first).get_property());
            }

            // Erase the edge property
            g.m_edges.erase( (*first.base()).get_iter() );

            // Erase the edge in the source
            el.erase( first.base() );
          }
        }
      }

      // O(E/V)
      template <class edge_descriptor, class EdgeList, class StoredProperty>
      inline void
      remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
                                    no_property&)
      {
        for (typename EdgeList::iterator i = el.begin();
             i != el.end(); ++i)
          if ((*i).get_target() == e.m_target) {
            el.erase(i);
            return;
          }
      }

    } // namespace detail

    template <class Config>
    struct directed_edges_helper {

      // 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::graph_type graph_type;
        graph_type& g = static_cast<graph_type&>(*this);
        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
        typedef typename Config::OutEdgeList::value_type::property_type PType;
        detail::remove_directed_edge_dispatch(e, el,
                                              *(PType*)e.get_property());
      }

      // O(1)
      inline void
      remove_edge(typename Config::out_edge_iterator iter)
      {
        typedef typename Config::graph_type graph_type;
        graph_type& g = static_cast<graph_type&>(*this);
        typename Config::edge_descriptor e = *iter;
        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
        el.erase(iter.base());
      }

    };

    // O(1)
    template <class Config>
    inline std::pair<typename Config::edge_iterator, 
                     typename Config::edge_iterator>
    edges(const directed_edges_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.vertex_set().begin(), 
                                           g.vertex_set().begin(), 
                                           g.vertex_set().end(), g),
                             edge_iterator(g.vertex_set().begin(),
                                           g.vertex_set().end(),
                                           g.vertex_set().end(), g) );
    }

    //=========================================================================
    // Directed Graph Helper Class

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

    template <class Config>
    struct directed_graph_helper
      : public directed_edges_helper<Config> { 
      typedef typename Config::edge_descriptor edge_descriptor;
      typedef adj_list_dir_traversal_tag traversal_category;
    };

    // O(E/V)
    template <class Config>
    inline void
    remove_edge(typename Config::vertex_descriptor u,
                typename Config::vertex_descriptor v,
                directed_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_);
      detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
    }

    template <class Config, class Predicate>
    inline void
    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
                       directed_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      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 edge_parallel_category;
      detail::remove_directed_edge_if_dispatch
        (first, last, g.out_edge_list(u), pred, edge_parallel_category());
    }

    template <class Config, class Predicate>
    inline void
    remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::vertex_iterator vi, vi_end;
      for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        remove_out_edge_if(*vi, pred, g);
    }    

    template <class EdgeOrIter, class Config>
    inline void
    remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
    {
      g_.remove_edge(e_or_iter);
    }

    // O(V + E) for allow_parallel_edges
    // O(V * log(E/V)) for disallow_parallel_edges
    template <class Config>
    inline void 
    clear_vertex(typename Config::vertex_descriptor u,
                 directed_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::vertex_iterator vi, viend;
      for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
        detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
      g.out_edge_list(u).clear();
      // clear() should be a req of Sequence and AssociativeContainer,
      // or maybe just Container
    }

    template <class Config>
    inline void 
    clear_out_edges(typename Config::vertex_descriptor u,
                    directed_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_);
      g.out_edge_list(u).clear();
      // clear() should be a req of Sequence and AssociativeContainer,
      // or maybe just Container
    }

    // O(V), could do better...
    template <class Config>
    inline typename Config::edges_size_type
    num_edges(const directed_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type graph_type;
      const graph_type& g = static_cast<const graph_type&>(g_);
      typename Config::edges_size_type num_e = 0;
      typename Config::vertex_iterator vi, vi_end;
      for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        num_e += out_degree(*vi, g);
      return num_e;
    }
    // O(1) for allow_parallel_edge_tag
    // O(log(E/V)) for disallow_parallel_edge_tag
    template <class Config>
    inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
    add_edge(typename Config::vertex_descriptor u, 
             typename Config::vertex_descriptor v,
             const typename Config::edge_property_type& p, 
             directed_graph_helper<Config>& g_)
    {
      typedef typename Config::edge_descriptor edge_descriptor;
      typedef typename Config::graph_type graph_type;
      typedef typename Config::StoredEdge StoredEdge;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::OutEdgeList::iterator i; 
      bool inserted;
      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
                                            StoredEdge(v, p));
      return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 
                            inserted);
    }