Boost logo

Boost :

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 (also planar_graphs.tar.gz) and contains
>>>>>the .hpp files, the documentation, and the examples. The second is called
>>>>> (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?

>>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
> ( 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 ...



Boost list run by bdawes at, gregod at, cpdaniel at, john at