adjacency_list.hpp

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

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

    template <class Config>
    inline typename Config::degree_size_type
    in_degree(typename Config::vertex_descriptor u,
              const undirected_graph_helper<Config>& g_)
    { return degree(u, g_); }

    //=========================================================================
    // 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;
    };

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

    template <class Predicate, class Config>
    inline void
    remove_edge_if(Predicate pred, bidirectional_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);
      }
    }

    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, 
                     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>
    {
      typedef typename Config::graph_type graph_type;
      typedef typename Config::out_edge_iterator out_edge_iterator;
      
      std::pair<out_edge_iterator, out_edge_iterator>
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
                                const graph_type& g,
                                void*)
      { return out_edges(source(e, g), g); }

      std::pair<out_edge_iterator, out_edge_iterator>
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
                                const graph_type& g,
                                setS*)
      { return edge_range(source(e, g), target(e, g), g); }

      std::pair<out_edge_iterator, out_edge_iterator>
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
                                const graph_type& g,
                                multisetS*)
      { return edge_range(source(e, g), target(e, g), g); }

#if !defined BOOST_NO_HASH
      std::pair<out_edge_iterator, out_edge_iterator>
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
                                const graph_type& g,
                                hash_setS*)
      { return edge_range(source(e, g), target(e, g), g); }
#endif

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

      // O(E/V) or O(log(E/V))
      void
      remove_edge(typename Config::edge_descriptor e)
      {
        typedef typename Config::global_edgelist_selector EdgeListS;
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        graph_type& g = static_cast<graph_type&>(*this);

        typedef typename Config::edgelist_selector OutEdgeListS;

        std::pair<out_edge_iterator, out_edge_iterator> rng = 
          get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
        rng.first = std::find(rng.first, rng.second, e);
        assert(rng.first != rng.second);
        remove_edge(rng.first);
      }

      inline void
      remove_edge(typename Config::out_edge_iterator iter)
      {
        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&>(*this);
        typename Config::edge_descriptor e = *iter;
        typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
        typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
        typedef typename Config::OutEdgeList::value_type::property_type PType;
        PType& p = *(PType*)e.get_property();
        detail::remove_directed_edge_dispatch(*iter, iel, p);
        g.m_edges.erase(iter.base()->get_iter());
        oel.erase(iter.base());
      }
    };

    // 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::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(in_edge_list(g, v), u, Cat());
    }

    // 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_)
    {
      typedef typename Config::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

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

      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::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