path planning implementations?

[Philippe Sigaud]

On Sat, May 12, 2012 at 8:39 PM, Gor Gyolchanyan
<gor.f.gyolchanyan at gmail.com> wrote:
> ok, I'll fork from phobos and get down to busyness.

Maybe you should launch another thread on what features such a module
should contain. As was linked upstream in this thread, I wrote a small
generic Graph (+ algos + ranges) module on this a few years ago, so
I'm interested in hearing your take on this. All on all, I had great
fun in writing the algos and the factory function.That was my first
real dabbling in template constraints.

Also, seeing the crowd here, I guess Boost::Graph will be the
yardstick with which you'll be measured. Did you have a look at it?

Anyway, here is what I would like a graph module to have:

- directed and undirected graphs
- templated nodes
- templated edges: I want the possibility to start from a weighted
graph and to create a graph with no info in edges, for example.
- a way to get a range on a graph, to as to leverage std.algorithm goodness.
- adding, deleting nodes and edges
- adding a entire graph to another graph
- merging or splitting of edges and nodes
- policies! Are multiple edges authorized? Dangling edges? How are the
nodes and edges stored (dense graph or sparse graph)
- bidirectional graphs (that is, given a node, gives access to all
ancestors, probably through a node property)
(- branching ranges)
- factory functions for standard graphs: linear, circle, grid, etc.
- standard graph operations: search and path algorithms of course,
transitive closure, metagraph,...


But, you know, you could say that a graph is a container (though we
are interested not only by what it contains, but also by its the
global 'shape'). This opens the same can of worms as for any other
containers: memory, element possession, relation to ranges, and so on.
We are still waiting for Andrei's design on D allocators.


Philippe