On 7/2/07, Jens Müller <jens.mueller@ira.uka.de> 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.
2. I have an (directed) graph which should be planar:
http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250.graphml
I read it into a LEDA graph using the GraphML reader from graph-tool. LEDA confirms that the graph is indeed planar.
To test it with your implementation, I changed it to undirected
edges:
http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250-undirected.graphml
I read it into a boost::adjacency_list with undirectedS directionality (instead of bidirectionalS which I would be using normally), and boyer_myrvold_planarity_test returns false ...
Maybe you can take a look at the graph?
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.
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. Regards, Aaron