Re: [boost] [graph]Direct Edge Access

Subject: Re: [boost] [graph]Direct Edge Access
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-03-07 13:57:59

On Thu, 7 Mar 2013, Takatoshi Kondo wrote:

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

That's right; it (and a few other graph types) provide edge() but do not 
satisfy the complexity requirement for it given in the Adjacency Matrix 
concept.

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

You are right: the one with that complexity is public but not in a concept 
officially.

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

Yes.  You might want to consider using lookup_edge() from 
<boost/graph/lookup_edge.hpp>; it will use edge() for graphs that model 
Adjacency Matrix and do a manual search of a vertex's out_edges() for 
other Incidence Graph models.  That will make your algorithms work on all 
Incidence Graphs but get the better performance when possible.  Note that 
lookup_edge() will not take advantage of logarithmic-time edge() functions 
available in some graphs that do not model Adjacency Matrix, however; it 
either uses a constant-time implementation or falls back to linear search. 
The edge() function that you found will itself use linear search in many 
cases, however.

-- Jeremiah Willcock