[Boost-users] [BGL] "undirected" edges in a directed graph

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2006-05-10 16:46:46

Hi people,

I'm interfacing an algorithm to a data structure via the BGL (that is, I'm 
presenting the DS as a BGL graph along with various property maps)

My data structure is the so-called Halfedge Data Structure (HDS) used in 
geometric modeling. If the faces of the HDS are not considered, a HDS is a 
form of Planar Directed Graph (PDG) with the particularity that for any two 
adjacent vertices p and q, there is an edge from p to q and an opposite edge 
from q to p.
Obtaining the "opposite" edge of any edge is O(1)

The structure is called HalfedgeDS because there is always a pair of "Joint 
Opposite Directed Edges", called halfedges, between p and q : p->q and q->p.

Any HDS can be mapped as a BGL graph by simply specializing graph_traits and 
the global functions accordingly. It just needs as an extension an 
"opposite_edge" operation.

With the "opposite_edge" extension this works like a charm, but there is 
still one small thing that is natural in the HDS that I'm not sure how to 
best map to the BGL:

Since between any two adjacent vertices p and q there are exactly 2 joint 
opposite directed edges (that is, two halfedges): p->q and q->p, there is 
always a very well defined UNDIRECTED view of the HDS: simply considering an 
arbitraty one of each of the two joint opposite directed edges between any 
two adjacent vertices.

Any edge here (which is a directed edge) can be used an "undirected" edge 
due to the availability of the opposite_edge() operation.

There is at least one operation that needs such an undirected view of the 
HDS: iterate (not traverse but iterate) all "edges" of the HDS (not 
"halfedges"). This is of course possible with an ordinary dgraph but much 
more expensive as it requires the algorithm to filter out halfedges whose 
opposite was already iterated. Typical instances of a HDS store opposite 
halfedges pairwise, thus, iterating over all halfedges but stepping 2 at a 
time, iterates over "undirected edges" very efficienty. This requires a 
special iterator that is different from the halfedge iterator (and is 
tyipically provided by HDS models).

>From a concept POV I would say that a HDS is a new BGL graph concept.
It would call it a "JODE" Graph instead of a "HDS" Graph becasue in the HDS 
jargon an "edge" is a pair of "halfedges" while in the BGL an "edge" is the 
actual edge (a directed edge in this case).

Such a JODE Graph concept would include the "opposite_edge" operation and 
the definition of "undirected_edge_iterator", which would iterate over 1 out 
of the 2 opposite halfedges (Joint Opposite Directed Edges), along with the 
"undirected_edges" accesor.

So far so good... nut I have a problem: where do I put the 
"undirected_edge_iterator" type??

AFAICT I cannot add an additional type to graph_traits, right?
Is subclassing graph_traits a good alternative?
Or is there a better way?

TIA

-- 
Fernando Cacciola
SciSoft
http://fcacciola.50webs.com/