On Sun, May 13, 2012 at 3:05 AM, H. S. Teoh <[email protected]> wrote: > On Sat, May 12, 2012 at 11:07:41PM +0200, Philippe Sigaud wrote: > [...] >> 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. > [...] > > I don't know if this is overly ambitious, but I was thinking along the > lines of a completely generic duck-typed graph interface for graph > algorithms, so the algorithms will work for any kind of structs/classes > that implement the right methods for graph access.
I don't think that's overly ambitious. IIRC, that's what I did. I have isNode!(T) and isEdge!(T) templates and the algorithms accept any type that fulfils the conditions. The idea is that some algorithms just ask for the standard run-of-the-mill graph 'interface' (à la range): * give me the value of the current node (or "give me the node with this identifier") * give me outgoing edges (possibly a range instead of an array, hence possibly infinite, btw) (optionally: * give me the ingoing edges) and an edge is any type that exposes '.from' and '.to' members that returns nodes, and possibly other fields. Have a look at https://github.com/PhilippeSigaud/dranges/blob/master/graph.d https://github.com/PhilippeSigaud/dranges/blob/master/graphalgorithm.d https://github.com/PhilippeSigaud/dranges/blob/master/graphrange.d The main question you must ask yourself is: "what kind of inner storage do I use to represent the graph?". > > For example, say I have a grid of voxels representing some kind of game > world, where adjacent voxels within a certain height difference are > considered "reachable" and voxels with greater height difference are > considered "unreachable". I'd like to be able to invoke graph > reachability algorithms on the grid directly, by defining methods that > expose a kind of graph-like interface to the grid (e.g., enumerate edges > given a particular location, enumerate locations, etc.) without having > to explicitly construct a separate graph object to represent > reachability. Yes, that's quite doable. It's a reachability algorithm, with a passed predicate. The default predicate would be to test for edge existence, whereas in your above case, one must test for height difference between nodes. > Graph algorithms generally tend to assume a particular kind of > representation for the graph; we may classify graphs into different > types depending on what kind of operations are expected (analogous to > std.range where we have input ranges, output ranges, forward ranges, > etc.). Is a graph a container or a range? A graph may *expose* a particular (linear or otherwise) range, but it's a container, for me.
