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

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost