
Boost : 
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 20070711 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:undirectedgraphs):
> 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 BoyerMyrvold
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 selfloops?
> >
> >
> > It's undefined on anything that isn't an undirected graph with no
> > selfloops and no parallel edges. The BoyerMyrvold 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 viseversa.
>
> 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 LEDAbased 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 selfloops 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 endpoint nodes, I
> suppose.
>
> Do you know which steps of the algorithm rely on there being no
> selfloops or parallel edges?
>
I modified the implementation so that everything works correctly in
the presence of selfloops 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
selfloops. Please let me know how it works for you.
Regards,
Aaron
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk