
Boost : 
Subject: Re: [boost] [graph]Direct Edge Access
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20130307 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 logarithmictime edge() functions
available in some graphs that do not model Adjacency Matrix, however; it
either uses a constanttime implementation or falls back to linear search.
The edge() function that you found will itself use linear search in many
cases, however.
 Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk