mitchmindtree/daggy

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 or b without prior edges?
  • is there already an edge from a to b 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

🎉