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.

-Peter

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.

Peter Alexander:

> http://poita.org/2014/01/09/range-based-graph-search-in-d.html

I'd like to see the usage of a not implicit graph.

Regarding this line:

static d(string a, string b) { return zip(a, b).count!"a[0] != a[1]"; }

An alternative:

enum dist = (in string s, in string s2) pure =>
    s1.zip(s2).count!(ab => ab[0] != ab[1]);

It's a use case for some tuple unpacking syntax:

enum dist = (in string s1, in string s2) pure =>
    s1.zip(s2).count!(@{a, b} => a != b);

Bye,
bearophile

On Thursday, 9 January 2014 at 22:54:11 UTC, bearophile wrote:
> Peter Alexander:
>
>> http://poita.org/2014/01/09/range-based-graph-search-in-d.html
>
> I'd like to see the usage of a not implicit graph.

There is a crude example in the unit test in the file.

You could actually create an non-implicit graph using implicitGraph:

auto adjacencyLists[nVerts] = [...];
auto graph = implicitGraph!(int, i => adjList[i]);


> Regarding this line:
>
> static d(string a, string b) { return zip(a, b).count!"a[0] != a[1]"; }
>
> An alternative:
>
> enum dist = (in string s, in string s2) pure =>
>     s1.zip(s2).count!(ab => ab[0] != ab[1]);

True, I tried to make it as short as possible so it fit on one line in my blog :-)

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

Put it on reddit:
http://www.reddit.com/r/programming/comments/1uvgvi/rangebased_graph_search_in_d/

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

Nice :)

I presume you are aware of https://github.com/WebDrake/Dgraph

On Friday, 10 January 2014 at 11:07:13 UTC, John Colvin wrote:
> Nice :)
>
> I presume you are aware of https://github.com/WebDrake/Dgraph

Good inspiration for me to get back to work on that :-)

@Peter -- this is really exciting to see and I will be looking into your work with great interest.  Let me know if there is any overlap in our projects that we can make use of.  At first glance (I'm in the midst of house-moves right now so can't give your code the attention it deserves immediately:-) it is interesting to see how our algorithms and problems of interest have resulted in different design concerns.

We should definitely try and set up some mutual coding challenges to try and test scalability, performance etc. :-)

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.

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

I really like it, very elegant! Certain lines brought a smile to my
lips :-) (using anonymous functions as graph parameters, for example).
Much more elegant than my own graph code :)

You wanted suggestions, here are a few. They come from my use of graphs: not so much as search-based, but as a way to store and modify 'relationships' (call graphs, import graphs) or to use them as support for state machines.

* I sometimes have to use graphs with more than just `weight` on edges (names as strings, chars, for example for a state machine, etc). Do you think you could extend your design to allow parameterization on edges? Of course, to use the search algorithms, the user should provide an way to get a priority from the edges. Or any user-defined type could be used, ideally, as long as it provides a way to get a `size_t`.

* I'd like a way to map on a graph (keeping the edge structure, but changing the nodes contents). I know I can map on your search result, but 1) I want a graph after mapping, not a range and 2) I don't want to search, I want to affect all nodes.

* I'd like a way to iterate seeing only edges, not nodes.

* I'd like a way to concatenate/link different graphs (a bit like chain for ranges). I sometimes have graphs that are assembled from many different small graphs, bottom-up style. Typically, if you assemble automata (from regexes, for example), you do it bottom-up.

* Of course, I'd like a way to build a graph from nothing, putting nodes and then edges in them.

* I sometimes need to extract some global information from a graph: number of nodes, number of edges, etc.

* Does you design allow for backward iteration? (I mean, inverting the edges). Some graph algorithms ask for this kind of magic.

* Getting strongly connected components is a very interesting algorithm to have.

* you should define some template constraints on your types (Graph...), but I understand they can be added later on.


Re-reading my suggestions, I see they would push your code toward my own attempts :-) I guess I'm biased.

I have some (years old!) code in there: https://github.com/PhilippeSigaud/dranges/blob/master/graphrange.d https://github.com/PhilippeSigaud/dranges/blob/master/graph.d https://github.com/PhilippeSigaud/dranges/blob/master/graphalgorithm.d

As for my (age old) vision on graph iteration, here it is:

https://github.com/PhilippeSigaud/dranges/blob/master/recursive.d

But yet again, nothing as elegant as your own code.

On Thursday, 9 January 2014 at 22:53:02 UTC, qznc wrote:
> 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.

Unless the graph is infinite ;-)

But yes, for most graphs that would likely be more efficient than a hash lookup. I'll keep note of that. Thanks!