Range-Based Graph Search in D (blog post)

[Peter Alexander]

On Saturday, 11 January 2014 at 03:53:28 UTC, Timon Gehr wrote:
> 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.)

I was thinking of changing the adjacency list to return a range 
of edges instead. That may solve the problem. It also solves the 
problem of the edgeWeight API being inefficient for certain graph 
data structures.


> 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.)

A range of events would be interesting. You could then get a 
range of different events by filtering:

graph.depthFirstSearchEvents(start).filter!(e => e.type == 
Event.node).map!(e => e.node);

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.

Absolutely. I'm leaving things like memory allocation API until 
later and focussing on the general usability and flexibility.


> 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.

Yah, I only implemented implicit graph first due to it's simple 
representation. It's mainly useful for infinite graphs like game 
trees and works well for some other simple graph types, but 
certainly there will be a need for other types of graph 
(adjacency matrices, edge lists, adjacency lists, etc.)

It's also a very minimal graph type, which is useful for testing 
a generic API. I want the algorithms to require only as much as 
necessary from the graph representation. If users have to 
construct large graph data type with many mandatory member 
functions then I would be unhappy.

Thanks for all the feedback.