Re: [boost] [BGL] Tools for planar graph testing/embedding/drawing in the vault

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-08-14 07:28:10

On 8/13/07, Jens Müller <jens.mueller_at_[hidden]> 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