1

我无法弄清楚为什么我的 Reverse Cuthill–McKee 算法的实现会返回错误的位置。基本上，它会产生正确的结果，但是当我运行代码时，它会返回一个不同的值。

这是带有图表的完整代码，有人可以解释一下这种行为吗？

import numpy as np

A=np.diag(np.ones(8))

nzc=[[4],[2,5,7],[1,4],[6],[0,2],[1,7],[3],[1,5]]

for i in range(len(nzc)):
    for j in nzc[i]:
        A[i,j]=1

# define the Result queue
R = ["C"]*A.shape[0]


def getDegree(Graph):
    """
    find the degree of each node. That is the number
    of neighbours or connections.
    (number of non-zero elements) in each row minus 1.
    Graph is a Cubic Matrix.
    """
    degree = [0]*Graph.shape[0]
    for row in range(Graph.shape[0]):
        degree[row] = len(np.flatnonzero(Graph[row]))-1
    return degree

# find the starting point, the parent
degree = getDegree(A)

adj = getAdjcncy(A)
degree2=degree[::]
adj2 = adj[::]
digar=np.array(degree2)
pivots = list(np.where(digar == digar.min())[0])

def main_loop2(deg,start, adj,R):
    degcp=deg[:]
    digar=np.array(deg)
    # use np.where here to get indecies of minimums
    if start not in R:
        R.append(start)
        degcp.pop(start)
        if start in pivots:
           pivots.pop(start)
           print "p: ", pivots
    Q=adj[start]
    for idx, item in enumerate(Q):
        if item not in R:
            R.append(item)
            print "R", R
    print "starts", adj[R[-1]]
    Q=adj[R[-1]]
    if set(Q).issubset(set(R)) and len(R) < len(degcp) :
         print "will now look for new pivot"
         p = pivots[0]
         pivots.pop(0)
         print "pivots", pivots
         print "starting with" , p
         main_loop2(deg,p,adj,R)
         return 'this is never reached'
    elif len(R) < len(degcp):
         main_loop2(deg,R[-1],adj,R)
         return 'wrong'
    else:
         print "will return R"
         print type(R)
         return R      

inl=[]
Res = main_loop2(degree2,0, adj,inl)

print(Res)

输出：

Degrees: [1, 3, 2, 1, 2, 2, 1, 2]
0
p:  [3, 6]
R [0, 4]
starts [0, 2]
R  2 degcp 7
R [0, 4, 2]
starts [1, 4]
R  3 degcp 8
R [0, 4, 2, 1]
starts [2, 5, 7]
R  4 degcp 8
R [0, 4, 2, 1, 5]
R [0, 4, 2, 1, 5, 7]
starts [1, 5]
will now look for new pivot
pivots [6]
starting with 3
R [0, 4, 2, 1, 5, 7, 3, 6]
starts [3]
will return R
<type 'list'>
wrong

所以问题是：
为什么函数在递归的所有循环中都能正常工作，但在最后一个循环中，它返回值wrong？输出显示 lastelse只到达了一次，但是没有返回一个列表，我在这里很无奈。如果有人对此有所了解，我将不胜感激。

更新：

我发现了另一个关于 python 和递归的问题，当我在那里应用解决方案时，我的代码有效！

所以，而不是main_loop2(deg,R[-1],adj,R)我写 的每一个retrun main_loop2(deg,R[-1],adj,R)，现在的输出是：

... snip ...
R [0, 4, 2, 1, 5, 7]
starts [1, 5]
will now look for new pivot
pivots [6]
starting with 3
R [0, 4, 2, 1, 5, 7, 3, 6]
starts [3]
will return R
<type 'list'>
[0, 4, 2, 1, 5, 7, 3, 6]
4

1 回答 1

3

递归调用的顶层进入这里：

elif len(R) < len(degcp):
     main_loop2(deg,R[-1],adj,R)
     return 'wrong'

递归调用内部发生的任何事情main_loop2都无关紧要。当它回来时，它将执行该return 'wrong'语句。您需要实际返回最内层调用产生的值，一直返回到顶层 - 这不会神奇地发生在您身上。

你是故意的return main_loop2(...)吗？

于 2012-11-08T05:15:49.420 回答