program of Recursion for Maximum Independent Set in a Graph

I am getting difficulty in writing a program for the above mentioned problem.. I have the following graph....

A-----B------C       D
A is connected to B
B is connected to C
D is connected with no body!! 
The maximum Independent set in this is {A,C, D}... 

The Adjacency Matrix for the graph is below:-

I drew the following decision tree inorder to solve the problem:-

• The first element of each node is the index.

• The second element of each node is the set which store independent elements of the graph.

• The left branch says that i will not consider the element, and the right branch says that I will consider the element at index specified by first element of the node.

So as you can see clearly, at each node, I haven't considered the element specified by first element index of the node, and I have consider the element whether it can be inserted in the independent set.

I want to write up a program for this in Python!! I am a newbie, and just still in early stages of implementing the program through recursion.

kindly help!!

I wrote the following code:- but it doesn't looks nice to me.. Its working somehow.. Please experiences People could put in your comments.. I am still learning in recursion..

def maxset(tab, i, set):
    global numcalls
    numcalls += 1
    if i == 0:
        flag = 0
        for s in set:
            if tab[i][s]:
                return 0
        if i not in set:
            set.append(i)
        return len(set)

    without_i = maxset(tab, i-1, set)

    flag = 0
    for s in set:
        if tab[i][s]:
            return withou开发者_JS百科t_i
    if i not in set:
        set.append(i)
    with_i = maxset(tab,i-1,set)
    return max(without_i, with_i)


tab = [[0,1,0,0],[1,0,1,0],[0,1,0,0],[0,0,0,0]]
#tab = [[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]
set = []
numVertIndex = 3 #### 0,1,2,3
numcalls = 0
print(maxset(tab, numVertIndex, set))
print(set)
print (numcalls)

There is a well known and simple algorithm to solve this problem:

1. Initially color all your vertices green.
2. Find a green vertex. Color it's neighbors red.
3. For every red vertex, color it's green neighbors red. (Here's the recursion part)
4. When there are no more red vertices with green neighbors, the set of red vertices determines a maximally connected component.
5. Repeat from 2 until all vertices are red and all components are discovered.

Now that you know all the components, you can choose the one with the most vertices (i.e. the highest order maximally connected sub-graph).

As for your code:

1. It has one critical error: set is never copied. Usually it is ok, but this is not the case. Let's see your code. After computing of without_i the original set value could be modified. In this case computing of with_i uses incorrect set value. The simplest example of the case I could imagine is tab = [[0,1,0],[1,0,0],[1,0,0]].

2. Minor errors: flag is unused? Also numcalls seems to be created to simplify debugging. So I exclude it in my code example.

3. It seems to me that interface of your function is not convenient. User has to create his own set variable and manually specify problem size. So in my code example I wrapped the original function into the one with interface I would like to use. Actually you can go further and explore the ways of adjacency declaration. For example, adjacency lists could be more convenient than matrices.

My code example:

def maxset( tab ):
    def maxset_detail(tab, i, set):
        if any( tab[i][s] for s in set ):
            return i and maxset_detail(tab, i-1, set) or 0
        if (i == 0):
            set.append(i)
            return len(set)
        set_copy = set[:] + [i]
        without_i = maxset_detail(tab, i-1, set)
        with_i = maxset_detail(tab, i-1, set_copy)
        if ( with_i > without_i ):
            set[:] = set_copy
            return with_i
        else:
            return without_i
    set = []
    maxset_detail(tab, len(tab)-1, set )
    return set