opened
wmmxk
username_0
I was trying to understand the output of the algorithm. For example, 

make_path = "/mnt/shortest/cuda-floyd_warshall/test/test_apsp/../.."
exec_name = 'cuda_floyd-warshall'
algorithm = APSP.CUDA_BLOCKED_FW
data, stderr = execute_algorithm(exec_path, algorithm,gen_kn_graph_in(4))

The output data['predecessors'] is [[-1, 0, 0, 0], [1, -1, 1, 1], [2, 2, -1, 2], [3, 3, 3, -1]]. But for this complete graph, I am expecting the shortest path to each node from any node is 1. The result would be [[0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0]]. I think I misunderstood data['predecessors']. Could you explain how to use the algorithm?
How to interpret the results?
issue
created
MTB90
username_1
predecessors is not length of path or number steps but from this matrix you
can read whole path
maybe I will explain this on different case
C5 -> circle graph



input data:
5 5
0 1 1
1 2 1
2 3 1
3 4 1
4 0 1

input matrix will look like

INF, 1, INF, INF, INF
INF, INF, 1, INF, INF
INF, INF, INF, 1, INF
INF, INF, INF, INF, 1
1, INF, INF, INF, INF

vertex 0 connected with vertex 1 with length 1
vertex 1 connected with vertex 2  with length 1
...
vertex 4 connected with vertex 0  with length 1

v0 -> v1 -> v2 -> v3 -> v4 -> v0


shortest path will look be:
[[0, 1, 2, 3, 4],
[4, 0, 1, 2, 3],
[3, 4, 0, 1, 2],
[2, 3, 4, 0, 1],
[1, 2, 3, 4, 0]]

predecessors matrix will be:


[[-1, 0, 1, 2, 3],
 [4, -1, 1, 2, 3],
 [4, 0, -1, 2, 3],
 [4, 0, 1, -1, 3],
 [4, 0, 1, 2, -1]]

imagine that you want recreate path from v1 to v4

so you will select row 1 and column 4 (start counting from 0)

[[-1, 0, 1, 2, 3],
 [4, -1, 1, 2, *3*],
 [4, 0, -1, 2, 3],
 [4, 0, 1, -1, 3],
 [4, 0, 1, 2, -1]]

you will get 3, this mean that
before v4 we need to go first to v3

so you will select row 1 and column 3
[[-1, 0, 1, 2, 3],
 [4, -1, 1, *2*, 3],
 [4, 0, -1, 2, 3],
 [4, 0, 1, -1, 3],
 [4, 0, 1, 2, -1]]

2
before v3 we need to go first to v2

[[-1, 0, 1, 2, 3],
 [4, -1, *1*, 2, 3],
 [4, 0, -1, 2, 3],
 [4, 0, 1, -1, 3],
 [4, 0, 1, 2, -1]]

1
before v2 we need to go first to v1 but we are in v1  :) so algorithm ends
hire

and the whole path is
v1 -> v2 -> v3 -> v4


Regards,
Mateusz
comment
created
wmmxk
username_0
Thanks so much for your detailed reply. I see. The predecessor matrix stores the information for recovering the shortest path. The data['graph'] stores the shortest path. I mistook the data['graph'] as the adjacent matrix of the graph. I just tested on a few small graphs and it worked.  I really like your implementation.
comment
closed
wmmxk
username_0
issue
created
MTB90
username_1
Thx  ;)
comment