Floyd Warshall Algorithm

This repository is created as part of the Practical Assessment for University of Liverpool's CSCK541 Software Development in Practice Module (June 2022 A)

floydwarshall is a Python module that implements the Floyd Warshal algorithm for computing the shortest path between all pairs of vertices in a graph. This includes a set of functions for the Floyd Warshall Algorithm written iteratively and recursively.

tests is included to test for the functions and ensure that the functions work as expected.

Floyd Warshall Algorithm

Install

Use the package manager pip to install Floyd Warshall Algorithm using the following command:

pip install git+https://github.com/zhulinchng/floydwarshall.git

Re-run the above command to check for and install updates.

Usage

Functions for Floyd Warshall Algorithm

fw_iterative, fw_recursive, fw_recursive_memo are the main functions of the floydwarshall package.

Each function takes a graph (2d array, i.e. list of lists) as input and returns the shortest path matrix.

fw_iterative is the most efficient algorithm, but it is not recursive.

python

>>> from floydwarshall import fw_iterative, fw_recursive, fw_recursive_memo
>>> example_graph = [[0, 7, 2], [9, 0, 3], [3, 9, 0]]
>>> shortest_graph = fw_iterative(example_graph)
>>> shortest_graph
[[0, 7, 2], [6, 0, 3], [3, 9, 0]]

fw_recursive is the most efficient recursive algorithm, but it is not memoized.

>>> shortest_graph = fw_recursive(example_graph)
>>> shortest_graph
[[0, 7, 2], [6, 0, 3], [3, 9, 0]]

fw_recursive_memo is the most efficient recursive algorithm, and it is memoized.

>>> shortest_graph = fw_recursive_memo(example_graph)
>>> shortest_graph
[[0, 7, 2], [6, 0, 3], [3, 9, 0]]

Miscellaneous Functions

Graph generation and validation

graph_generator is a function that generates a graph of a given size.

>>> from floydwarshall import graph_generator
>>> from math import inf
>>> graph_generator()
[[0, 99, 24, 49, 89], [24, 0, 85, 35, 33], [21, 67, 0, 92, 26], [inf, 59, inf, 0, 43], [79, 84, 34, inf, 0]]

Different graphs can be generated by passing arguments into the function.

graph_generator(size: int = 5,          # size of square matrix to generate
                edgeprob: float = 0.8,  # probability of an edge between two nodes
                minval: float = 0,      # minimum value of an edge
                maxval: float = 100,    # maximum value of an edge
                seed: float = None)     # seed for random number generator

negative_loop_checker is a function that checks if a graph have negative cycles.

By default, it uses an iterative floyd warshall algorithm calculate the shortest path and check if there is a negative cycle.

If there is a negative cycle, the node will loop back to itself with negative weights and the function will return False.

>>> from floydwarshall import negative_loop_checker
>>> from math import inf
>>> negative_loop_checker([[0, 7, 2], [6, 0, 3], [3, 9, 0]])
True
>>> negative_loop_checker([[0, -10, 0, inf], [-5, 0, -9, inf], [-10, -14, 0, 2], [inf, -13, inf, 0]])
False

Different functions can be used to check for negative cycle by passing function argument into the function.

negative_loop_checker(graph: list of lists,  # graph to check for negative cycles
                      func=fw_iterative_mod) # floyd warshall algorithm to use to check

Tests

Unit Tests

Unit tests are performed to ensure that the algorithm is working correctly.

fw_iterative, fw_recursive, fw_recursive_memo are tested.

The same set of inputs are used for the unit tests.

To run the tests, import the built-in unittest package and the TestFloydWarshall class from the tests module and run unittest.main() as follows:

>>> import unittest
>>> from tests import TestFloydWarshall
>>> unittest.main()
..
----------------------------------------------------------------------
Ran 2 tests in 0.001s

OK

Results are printed to the console: Sample of the result

Performance tests

Performance tests are performed to compare the performance of algorithm written in different ways. Functions:

perf_test(fn: callable) --> Generates the same set of 11 different test cases ranging from 0x0 to 10x10 square matrices.
timeit_perf_test --> Takes in an algorithm function and tests the algorithm on the test cases generated by perf_test using timeit.repeat for 25 times, with every 5th time being used for the total time, the function prints the minimum total time to the console.
cprofile_perf_test --> Takes in an algorithm function and tests the algorithm on the test cases generated by perf_test using cProfile.run for 1 time, the function prints the profile data to the console.

Timeit

Performance are measured in terms of time taken to execute the algorithm using the timeit module against the same set of inputs.

To run the tests, import the functions to test from the floydwarshall module, and the timeit_perf_test and perf_test function from the tests module and run the timeit_perf_test function with the algorithm function as an argument as follows:

>>> from floydwarshall import fw_iterative, fw_recursive, fw_recursive_memo
>>> from tests import perf_test, timeit_perf_test

>>> timeit_perf_test(fw_iterative)
Time taken for fw_iterative is 0.0033771999878808856 seconds

>>> timeit_perf_test(fw_recursive)
Time taken for fw_recursive is 4.942898500012234 seconds

>>> timeit_perf_test(fw_recursive_memo)
Time taken for fw_recursive_memo is 0.010060300002805889 seconds

cProfile

Performance are also measured in terms of the number of calls and time taken to execute the algorithm using cProfile module against the same set of inputs.

To run the tests, import the functions to test from the floydwarshall module, and the cprofile_perf_test and perf_test function from the tests module and run the cprofile_perf_test function with the algorithm function as an argument as follows:

>>> from floydwarshall import fw_iterative, fw_recursive, fw_recursive_memo
>>> from tests import perf_test, cprofile_perf_test
>>> cprofile_perf_test(fw_iterative)
>>> cprofile_perf_test(fw_recursive)
>>> cprofile_perf_test(fw_recursive_memo)

Results

Results are printed to the console.

Explanation and a sample of the result

Repository Tree

floyd-warshall-algorithm
│   .gitignore
│   LICENSE
│   README.md
│   requirements.txt
│   setup.py
│
├───floydwarshall
│       fw_algo.py
│       graph_io.py
│       tc_generator.py
│       __init__.py
│
└───tests
    │   generate_perf_test_cases_pickle.py
    │   performance_test.py
    │   unit_test.py
    │   __init__.py
    │
    ├───performance_tests
    │   │   performance_test_results.md
    │   │
    │   └───data
    │           perf_data.pkl
    │
    └───unit_tests
        │   unit_test_results.md
        │
        └───data
                case0_input.txt
                case0_output.txt
                case1_input.txt
                case1_output.txt
                case2_input.txt
                case2_output.txt

Contributing

Pull requests are welcome. For major changes, open an issue to discuss beforehand.

License

MIT License

zhulinchng/floydwarshall