On Friday, 10 January 2014 at 18:26:15 UTC, Joseph Rushton Wakeling wrote:
> 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. :-)

I'm currently only in the exploratory phase, trying to iron out a simple but flexible API. Hard to say if there is or will be any overlap at this time. However, assuming both our designs are as generic as they hope to be, they should all be interoperable (perhaps with a bit of adaptation/forwarding)!

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.

On Saturday, 11 January 2014 at 09:11:45 UTC, Philippe Sigaud wrote:
> * 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`.

Yes, I think this should be possible. I think I will allow arbitrary edge types so the user can attach whatever information they like, and then these can be retrieved through an edge event visitation of the graph.

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

Interesting. I think that should be possible if you provide some sort of adaptor on the graph that modifies the result of the "adjacent" function.


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

Yes, I think I will change the search range to be a range of events, which will include edges taken and vertices visited among other things. You can then filter the events to only see edge events if you wish.


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

Should be possible, but I think that would be up to the user to do the combination. They just need to provide the correct API.


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

Yep, I'll add some real graph data structures later :-)  I understand implicit graphs aren't everything!


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

Any graph that can provide that would be free to do so.


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

True. Implicit graph would struggle to provide that, but other graphs would be able to provide "incidentEdges" as part of the API (easy for adjacency matrix for example).


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

Absolutely, I'll likely move onto connected components and graph flow next.


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

Yeah, it's not very robust at the moment, just experimental :-)   I find adding constraints early just gets in the way of experimentation.


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

Thank you for the feedback. I will have a look at your code for inspiration!

On Saturday, 11 January 2014 at 09:51:57 UTC, Peter Alexander wrote:
> 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!

I love the design, only some few minor tweaks needed(as already highlighted in this thread).

Even without any changes, it fits my current needs and I'd like to use it already, am I right in assuming that it's Boost licensed?