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/