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

"cstnt" <cstnt@hotmail.com> writes:

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:

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:
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.