Is Seidel's algorithm on wikipedia page incorrect?

user_2952903 0
Viewed 137

I am trying to use the python program from https://en.wikipedia.org/wiki/Seidel%27s_algorithm .

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))

But I gives error:

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

Am I using the program wrongly or is the program itself incorrect? Here on page 9 seems to be the exactly same algorithm as is implemented in python.

graph matrix numpy python
1 Answers

This implementation worked for me. The code provided on wikipedia has the indexing incorrect. when indexing a numpy matrix to get the i'th , j'th element you need to do A[i,j] not 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))

Returns this.

[[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]]

Is this the response you expect to see?

user_87551020
Related