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/