ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 13 Mar 2021 18:29:57 +0100FFloyd-Warshall doesn't workshttps://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/ 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.Fri, 12 Mar 2021 10:46:11 +0100https://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/Answer by Emmanuel Charpentier for <p>In <code>https://stackoverflow.com/questions/55518900/seeking-pseudo-code-for-calculating-the-smith-and-schwartz-set</code> I have found the following application of Ffloyd-Warshall algorithm :</p>
<p>`I guess python is close enough to pseudocode.</p>
<p>Let's say we have n candidates numbered from 0 to n - 1.</p>
<p>First you can compute a matrix beats[i][j] equal to True if candidate i beats candidate j and False otherwise.</p>
<p>Now compute the transitive closure of the matrix using the Floyd-Warshall algorithm:</p>
<p>for k in range(n):</p>
<pre><code>for i in range(n):
for j in range(n):
beats[i][j] = beats[i][j] or (beats[i][k] and beats[k][j])`
</code></pre>
<p>There is my code for <code>n=3</code></p>
<pre><code>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)
</code></pre>
<p>I wonder why <code>B</code> and <code>fw</code> are the sames since </p>
<pre><code>show(B[0][3])
show(B[0][1] and B[1][3])
</code></pre>
<p>returns <code>False</code> for the first and <code>True</code> for the second. Certainly an error of mine.</p>
https://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/?answer=56141#post-id-56141This :
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...Fri, 12 Mar 2021 15:28:18 +0100https://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/?answer=56141#post-id-56141Comment by Cyrille for <p>This :</p>
<pre><code>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))
</code></pre>
<p>should do...</p>
https://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/?comment=56162#post-id-56162I 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 1Sat, 13 Mar 2021 18:29:57 +0100https://ask.sagemath.org/question/56128/ffloyd-warshall-doesnt-works/?comment=56162#post-id-56162