search

declanvk / incremental-topo

Data structure to maintain an incremental topological ordering over a collection of values
Apache License 2.0
16 stars 2 forks source link

Considering `incremental-topo` #31

Open cloudhead opened 1 year ago

cloudhead commented 1 year ago

Hey there, I'm working on a CRDT which uses Git DAGs to store events. I'm currently using petgraph but it doesn't allow me to have control over the order of iteration of neighbors, eg. in a partial ordering.

I'm considering this library, though for now it looks like there is the same limitation, ie. the library doesn't expose the fact that there may be more than one possible topological ordering per graph.

Is this something that could be exposed somehow? When doing an iter_unsorted, the topological ranking is different for nodes that should have the same ranking, which I'm not sure is by design or not. Eg. in the graph:

b    c
 \  /
  a

b and c should have the same ranking, since two orderings exist: [a, b, c] and [a, c, b]. It would be nice to expose that, or to allow for iteration in both of those orderings.

declanvk commented 1 year ago

the topological ranking is different for nodes that should have the same ranking

I think you're referring to the usize rankings returned by the DescendantsUnsorted iterator, unfortunately those values aren't very useful outside of the implementation (I should really remove them from the API and topo_cmp).

I don't think the incremental topo ordering algorithm support labeling nodes that could be considered equal. However,

It would be nice to [...] allow for iteration in both of those orderings.

I think it would be possible to enumerate through all topological orderings of the graph using something like the algorithm described in https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/.

Internally, the graph maintains sets of successor/predecessor edge relationships so traversing shouldn't be too difficult.

Is that something you would be interested in? I could add another iterator that returns all the possible orderings of nodes in the graph.

cloudhead commented 1 year ago

Yeah, so for now I decided to implement a simple Dag that shuffles the order of the keys through which it iterates during a topological sort. It seems to do the trick, though having a function to go through all permutations would be nicer for testing for sure. I think I'll stick to this simple implementation in the short term, though I bet it won't perform too well for large graphs, so will be keeping an eye on that, and on incremental-topo.

This is what I ended up with: https://github.com/radicle-dev/heartwood/blob/master/radicle-dag/src/lib.rs anyway.