On 01/09/2014 11:04 PM, Peter Alexander wrote:

Trying to write a bit more about D on my blog now. To start, I've written about a proof-of-concept range-based API for graph search.http://poita.org/2014/01/09/range-based-graph-search-in-d.html I'd greatly appreciate any feedback on the design.

I like the general direction.

`One issue with the API is that it does not deal with graphs with more`

`than one edge between two given vertices very well. I think it'd need a`

`separate edge abstraction. (Formally, a graph is just a pair of sets`

`(V,E) with two functions from E to V giving you start and end vertex of`

`an edge.)`

`A graph search can have more properties than just the sequence of`

`visited edges, so maybe it is not a range, but just provides a range.`

`(And maybe also a range of events, usable instead of callbacks, maybe a`

`DFS tree etc.)`

`Allocation of memory for visited flags and the like should be`

`controllable. Maybe the design should even allow using persistent data`

`structures for storing visited flags, such that the search range can be`

`used as a value type / forward range.`

As we don't yet have a graph library for D, it would be interesting to discuss APIs in general. -Peter

`Probably it would be worthwhile to explore a design that is similar to`

`Phobos ranges at some level. I.e. support kinds of graphs with different`

`capabilities. (Eg. your implicitGraph cannot enumerate all vertices or`

`edges that are present in the Graph. The least capable graph kind`

`reasonably supported might not even be able to quickly report all`

`adjacent edges to a vertex. Some graphs may allow in-place mutation`

`etc.) Then provide some explicit representations with high capabilities`

`and helper functions to convert certain representations to (more)`

`explicit representations. (similar to constructing eg. an array from a`

`range.) Constructions on graphs would then return implicit representations.`