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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-07-24 07:23:23

On 7/23/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> Aaron Windsor wrote:
> > 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?
> >
>
> Hmm, I'm not sure if we're talking about the same things.
>
> In an undirected graph, each edge appears in the out_edges list of both
> incident vertices.
>
> In a bidirectional graph, it appears only in the out_edges list of one
> incident vertex (the source), and the in_edges list of the other.
>
> I don't really know what you mean by a graph that is both an undirected
> graph and a BidirectionalGraph.
>
> My graph typedef looks as follows:
>
> typedef boost::adjacency_list<boost::vecS, boost::vecS,
> boost::bidirectionalS,
>    VertexProperties, boost::property<boost::edge_index_t, long,
> EdgeProperties> > BoostGraph;
>
> bidirectionalS and undirectedS are two different options, or am I
> missing something here?

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.

> [...]
> >>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.
>
> Well, I tested it with the same graph as before (read from file into the
> abovementioned BoostGraph type; for every edge there is also a reverse
> edge already in the original data).
>
> [The difference to an undirected graph is that there the reverse edge is
> the edge itself, here it is a different one]
>
> Well, the planarity test says it is planar, so the implementation looks
> really good!
>
> So I hope we can solve our misunderstandings concerning terminology ...
>

Glad to hear it!

Regards,
Aaron