adjacency_list.hpp

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

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

      typedef typename Config::global_edgelist_selector
        global_edgelist_selector;

      //    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)
          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
                                true);
        else
          return std::make_pair(edge_descriptor(u, v, 0), false);
      }
    };

    template <class Config, class Base>
    inline std::pair<typename Config::adjacency_iterator, 
                     typename Config::adjacency_iterator>
    adjacent_vertices(typename Config::vertex_descriptor u, 
                      const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      typedef typename Config::adjacency_iterator adjacency_iterator;
      typename Config::out_edge_iterator first, last;
      boost::tie(first, last) = out_edges(u, g);
      return std::make_pair(adjacency_iterator(first, &g),
                            adjacency_iterator(last, &g));
    }
    template <class Config, class Base>
    inline std::pair<typename Config::inv_adjacency_iterator, 
                     typename Config::inv_adjacency_iterator>
    inv_adjacent_vertices(typename Config::vertex_descriptor u, 
                          const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
      typename Config::in_edge_iterator first, last;
      boost::tie(first, last) = in_edges(u, g);
      return std::make_pair(inv_adjacency_iterator(first, &g),
                            inv_adjacency_iterator(last, &g));
    }
    template <class Config, class Base>
    inline std::pair<typename Config::out_edge_iterator, 
                     typename Config::out_edge_iterator>
    out_edges(typename Config::vertex_descriptor u, 
              const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      typedef typename Config::out_edge_iterator out_edge_iterator;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      return
        std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
                       out_edge_iterator(g.out_edge_list(u).end(), u));
    }
    template <class Config, class Base>
    inline std::pair<typename Config::vertex_iterator, 
                     typename Config::vertex_iterator>
    vertices(const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& cg = static_cast<const AdjList&>(g_);
      AdjList& g = const_cast<AdjList&>(cg);
      return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
    }
    template <class Config, class Base>
    inline typename Config::vertices_size_type
    num_vertices(const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& g = static_cast<const AdjList&>(g_);
      return g.vertex_set().size();
    }
    template <class Config, class Base>
    inline typename Config::degree_size_type
    out_degree(typename Config::vertex_descriptor u, 
               const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type AdjList;
      const AdjList& g = static_cast<const AdjList&>(g_);
      return g.out_edge_list(u).size();
    }
    template <class Config, class Base>
    inline std::pair<typename Config::edge_descriptor, bool>
    edge(typename Config::vertex_descriptor u, 
         typename Config::vertex_descriptor v, 
         const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_parallel_category Cat;
      const Graph& g = static_cast<const Graph&>(g_);
      return g_.edge_dispatch(g, u, v, Cat());
    }
    template <class Config, class Base>
    inline std::pair<typename Config::out_edge_iterator,
                     typename Config::out_edge_iterator>
    edge_range(typename Config::vertex_descriptor u,
               typename Config::vertex_descriptor v,
               const adj_list_helper<Config, Base>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::StoredEdge StoredEdge;
      const Graph& cg = static_cast<const Graph&>(g_);
      Graph& g = const_cast<Graph&>(cg);
      typedef typename Config::out_edge_iterator out_edge_iterator;
      typename Config::OutEdgeList& el = g.out_edge_list(u);
      typename Config::OutEdgeList::iterator first, last;
      typename Config::EdgeContainer fake_edge_container;
      tie(first, last) = 
        std::equal_range(el.begin(), el.end(), 
                         StoredEdge(v, fake_edge_container.end(),
                                    &fake_edge_container));
      return std::make_pair(out_edge_iterator(first, u),
                            out_edge_iterator(last, u));
    }

    template <class Config>
    inline typename Config::degree_size_type
    in_degree(typename Config::vertex_descriptor u, 
              const directed_edges_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      const Graph& cg = static_cast<const Graph&>(g_);
      Graph& g = const_cast<Graph&>(cg);
      return in_edge_list(g, u).size();
    }

    namespace detail {
      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type,
        Property>::type
      get_dispatch(adj_list_helper<Config,Base>&, Property, 
                   boost::edge_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::type PA;
        return PA();
      }
      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type, 
        Property>::const_type
      get_dispatch(const adj_list_helper<Config,Base>&, Property, 
                   boost::edge_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::const_type PA;
        return PA();
      }

      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type, 
        Property>::type
      get_dispatch(adj_list_helper<Config,Base>& g, Property, 
                   boost::vertex_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::type PA;
        return PA(&static_cast<Graph&>(g));
      }
      template <class Config, class Base, class Property>
      inline
      typename boost::property_map<typename Config::graph_type,
        Property>::const_type
      get_dispatch(const adj_list_helper<Config, Base>& g, Property, 
                   boost::vertex_property_tag) {
        typedef typename Config::graph_type Graph;
        typedef typename boost::property_map<Graph, Property>::