declanvk/incremental-topo

Data structure to maintain an incremental topological ordering over a collection of values

incremental-topo's Issues

Make the dag example show genericity

To be truly usable in a wide range of situation, it needs to be generic, show the world that it is !

Delete travis config and replace with Github Actions

This repository does not have any automated tests running on PRs at the moment, need to implement something before merging anything new.

Reconsider API design

Some rambling ideas:

In the changes from v0.1.2 to v0.2.0, the signature of the IncrementalTopo type changed from IncrementalTopo<T> to IncrementalTopo, losing the ability to store user-defined types. This was largely because I didn't want to have the bi-map component anymore, and thought that it would be better for performance just to hand out tokens which represented nodes in the graph.

The performance was a bit better, but made using the library more difficult. The expression evaluator example was the main usage test for the library. The changes to the example to work with the v0.2.0 made me realize that maybe having some user-defined type stored in the IncrementalTopo object might be useful.

Previously, the type T in the IncrementalTopo<T> signature represented the node type. When creating a new node, the user would specify a value of type T which uniquely represented the node. Then, the other APIs had the form:

pub fn method_using_single_node<Q>(&self, node: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + Eq + ?Sized;

This gave users the flexibility to have a IncrementalTopo<String>, then using &str form to query it.

Instead of reverting to this, what if I made a new API that allowed store abitrary T values, but returned a opaque node token (like the incremental_topo::Index value today). Other APIs would still take the token to query and mutate dependency information. The query and iterator APIs could return references to T or &T or &mut T depending.

I think this would simplify the expr_evaluator example specifically because it could remove the bindings and values maps from

incremental-topo/examples/expr_evaluator.rs

Lines 115 to 120 in 90dd2a2

	#[derive(Debug, Clone, Default)]
	struct Assignments {
	bindings: HashMap<Symbol, Rc<Expr>>,
	ordering: IncrementalTopo,
	values: HashMap<Symbol, Value>,
	}

.

Mutable access in bimap component

Mutable access in maps is an issue because of the use of hashes to maintain lookup location. In a normal HashMap, this is resolved because mutable access is only allowed to the value, never the key. Because the value is never hashed, changing its internals is fine.

The issue with the BiMap is that it supports mutable access but will have its hashes invalidated as soon as either a right or left value is changed internally. To fix this we can either forbid mutable access, or we can add a wrapper guard that will update the map when the mutable access is dropped.

In the meantime, removing the public access to all mutable access and iterators is the best method. The methods can be tagged with #[allow(dead_code)], which will be removed with the fix.

Considering `incremental-topo`

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.