Range-Based Graph Search in D (blog post)

[Timon Gehr]

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.