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

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-07-05 10:30:29

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

[...]
> 
> It's because you've got parallel edges - each edge is repeated twice
> (for example, {n0,n2} shows up as source=n0, target=n2 and source=n2,
> target=n0). I cleaned up the file and ran it through my code and it
> was recognized as a planar graph.
> 

Args - sorry, that is a "feature" of the generators we use here ...

> 
>>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?

Regards,

Jens