On 8/13/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
When I'm saying "BidirectionalGraph", I'm talking about the concept (http://www.boost.org/libs/graph/doc/BidirectionalGraph.html), which can be modeled by both undirected and directed graphs. When you're saying "bidirectional graph", it seems to me that you're talking about a directed graph that models the BidirectionalGraph concept (an adjacency_list with the bidirectionalS property selector is such a graph). But undirected graphs can also model the BidirectionalGraph concept (for example, an adjacency_list with the undirectedS property selector).
The planarity test/embedding algorithms require an undirected graph that models the concepts VertexAndEdgeListGraph and IncidenceGraph (both described here: http://www.boost.org/libs/graph/doc/graph_concepts.html). Furthermore, BidirectionalGraph is a refinement of IncidenceGraph, so if you have an undirected graph that models BidirectionalGraph and VertexAndEdgeListGraph, that will work as well. But it must be an undirected graph.
Hmm, ok, I think I got it. Would it be possible to treat directed graphs as well? After all, a directed graph is conceptually the same as an undirected graph with additional edge labels designating source and target ...
No, again, I don't think directly supporting directed graphs is the way to go. The Boyer-Myrvold algorithm is based on a depth-first traversal of an undirected graph, and algorithms such as connected components and biconnected components are used elsewhere as subroutines. All of these take undirected graphs as input, so I think the right thing to do is to create an undirected adapter class for a directed graph and pass in the adapted directed graph. Regards, Aaron