Re: Dynamic cycle Detection

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...@xxxxxxxxx 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


.

Relevant Pages

  • Re: Where are the BEST Point and Shoot Photos ?
    ... figures of 30 seconds of arc in good conditions, ... as the minimum separation between black lines on ... That's one full cycle of the test pattern. ... pixels it takes to create one black/white cycle. ...
    (rec.photo.digital)
  • Re: Where are the BEST Point and Shoot Photos ?
    ... figures of 30 seconds of arc in good conditions, ... That's one full cycle of the test pattern. ... pixels it takes to create one black/white cycle. ... The 2.5-3 pixels/cycle comes from looking at resolution charts from ...
    (rec.photo.digital)
  • computing in pgf tikz
    ... I need to a draw a picture of a cycle with 6 arcs. ...
    (comp.text.tex)