CODEWITHSUNDEEP
algorithmgraph-algorithm
Sergey Sosnin
Sergey Sosnin

Reputation: 1413

An algorithm to get all connected subgraphs from graph, is it correct?

I try to find an quick algorithm to obtain all connected subgraphs form an undirected graph with subgraphs length restricted. Simple methods, such as BFS or DFS from every vertex generate huge amount of equals subgraphs, so in every algorithm iteration we have to prune subgraphs set. I have found in russian mathematical forum an algorithm: 

Procedure F(X,Y)
//X set of included vertices 
//Y set of forbidden vertices to construct new subgraph
1.if |X|=k, then return;
2.construct a set T[X] of vertices that adjacent to vertices from X (If X is a empty set, than T[X]=V), but not belong to the sets X,Y;
3.Y1=Y;
4.Foreach v from T[X] do:
__4.1.X1=X+v;
__4.2.show subgraph X1;
__4.3.F(X1,Y1);
__4.4.Y1=Y1+v;

Initial call F(X,Y):
X, Y = empty set;
F(X,Y);

The main idea of this algorithm is using "forbidden set" so that, this one doesn't require pruning, author of this algorithm said that it is 300 times more quickly than solution based on pruning equals subgraphs. But I haven't found any proofs that this algorithm is correct at all.

UPDATE: More efficient solution was found here

Upvotes: 2

Views: 2007

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Here is an Python implementation of what I believe to be your original algorithm:

from collections import defaultdict

D=defaultdict(list)
def addedge(a,b):
    D[a].append(b)
    D[b].append(a)

addedge(1,2)
addedge(2,3)
addedge(3,4)

V=D.keys()
k=2

def F(X,Y):
    if len(X)==k:
        return
    if X:
        T = set(a for x in X for a in D[x] if a not in Y and a not in X)
    else:
        T = V
    Y1=set(Y)
    for v in T:
        X.add(v)
        print X
        F(X,Y1)
        X.remove(v)
        Y1.add(v)

print 'original method'
F(set(),set())

F generates all connected subgraphs of size <=k where the subgraph must include vertices in X (a connected subgraph itself), and must not include vertices in Y.

We know that to include another vertex in the subgraph we must use a connected vertex so we can recurse based on the identity of the first connected vertex v that is inside the final subgraph. The forbidden set means that we ensure that a second copy of subgraph cannot be generated as this copy would have to use v, but v is in the forbidden set so cannot be used again.

So at this superficial level of analysis, this algorithm appears efficient and correct.

Upvotes: 2

trungdinhtrong
trungdinhtrong

Reputation: 2674

You did not describe the algorithm well. We dont know that k is or what V is in this algorithm. I just assume k is the restricted length on the sub-graph and V is some root vertex.

If that is true than it looks to me that this algorithm is incorrect. Suppose we have a graph with only two connected vertices v1, v2 and the restricted on the sub graph k = 1.

In the first iteration: X, Y = empty, T(X) = {v1}, X1 = {V1}, Y1 = empty we show X1.

  • Then we recursively call F(X1, Y1), and it should return immediately because |X| = |{v1}| = 1

Back to the 1st iteration now Y(1) = v1. The loop ends and the initial call also ends here. So we are printing out only X1. We suppose to print out X1, X2.

By the way do not "test" an algorithm - there is no way to test it (the number of possible test case is infinite). You should indeed formally prove it.

Upvotes: 0

Related Questions