Re: Dynamic cycle Detection

On Wednesday 18 April 2007 11:17, aimal.rextin@xxxxxxxxx wrote:
I add edges to a DAG G one by one.
After each addition I need to check if the addition made the digraph
cyclic. I can check this by running DFS, but I want to do it more
efficiently by using the information already available.

If every node has a list of its ancestors, a check would be quick.
Specifically, if an edge goes from a node to an ancestor of that node,
it would create a loop. Otherwise, it doesn't create a loop.

Space requirement is O(n^2), where n is the number of nodes. Time to
check can be constant.


In the special case that the DAG has many pieces, there may be a short
cut. A "piece" is a "connected" subgraph (I can't think of a
succinct, precise definition now. If this informality upsets you,
please stop reading here.) Number each piece, that is, give the piece
number to all nodes in that piece. If your edge goes from (a node in)
one piece to (a node in) a different piece, it doesn't create a loop.
If the edge is within a piece, it might create a loop

-paul-
--
Paul E. Black (p.black@xxxxxxx)
.