Re: How to judge if the graph is cyclic when add a new edge?

"cstnt" <cstnt@xxxxxxxxxxx> writes:

How to judge if the graph is cyclic when add a new edge? How to do it
quickly.

For a directed graph, you can do it quickly if you keep in parallel
the transitive closure.


Given a graph like: a->b;b->c, you keep a second graph: a->b;b->c;a->c
Then when you add an edge, you just need to check if there is already
an edge in the other direction: If you try to add a->c, it's ok
because c->a doesn't exist in the transitive closure. If you try to
add c->a, or b->a or c->b, you know immediately that it would make a
cycle for the resersed edges are in the transitive closure.


Well, on the other hand, adding the transitive closure will probably
be in O(|edges|)...

--
__Pascal Bourguignon__ http://www.informatimago.com/

ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.
.