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

"cstnt" <cstnt@hotmail.com> 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.

cstnt wrote:

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

I will assume that the graph is undirected, otherwise the following 
won't work:

Give each connected group in the graph a distinct name, and label each 
node with the name of its group.  When you add an edge then:
(a) If the edge is between two nodes with the same label, you are 
creating a cycle or cycles.
(b) If the edge is between two nodes with different labels, you are not 
creating a cycle, and you should re-label the nodes of one group to 
match the other group, as the two groups have merged.

I think that if you create a tree from a cloud of n disconnected nodes 
by add random non-cycle-inducing links, and you always re-name the 
smaller group in case (b), you will need O(n log n) individual 
re-labelling operations, though I am not sure how to prove it.

-- 
Simon Richard Clarkstone:
s.r.cl?rkst?n?@durham.ac.uk/s?m?n.cl?rkst?n?@hotmail.com
Scheme guy says:   (> Scheme Haskell)
Haskell guy says:  (> Scheme) Haskell

On Apr 26, 4:34 am, "cstnt" <c...@hotmail.com> wrote:
> How to judge if the graph is cyclic when add a new edge? How to do it
> quickly.

Assuming your graph is undirected, the standard approach
is to use the "union-find" (a.k.a. "disjoint-sets") data structure.
The time per edge insetion / will edge add a cycle is
essentially constant.