CODEWITHSUNDEEP
pythonrecursiongraph-theory
Tamim Azmain
Tamim Azmain

Reputation: 35

Trying to find disconnected Graphs in Python

I am looking to find disconnected subgraphs in Python

Take this graph as an example: Index 0 represents node A , 1 represent B ... etc -1 is just a place holder because this is a simple graph having no edges connecting itself.

The 5 represents the weight of the edges ( will have graphs in the future with different weights )

[[-1  5  5  0  0]
 [ 5 -1  0  0  0]
 [ 5  0 -1  0  5]
 [ 0  0  0 -1  0]
 [ 0  0  5  0 -1]]

To look for disconnected graphs, I first created a True / False on if I have visited the edge or not. ( 0 and -1 are as default, True) which looks like this:

[[ True False False  True  True]
 [False  True  True  True  True]
 [False  True  True  True False]
 [ True  True  True  True  True]
 [ True  True False  True  True]]

My approach to this problem is to start at any edge with a false value and start at the node represented by the rows, and go through all the possible edges connecting that node and its children's node, and so on. As I traverse along those vertices, I will mark the Boolean Matrix True as I have "visited" that edge. Once I know that I have "visited" all the edges, I know that I will have a connected subgraph. Then I will look for another "False" in my True/False matrix and start from there looking for another disconnected graph, and continue until I fill in all the elements as True.

However, I am stuck on traversing through the edges

Here is my algorithm:

reducedMatrix = np.load(reducedweightmatrix)
print(reducedMatrix)
boolarray = (reducedMatrix == 0) | (reducedMatrix == -1)
print(boolarray)


def traverse(iy,visited_nodes,looped):
    #Only move to next index if there is no loop
    # already visited node?
    print("I am currently at: "+ str(iy))
    print(visited_nodes)
    print(looped)
    print("-----------------\n")
    if (iy in visited_nodes):
        looped = True
    if(not looped):
        print("I enterred the loop")
        children = []
        #Find connected "children" vertices
        for ix,weight in enumerate(reducedMatrix[iy]):
            if weight != 0 and weight != -1:
                #Collect the index with connected vertices
                children.append(ix)
                #I AM GOING TO VISIT  THESE VERTICES
                boolarray[iy,ix] = True

        print(children)
        visited_nodes.append(iy) 
        for child,children in enumerate(children):
            print(child)
            traverse(child,visited_nodes,looped)
    return visited_nodes

print(traverse(0,[],False))

Using the example shown above, here are the log messages:

[[-1  5  5  0  0]
 [ 5 -1  0  0  0]
 [ 5  0 -1  0  5]
 [ 0  0  0 -1  0]
 [ 0  0  5  0 -1]]
[[ True False False  True  True]
 [False  True  True  True  True]
 [False  True  True  True False]
 [ True  True  True  True  True]
 [ True  True False  True  True]]
I am currently at: 0
[]
False
-----------------

False
I enterred the loop
[1, 2]
0
I am currently at: 0
[0]
False
-----------------

True
1
I am currently at: 1
[0]
False
-----------------

False
I enterred the loop
[0]
0
I am currently at: 0
[0, 1]
False
-----------------

True
[0, 1]

According to the example above, the algorithm should be showing the following: [0,1,2,4] Please point out to me where I went wrong with the recursion

Upvotes: 3

Views: 1282

Answers (1)

MaxPlankton
MaxPlankton

Reputation: 1258

I don't quite understand this piece of code,

for child,children in enumerate(children):
    print(child)
    traverse(child,visited_nodes,looped)

Just change it to,

for child in children:
    print(child)
    traverse(child,visited_nodes,looped)

The answer is right over there.

What you want is to visit every child in the children, not the index of children. What you saved in children previously is the index number. You definite do not want to find the index of index number.

Edit: If you are iterating over an iterable, please don't name your value the same as the iterable itself. Guess what happens below?

children = list(range(10))  
for child,children in enumerate(children):
    pass
print(children)

Upvotes: 1

Related Questions