Convexity algorithm #97
Conversation
src/algorithms/convex.rs
Outdated
|
|
||
| /// A pre-computed datastructure for fast convexity checking. | ||
| /// | ||
| /// TODO: implement for graph traits? |
src/algorithms/convex.rs
Outdated
| P, // in the past | ||
| F, // in the future |
There was a problem hiding this comment.
Using the full words as variant names would make the code more readable.
src/algorithms/convex.rs
Outdated
| // A temporary datastructure used during `is_convex` | ||
| causal: Vec<Causal>, |
There was a problem hiding this comment.
Is this used to avoid allocations on each is_node_convex call? If not sure it's that necessary, specially since we'd only need to allocate max_ind - min_ind elems on each call (which hopefully is smaller than n).
Also, a bitvec would be better (or a CausalFlags wrapper to keep the nice Causal interface).
There was a problem hiding this comment.
I'd rather leave this option (because in my usecase I really expect a lot of calls to this), but I can offer a third option, which would be to pass this as an optional argument to is_convex. What do you think?
There was a problem hiding this comment.
Ahh but that would require to make Causal and CausalVec public, which I'm not too keen on.
There was a problem hiding this comment.
Makes sense. Just leave it as is, we can change it in the future.
(but check the bitvec option, Vec<bool> is quite inefficient).
There was a problem hiding this comment.
Now using bitvec 😊
src/algorithms/convex.rs
Outdated
| // The nodes in topological order | ||
| topsort_nodes: Vec<NodeIndex>, | ||
| // The index of a node in the topological order (the inverse of topsort_nodes) | ||
| topsort_ind: BTreeMap<NodeIndex, usize>, |
There was a problem hiding this comment.
The indices should be dense on a full graph toposort, so an UnmanagedMap would do better here.
|
Comments addressed! |
src/algorithms/convex.rs
Outdated
| /// Create a new ConvexChecker. | ||
| pub fn new(graph: G) -> Self { | ||
| let mut topsort_nodes = Vec::with_capacity(graph.node_count()); | ||
| while topsort_nodes.len() < graph.node_count() { |
There was a problem hiding this comment.
Can't you traverse graph.nodes_iter() once, get nodes with no inputs, and run toposort from there?
There was a problem hiding this comment.
True, sorry I'm getting tired. I mixed up two separate concerns: the only thing I needed to take care of is the case where there are inputs put they are not connected.
Co-authored-by: Agustín Borgna <[email protected]>
|
Good thing you're checking! |
This builds on top of #96, so it will be easier to review that one first!