path_finder

Find non-looping paths in a graph

How to compile?

cargo build --release

How to use?

The graph is represented as a symmetrical square matrix with zeros for unconnected vertices and ones for connected vertices.

For example, the following graph

Is going to be represented with the following matrix: $$\LARGE{\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}$$

Note that the diagonal of the matrix is filled with zeros because a vertex doesn't connect to itself.

The first input of the program is the start vertex, the second is the end vertex and the third is the matrix.

The output are all the paths from the start to the end vertex that don't repeat any vertex.

For example, for discovering the paths from vertex $0$ to vertex $2$ you would execute:

./target/release/path_finder
0 2
0 1 0
1 0 1
0 1 0
[0, 1, 2]

How fast is it?

Just to you have an idea, this is a benchmark:

time echo "0 9
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0" | ./target/release/path_finder
[0, 1, 9]
[0, 1, 2, 9]
[0, 1, 2, 8, 9]
...
[0, 8, 7, 9]
[0, 8, 9]
[0, 9]

real    0m1.054s
user    0m0.143s
sys     0m0.186s