From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-07-23 11:47:51
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.
>>>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
>>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
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
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?
>>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
So I hope we can solve our misunderstandings concerning terminology ...
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk