Dynamic cycle Detection
in [Theory]
|
From: aimal.rextin on 18 Apr 2007 11:17 Hello Everyone, I am working on a problem in which 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. Does anyone have any idea on how it can be done efficiently? Thanks Aimal
From: Paul E. Black on 18 Apr 2007 12:30 On Wednesday 18 April 2007 11:17, aimal.rextin(a)gmail.com 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(a)acm.org)
From: busygin on 18 Apr 2007 12:50 One obvious thing: if you keep topologocal sorting of your graph and your new arc goes upwards in it, you don't create a cycle for sure. Next step of the same idea: rank the vertices such that a) vertices with no incoming arcs have rank 0; b) vertices of rank k have incoming arcs only from vertices of ranks 0..k-1. Then, again, if your new arc is not from a higher rank to a lower rank, there will be no cycle. Of course, if the new arc goes downwards in your sorting/ranking, there may be a cycle. You need to update it, and if it's not possible, you do have a cycle. Keeping the entire transitive closure doesn't seem to be a good idea as it's update is more expensive than the marking algortihm to find a cycle. --Stas http://www.busygin.dp.ua On Apr 18, 11:17 am, aimal.rex...(a)gmail.com wrote: > Hello Everyone, > I am working on a problem in which 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. > Does anyone have any idea on how it can be done efficiently? > Thanks > Aimal
From: David Wagner on 18 Apr 2007 17:59 >I am working on a problem in which I add edges to a DAG G one by one. >After each addition I need to check if the addition made the digraph >cyclic. Keywords: "online cycle detection", "dynamic cycle detection". There is literature on this subject; do a literature search, and you'll find prior work. (See, e.g., Schmueli, 1983.) Also, here is a paper that uses online cycle detection and elimination in an application, and discusses a heuristic technique that seems to work well in that application: http://theory.stanford.edu/~aiken/publications/papers/pldi98b.ps
From: aimal.rextin on 20 Apr 2007 07:26 Thanks alot everyone... I think your suggestions were really useful.
|
Pages: 1 Prev: Multidimensional binary search trees Next: Fibonacci heap and Dijkstra's algorithm |