Printing all the cycles in an adjacency matrix using python

Question

In the below code, while trying to print all cycles, there comes the case where multiple cycles exist for one node. Even though I am increasing the value of k in the cycle function, it doesn't print all the possible cycles for a given node i.e. it doesn't consider the two possible cycles for node 3 or index 2 to index 1 as well as index 3 of the node 1 or index 0. Here we discuss the following graph, represented as mat in the code. Example Image

output the code prints:

['1 -> 2', '2 -> 3', '3 -> 1']

['1 -> 4', '4 -> 5', '5 -> 1']

['2 -> 3', '3 -> 1', '1 -> 2']

['3 -> 1', '1 -> 2', '2 -> 3']

Where the code fails is on the path [ [3 -> 1 ] , [1 -> 4] , [4-> 5] , [5-> 1] , [1 -> 2] , [2-> 3]]. With this code, I aim to print all cycles for a given adjacency matrix, even considering the case where no cycles exist.

I expect the output for the given an example as:

['1 -> 2', '2 -> 3', '3 -> 1']

['1 -> 4', '4 -> 5', '5 -> 1']

['2 -> 3', '3 -> 1', '1 -> 2']

['3 -> 1', '1 -> 2', '2 -> 3']

['2 -> 3', '3 -> 1', '1 -> 4', '4 -> 5', '5 -> 1', '1 -> 2']

['3 -> 1', '1 -> 4', '4 -> 5', '5 -> 1', '1 -> 2', '2 -> 3']

['4 -> 5', '5 -> 1', '1 -> 2', '2 -> 3', '3 -> 1', '1 -> 4']

['5 -> 1', '1 -> 2', '2 -> 3', '3 -> 1', '1 -> 4', '4 -> 5']

Code Sample:

mat = [[0,1,0,1,0] , [0,0,1,0,0] , [1,0,0,0,0] , [0,0,0,0,1] , [1,0,0,0,0]]

def cycle(mat,i,j,find):  
    global temp,t
    k = 0
    while k != len(mat): 
        if k != j and mat[j][k] and (temp == [] or temp[-1][-1] == str(j+1)):
            temp.append(f'{j+1} -> {k+1}')
            if k == find:
                print(temp)
                return 1
            else:
                t.append([i,j,k,find])
                if t.count([i,j,k,find]) > 1:
                    return -1
                cycle(mat,j,k,find)      
        k = k+1
        
                
for i in range(len(mat)):
    for j in range(len(mat)):
        if mat[i][j] and i != j:
            temp = []
            t = []
            temp.append(f'{i+1} -> {j+1}')
            cycle(mat,i,j,i)

Logic:

We are trying to go from : i -> j to : j -> k (where i , j , k are nodes) using cycle function. I've used

(temp == [] or temp[-1][-1] == str(j+1))

to make sure that after i -> j , only j -> k gets appended

                t.append([i,j,k,find])
                if t.count([i,j,k,find]) > 1:
                    return -1

conditions to prevent it from going into infinite recursion. For Detailed Logic click.

Thank you for your time and for helping me with my first StackOverflow question.

ravenspoint · Accepted Answer · 2023-03-10 02:05:24Z

1

You say you expect [ [3 -> 1 ] , [1 -> 4] , [4-> 5] , [5-> 1] , [1 -> 2] , [2-> 3]] but this is just a combination of two cycles which ARE printed out. [1 -> 4] , [4-> 5] , [5-> 1] and [3->1] , [1 -> 2] , [2-> 3].

It seems unreasonable to me to expect two cycles that just happen to share a node to be output as a combination. If you really do want to see this, then take the output of uncombined cycles, check them for shared nodes and print out the combined cycles as they are found.

FIND simple cycles ( using your code )
LOOP over pairs of simple cycles
   IF pair share nodes
       PRINT combined cycle

edited Mar 10, 2023 at 2:05

answered Mar 9, 2023 at 15:23

ravenspoint

21.2k7 gold badges64 silver badges114 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Dhruvil09 Over a year ago

The detailed logic is : docs.google.com/document/d/…

Dhruvil09 Over a year ago

Did you get an intuition of how the code works ?

Dhruvil09 Over a year ago

I deleted all the meaningless comments.

ravenspoint Over a year ago

Do you mean your code? Your code works fine. It finds the simple cycles. If you want to see the combined cycles, then my answer describes how to do so.

Dhruvil09 Over a year ago

My code will never print uncombined cycles because assuming there is a cycle from node '3' it will only print paths that start from '3' and end at '3', No question of uncombined cycles.

|

Collectives™ on Stack Overflow

Printing all the cycles in an adjacency matrix using python

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related