1 unstable release
0.1.0 | Jan 6, 2023 |
---|
#532 in Science
6KB
72 lines
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