时间戳

首页 > 解决方案 > 维基百科页面上的 Seidel 算法不正确吗？

python - 维基百科页面上的 Seidel 算法不正确吗？

问题描述

我正在尝试使用来自https://en.wikipedia.org/wiki/Seidel%27s_algorithm的 python 程序。

from numpy import matrix
def apd(A, n: int):
    """Compute the shortest-paths lengths."""
    if all(print(i,j)or A[i][j] for i in range(n) for j in range(n) if i != j):
        return A
    Z=A**2
    B=matrix([[1 if i != j and (A[i][j] == 1 or Z[i][j] > 0) else 0 for j in range(n)]for i in range(n)])
    T=apd(B,n)
    X = T*A
    degree = [sum(A[i][j] for j in range(n)) for i in range(n)]
    D = matrix([[2 * T[i][j] if X[i][j] >= T[i][j] * degree[j] else 2 * T[i][j] - 1 for j in range(n)]for i in range(n)])
    return D
maatriks=matrix([
         [0,0,1,0,0],
         [0,0,1,0,1],
         [1,1,0,1,1],
         [0,0,1,0,0],
         [0,1,1,0,0]])
print(apd(maatriks,5))

但我给出了错误：

Traceback (most recent call last):
  File "[PATH]/Seidel.py", line 19, in <module>
    print(apd(maatriks,5))
  File "[PATH]/Seidel.py", line 4, in apd
    if all(print(i,j)or A[i][j] for i in range(n) for j in range(n) if i != j):
  File "[PATH]/Seidel.py", line 4, in <genexpr>
    if all(print(i,j)or A[i][j] for i in range(n) for j in range(n) if i != j):
  File "/usr/local/lib/python3.8/dist-packages/numpy/matrixlib/defmatrix.py", line 193, in __getitem__
    out = N.ndarray.__getitem__(self, index)
IndexError: index 1 is out of bounds for axis 0 with size 1

是我错误地使用了程序还是程序本身不正确？ 第 9 页的此处似乎与在 python 中实现的算法完全相同。

标签： pythonnumpymatrixgraph

解决方案

这个实现对我有用。维基百科上提供的代码索引不正确。当索引一个 numpy 矩阵以获取第 i个、第j 个A[i,j]元素时，您不需要A[i][j]

from numpy import matrix


def apd(A, n: int):
    """Compute the shortest-paths lengths."""
    if all(A[i, j] for i in range(n) for j in range(n) if i != j):
        return A
    Z = A ** 2
    B = matrix(
        [
            [1 if i != j and (A[i, j] == 1 or Z[i, j] > 0) else 0 for j in range(n)]
            for i in range(n)
        ]
    )
    T = apd(B, n)
    X = T * A
    degree = [sum(A[i, j] for j in range(n)) for i in range(n)]
    D = matrix(
        [
            [
                2 * T[i, j] if X[i, j] >= T[i, j] * degree[j] else 2 * T[i, j] - 1
                for j in range(n)
            ]
            for i in range(n)
        ]
    )
    return D

a = matrix(
    [
        [0, 0, 1, 0, 0],
        [0, 0, 1, 0, 1],
        [1, 1, 0, 1, 1],
        [0, 0, 1, 0, 0],
        [0, 1, 1, 0, 0],
    ]
)
print(apd(a, 5))

返回这个。

[[0 2 1 2 2]
 [2 0 1 2 1]
 [1 1 0 1 1]
 [2 2 1 0 2]
 [2 1 1 2 0]]

这是您期望看到的回应吗？

推荐阅读