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!

Reply via email to