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

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
>>>>>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?

[...]
>>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 ...

Regards,

Jens