CODEWITHSUNDEEP
algorithmgraph
zync
zync

Reputation: 461

Detecting cycles in incremental graph

Given that I have an initially empty graph, to which will, incrementally, be added edges (one by one), what would be the best way to detect and identify appearing cycles?

Would I have to check for cycles in the entire graph every time a new edge is added? This approach doesn't take advantage of computations already made. Is there an algorithm that I still haven't found?

Thanks.

Upvotes: 3

Views: 687

Answers (2)

sten
sten

Reputation: 7476

implemented the algo that @Abhishek linked in python ..

q=QFUF(10)

In [131]: q.is_cycle([(0,1),(1,3),(2,3),(0,3)])
Out[131]: True

In [132]: q.is_cycle([0,1,4,3,1])
Out[132]: True

only cares about first two elements of the tuple

In [134]: q.is_cycle([(0,1,0.3),(1,3,0.7),(2,3,0.4),(0,3,0.2)])
Out[134]: True

here

import numpy as np

class QFUF:

    """ Detect cycles using Union-Find algorithm """

    def __init__(self, n):
        self.n = n
        self.reset()

    def reset(self): self.ids = np.arange(self.n)

    def find(self, a): return self.ids[a]

    def union(self, a, b):

        #assign cause can be updated in  the for loop
        aid = self.ids[a]
        bid = self.ids[b]

        if aid == bid : return

        for x in range(self.n) :
            if self.ids[x] == aid : self.ids[x] = bid

    #given next ~link/pair check if it forms a cycle    
    def step(self, a, b):
        # print(f'{a} => {b}')
        if self.find(a) == self.find(b) : return True
        self.union(a, b)
        return False

    def is_cycle(self, seq):
        self.reset()
        #if not seq of pairs, make them
        if not isinstance(seq[0], tuple) :
            seq = zip(seq[:-1], seq[1:]) 

        for tpl in seq :
            a,b = tpl[0], tpl[1]
            if self.step(a, b) : return True
        return False

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

You can use the Quick Union Find algorithm here to 1st check whether the two ends of the new edge are already connected.

EDIT:
As noted in the comment, this solution works only for an undirected graph. For a directed graph, following link may help https://cs.stackexchange.com/questions/7360/directed-union-find.

Upvotes: 5

Related Questions