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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-07-11 21:27:15

On 7/5/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> Aaron Windsor wrote:
> > On 7/2/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> >
> >>Aaron Windsor wrote:
> >>
> >>>I've put two sets of files in the vault under Home/Algorithms/graph: the
> >>>first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains
> >>>the .hpp files, the documentation, and the examples. The second is called
> >>>planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains
> >>>over 1000 test graphs and a small program that can be compiled to give an
> >>>example of how these planar graph tools can be used. I'd appreciate any
> >>>comments!
> >>
> >>
> >>1. It would be nice if bidirectional graphs could be supported as well.
> >
> >
> > Hi Jens,
> >
> > Thanks for taking a look at my implementation. Yes, it would be nice
> > if bidirectional graphs were supported - they should be, and if it
> > doesn't turn out to be too much trouble, I'd like to support them.
> > I'll check on this when I have a little more time over the next couple
> > of days.
>
> IMO, the only difference between undirected and bidirectional graphs is
> (see
> http://www.boost.org/libs/graph/doc/graph_concepts.html#sec:undirected-graphs):
> that in bidirectional graphs, you have to iterate over in and out edges
> seperately. Even source(e) and target(e) are used the same ...
>

I'm not sure I understand your point on bidirectional graphs.
bidirectional graphs offer the in_edges and in_degree functions, but
for undirected graphs, these two functions will yield the same thing
as out_edges and out_degree, respectively. So the distinction only
really matters for directed graphs, right? In any event, I checked the
implementation and updated the documentation of the Boyer-Myrvold
planarity test so that it specifies that the algorithm requires an
undirected graph that models both the IncidenceGraph and
VertexAndEdgeListGraph concepts. Since BidirectionalGraph is a
refinement of IncidenceGraph, it is supported. Am I still missing your
point?

> >>3. What is your implementation doing when the graph is not undirected or
> >>when there are self-loops?
> >
> >
> > It's undefined on anything that isn't an undirected graph with no
> > self-loops and no parallel edges. The Boyer-Myrvold algorithm relies
> > on several computations on an undirected DFS tree like lowpoint, least
> > ancestor, and the full suite of planar testing/embedding/drawing
> > algorithms rely on some algorithms that are only defined on undirected
> > graphs, like testing simple connectivity and finding biconnected
> > components. This is a case when it would be nice to have some adapters
> > in the BGL to treat directed graphs as undirected or vise-versa.
>
> You mean bidirectional graphs ;-) Yes, that would be nice, and not that
> very much complicated, I suppose. I just replied to a post by Benoit
> from November 2006 who asked for a bidirectional->undirected adapter as
> well. Maybe my bidirectional->"bidirected" adapter can serve as a
> starting point, which is in turn based on the graph reversal adapter by
> David Abrahams.
>
> When I now think of it, I wonder wether it would have been feasible to
> use a undirected graph for this - I suppose yes ... Probably my design
> choice was due to the original LEDA-based implementation I'm working
> with, which called G.make_bidirected(). Gotta take a look on it.
>
> That, of course, does not solve the problem with self-loops and parallel
> edges. IMO, it should be possible to construct planar embeddings for
> graphs containing them, as well. Maybe deleting them from the graph
> first and later "multiplying" edges again? This would mean adding them
> in opposite order in the adjacency lists of the two end-point nodes, I
> suppose.
>
> Do you know which steps of the algorithm rely on there being no
> self-loops or parallel edges?
>

I modified the implementation so that everything works correctly in
the presence of self-loops and multiple edges. I just uploaded the
latest source to the vault, so give it a try if you're interested
(http://tinyurl.com/2dltju). All of the algorithms: planarity
testing/embedding, kuratowski subgraph isolation, the planar face
traversal, and straight line drawing now handle parallel edges and
self-loops. Please let me know how it works for you.

Regards,
Aaron