
Boost : 
Subject: Re: [boost] [graph]Direct Edge Access
From: Takatoshi Kondo (redboltz_at_[hidden])
Date: 20130307 19:30:02
Hi Jeremiah,
Thank you for your reply. I'm relieved that I understand correctly. I
come up with a related question.
I think that general graph algorithm developers should test two
different things.
One is concepts. If function my_algo() required
VertexAndEdgeListGraphConcept for the parameter g, it should be
checked as follows:
#include <boost/graph/graph_concepts.hpp>
template <typename Graph>
void my_algo(Graph g) {
BOOST_CONCEPT_ASSERT(( boost::VertexAndEdgeListGraphConcept<Graph> ));
boost::edge(0, 1, g); // accidental invalid use ... Line A
}
But this test cannot detect out of concepts functions usage as Line A
if class Graph accidentally provide them.
So, these problems should be detected the following test:
void my_algo_test() {
typedef /* Only satisfies VertexAndListGraphConcept*/ Graph; // ... Line B
Graph g;
my_algo(g);
}
How do I define the type that is only satisfied specific concepts?
Thanks,
Taka
On Thu, Mar 7, 2013 at 10:57 AM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> 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
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk