Use heuristic for quick accept without cycle check in `add_edge`
Closed this issue · 2 comments
bluss commented
The type invariant that the current DAG is acyclic can be used to speed up incremental checks. A full algorithm is still O(|V| + |E|) though.
Some easy heuristics are:
- is either
a
orb
without prior edges? - is there already an edge from
a
tob
with the same directionality?
bluss commented
I saw add_child which says
/// This is faster than using `add_node` and `add_edge`. This is because we don't have to check
/// if the graph would cycle when adding an edge to the new node, as we know it it will be the
/// only edge connected to that node.
but that a node has no edges is something we can very easily check in add_edge too.
bluss commented
🎉