Solving the Maximum Flow Problem with Dinic's Algorithm

This project is a class assignment at ENSIIE in the "functional programming" course. The goal was to implement the Dinic algorithm to solve the maximum flow problem using Ocaml. In the context of this project, we will use it to maximize the flow of coffee from a source to a sink.

This project is split into 3 parts :

• Implementation of the graph data structure
• Implementation of the BFS algorithm
• Implementation of the Dinic algorithm

Table of contents

• Requirements
• Usage
• Sources

Requirements

This project requires Ocaml and Make :

For Debian distributions, you can install the libraries using the following command:

sudo apt-get install ocaml make

Usage

To compile the project, you can use the following command:

make 

Then to run the project, you can use those commands:

./phase1 "name_of_file.txt"

This command will run the second part of the project, which is the implementation of the BFS algorithm. It will use an input file to create a graph, and then it will run the algorithm. An output file will then be created.

./phase2 "name_of_file.txt"

This command will run the third part of the project which is the implementation of the Dinic algorithm and also create an output file.

./test

This command will run the set of test made to test the implementation of the graph data structure with the BFS algorithm and the Dinic algorithm.

Sources

• Ocaml
• Dinic's algorithm
• Video explaining the Dinic algorithm

Disclaimer

The file analyse.ml and analyse.mli are not written by us. They are provided by the teacher of the course. Comments are in French. The picture's from wikipedia.