Range-Based Graph Search in D (blog post)

[Peter Alexander]

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!