Ask Your Question
0

FFloyd-Warshall doesn't works

asked 2021-03-12 10:46:11 +0100

Cyrille gravatar image

In https://stackoverflow.com/questions/55518900/seeking-pseudo-code-for-calculating-the-smith-and-schwartz-set I have found the following application of Ffloyd-Warshall algorithm :

`I guess python is close enough to pseudocode.

Let's say we have n candidates numbered from 0 to n - 1.

First you can compute a matrix beats[i][j] equal to True if candidate i beats candidate j and False otherwise.

Now compute the transitive closure of the matrix using the Floyd-Warshall algorithm:

for k in range(n):

for i in range(n):

    for j in range(n):

        beats[i][j] = beats[i][j] or (beats[i][k] and beats[k][j])`

There is my code for n=3

B =[["False","True","True","False"],["False","False","True","True"],["False","False","False","False"],["True","False","True","False"]]
def floydWarshall1(graph,n=3): #n=no. of vertex
    beats=graph
    [[["True"  if (beats[i][j]=="True" or (beats[i][k] and beats[k][j])=="True") else "False" for j in range(n)] for i in range(n)]for k in range(n)]
    return beats  
fw=floydWarshall1(B,3)
show(B)
show(fw)

I wonder why B and fw are the sames since

show(B[0][3])
show(B[0][1] and B[1][3])

returns False for the first and True for the second. Certainly an error of mine.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2021-03-12 15:28:18 +0100

Emmanuel Charpentier gravatar image

This :

def FW(B): return [[bool(v) for v in u] for u in matrix(B)+(matrix(B).transpose()*matrix(B))]
B =[[False,True,True,False],[False,False,True,True],[False,False,False,False],[True,False,True,False]]
fw=FW(B)
print(matrix(B))
print("-"*9)
print(matrix(fw))

should do...

edit flag offensive delete link more

Comments

I have tried the proposed solution but if I understand the process, there is a strange line.

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

If 1 there is a path from i to j . But there is no path from 2 to 2 so fw[2][2] should be 0 not 1

Cyrille gravatar imageCyrille ( 2021-03-13 18:29:57 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-03-12 10:46:11 +0100

Seen: 466 times

Last updated: Mar 12 '21