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.
