COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

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

• Follow

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

```
 0

```"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.
```
 0

```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
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)
```
 0

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

```
 0

3 Replies
320 Views

Similiar Articles:

7/23/2012 9:43:30 PM