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
> >>>>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
> >>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,
> 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
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
The planarity test/embedding algorithms require an undirected graph
that models the concepts VertexAndEdgeListGraph and IncidenceGraph
(both described here:
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
> >>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!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk