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!
