Range-Based Graph Search in D (blog post)

[qznc]

On Thursday, 9 January 2014 at 22:04:16 UTC, 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. As we don't 
> yet have a graph library for D, it would be interesting to 
> discuss APIs in general.

Beautiful!

I was thinking about something like this myself. Your code and 
your compositional examples are nicer than I expected something 
like this to turn out.

For the visitation API design: Your map approach (bool[Vertex] 
m_visited) is probably the most generic one.

A variant, where the nodes store the flag internally is more 
efficient, though.
Since you do not want to walk the whole graph to reset the flag, 
a counter is more appropriate for multiple walks. You (or the 
graph data structure) must remember the current flag count. So 
the basic idea is: A vertex contains a counter/flag initialized 
with zero. On visiting it, the counter is increased to a the 
global value. Visit can be checked by comparing it to a global 
value.

Maybe a special vertex interface check could be used similar to 
isInputRange.

template isFlaggedVertex(R)
{
     enum bool isFlaggedVertex = is(typeof(
     (inout int = 0)
     {
         int global_value = 1;
         R v = void;                         // can define a 
vertex object
         if (r.is_visited(global_value)) {}  // can test for 
visited
         r.mark_visited(global_value);       // can mark as visited
     }));
}

Depending on this check, the search functions could use internal 
or external visit mechanisms.