[boost] [graph]Direct Edge Access

Subject: [boost] [graph]Direct Edge Access
From: Takatoshi Kondo (redboltz_at_[hidden])
Date: 2013-03-07 13:49:00

Hello,

I'm using Boost.Graph version 1.53.0. I'm trying to write some graph
algorithms and I want to minimize the requirements of the input graph.
I have a question about Boost.Graph concepts. I wrote a very simple
code as follows:

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::bidirectionalS> G;

int main() {
    G g;
    boost::add_edge(0, 1, g);
    auto res = boost::edge(0, 1, g); // Why can I call it?
    std::cout << std::boolalpha << res.second <<  std::endl;
    boost::graph_traits<G>::edge_descriptor e = res.first;
    std::cout << boost::source(e, g) << "," << boost::target(e, g) << std::endl;
}

It works, but I don't understand why I can call boost::edge().

According to the following document, AdjacencyMatrix concept provides
Direct Edge Access functionality, so I can call edge(u,v,g) :
http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/AdjacencyMatrix.html

The class template adjacency_list is a model of
VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible,
Assignable, and Serializable.
http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/adjacency_list.html

So, adjacency_list is not satisfied AdjacencyMatrix concept.

I checked which function template is called, then I found the
following function is called:

boost/graph/detail/adjacency_list.hpp:1582

    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::StoredEdge StoredEdge;
      const Graph& cg = static_cast<const Graph&>(g_);
      typedef typename Config::out_edge_iterator out_edge_iterator;
      const typename Config::OutEdgeList& el = cg.out_edge_list(u);
      typename Config::OutEdgeList::const_iterator it = graph_detail::
        find(el, StoredEdge(v));
      return std::make_pair(
               typename Config::edge_descriptor
                     (u, v, (it == el.end() ? 0 : &(*it).get_property())),
               (it != el.end()));
    }

Also, I found the following document:
http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/using_adjacency_list.html
This document describes that:
edge()
The time complexity for this operation is O(E/V) when the OutEdgeList
type is a Sequence and it is O(log(E/V)) when the OutEdgeList type is
an AssociativeContainer.
It seems that edge() is a part of the public interface of
adjacency_list. But I think that it is not a part of any graph
concepts.
If I want to write an algorithm that depends on several graph
concepts, not actual classes such as adjancency_list, I can use
edge(u,v,g) only if the input graph class satisfies AdjacencyMatrix
concept.

Am I understanding correctly?

Thanks,
Taka