I am working on an optimization algorithm that makes much use of shortest-paths and near-neighbor concepts.

To get a reasonable near-neighbor search on points on the Euclidean plane, I have implemented (mostly) a Delaunay tree as a Boost graph. The points on the graph represent points in space, and are unique. I make use of angles and cosines and such to find neighbors and so on. The Delaunay graph is a basis for the optimization and shortest-paths stuff, which encompasses concepts other than just points-in-space, like type-of-point and so on. The basic idea is that when I am traversing my graph looking for optimal paths and such, I use the Delaunay graph to find near neighbors.

Now, here is the problem: my graph really needs for vertices to share points in space. Each vertex has a location and other properties, so there needs to be several vertices at one point. To have a Delaunay graph with coincident points is not really meaningful; the geometry gets really weird (e.g. what is the angle between three coincident points?).

So I had figured I could build the Delaunay graph, and put a thin layer on it that handled reference counts for points in space, and stored vertices with all their attendant extra information. So I would make a class that had a map<> of points-in-space and their refcounts, and as I added or deleted points I would bump the counter. As far as the Dr. Delaunay knew, all points would be unique; every coincident point would share it's neighbors with it's brothers.

Problem is, how to do a (for instance) breadth-first search over this graph, in which the graph algorithm needs to "see" each point individually?

My thinking right now is that I can have my structure as described and build a custom iterator, then pass the iterator to the various search algorithms and visitors and what not. The iterator would have the intelligence to sort out the non-unique points.

So the simple question is: am I on the right track? Is this kind of thing feasible or supported by the library? If it is, how do I specify my iterator to the various algorithms?

Alternatively, does anyone know if it is possible to build a Delaunay graph with coincident points that has geometric meaning, i.e. preserves the properties we associate with Delaunay graphs? This is really a math question ...

Sorry if this is incoherent, it is late and I need to get it off my chest.

Eric