英文:
Printing all the cycles in an adjacency matrix using python
问题
在以下代码中，尝试打印所有循环时，存在一种情况，即一个节点存在多个循环。尽管我在循环函数中增加了k的值，但它并不打印给定节点的所有可能循环，即它不考虑节点3或索引2到索引1以及节点1或索引0的两种可能循环。这里我们讨论以下图形，表示为代码中的mat。示例图像
代码输出如下：
['1 -> 2', '2 -> 3', '3 -> 1']
['1 -> 4', '4 -> 5', '5 -> 1']
['2 -> 3', '3 -> 1', '1 -> 2']
['3 -> 1', '1 -> 2', '2 -> 3']
代码失败的地方是路径[[3 -> 1], [1 -> 4], [4-> 5], [5-> 1], [1 -> 2], [2-> 3]]。通过这段代码，我希望打印给定邻接矩阵的所有循环，甚至考虑不存在循环的情况。
对于给定示例，我期望输出如下：
['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']
代码示例：
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)
逻辑：
我们试图从：i -> j 到：j -> k（其中i，j，k是节点），使用cycle函数。我使用了
(temp == [] or temp[-1][-1] == str(j+1))
来确保在i -> j之后，只会附加j -> k
t.append([i,j,k,find])
if t.count([i,j,k,find]) > 1:
return -1
条件以防止它进入无限递归。详细逻辑点击。
感谢您的时间和帮助我解决我的第一个StackOverflow问题。
英文:
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.
答案1
得分: 1
你说你期望得到 [[3 -> 1], [1 -> 4], [4 -> 5], [5 -> 1], [1 -> 2], [2 -> 3]]，但这只是两个循环的组合，这两个循环已经被打印出来了：[1 -> 4], [4 -> 5], [5 -> 1] 和 [3 -> 1], [1 -> 2], [2 -> 3]。
我觉得期望两个只是碰巧共享一个节点的循环被输出为一个组合是不合理的。如果你真的想看到这个，那么可以获取未组合的循环的输出，检查它们是否有共享的节点，然后按照它们被找到的顺序打印出组合的循环。
查找简单循环（使用你的代码）
循环遍历简单循环的配对
如果配对共享节点
打印组合的循环
英文:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论