Skip to content

Latest commit

 

History

History
69 lines (54 loc) · 2.66 KB

README.md

File metadata and controls

69 lines (54 loc) · 2.66 KB

🔀 Ford-Fulkerson algorithm

Release Language

Python project developped for the graph theory course (MATH0499) given by Pr. Rigo, ULiège.
The final mark for this project is 19/20.

Flow example

The Ford-Fulkerson algorithm is a graph algorithm used to determine the maximum flow from a source node to a sink node. It can also be used to calculate if a minimum flow can flow through an entire network.

Using the -g option (see Examples), you can visualize the flow in the graph. The lighter the color of an edge, the more saturated it is.

Summary

  1. Required Modules
  2. Project structure
  3. Examples
  4. Technical Specifics
  5. Credits

Required modules

Project structure

  • ./
    • main.py: Main script
    • ford_fulkerson.py: Script containing the Ford-Fulkerson algorithm and pre-processing functions for loading files into Graph() objects
    • display.py: Script for displaying graphs via matplotlib
    • utils.py: Script for creating random graphs of any size

Examples

  1. Finding the maximum flow from s to t in an existing file

    python3 main.py -i filename.txt -s s -t t
  2. Finding the maximum flow from s to t in an existing file and displaying the residual graph in a window

    python3 main.py -i filename.txt -s s -t t -g
  3. Finding the maximum flow from multiple sources to t in an existing file

    python3 main.py -i filename.txt -s "s_1 s_2 s_3 s_n" -t t
  4. Finding the maximum flow from multiple sources to multiple sinks in an existing file

    python3 main.py -i filename.txt -s "s_1 s_2 s_3 ... s_n" -t "t_1 t_2 ... t_k"
  5. Finding the maximum flow from s to t in a randomly generated file with n vertices

    python3 main.py -r n -s s -t t

Technical specifics

Credits