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.


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.


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.

Reply via email to