README.md

Network-flows: a c++ command line tool for network optimization problems

1. Description
2. Project structure
3. Algorithms
4. How to use
5. Python Tester

Description

Command-line solver of the following network flows optimization problems:

1. Maximum Flow: it seeks a feasible solution that sends the maximum amount of flow from a specified source note s to node t per unit of time.
2. Minimum Cost Flow: it is the most fundamental of all the network flow problems. It searches for the cheapest possible way of sending a certain amount of flow through a flow network.
3. In particular, the solver solves the minimum cost maximum flow problem, seeking the least-cost maximum flow.

Algorithms

Maximum Flow:

• Edmonds-Karp

Minimum Cost Flow:

• Cycle Cancelling Algorithm
• Successive Shortest Path Algorithm
• Primal-Dual Algorithm

Basic algorithms:

• BFS
• Bellman-Ford
• Dijkstra

(See the implementations here)

Project structure

• data: example graphs
• docs: report of the project and results of the algorithms applied to the graphs inside data directory
• pyTest: python tester which permits to easily solve the network flow problems and to draw a graph using matplotlib
• src: the command-line tool source files

How to use

The following commands are for a generic Linux system, you may need to adapt them depending on your os

Requirements

CMake: minimum version 3.20, see here how to install.

Use your own graph

Both the c++ command line tool and the Python solver requires an input graph described by a well-formed JSON file.
To run the algorithms on you own graph you have to create a JSON file formatted as following:

{
    "Num_nodes": 5,
    "Edges": [
      {
        "Source": 0,
        "Sink": 1,
        "Capacity": 3,
        "Cost": 1
      },
      {
        "Source": 0,
        "Sink": 2,
        "Capacity": 2,
        "Cost": 1
      },
      {
        "Source": 1,
        "Sink": 2,
        "Capacity": 2,
        "Cost": 1
      },
      {
        "Source": 1,
        "Sink": 3,
        "Capacity": 2,
        "Cost": 1
      },
      {
        "Source": 2,
        "Sink": 3,
        "Capacity": 3,
        "Cost": 1
      },
      {
        "Source": 2,
        "Sink": 4,
        "Capacity": 1,
        "Cost": 1
      },
      {
        "Source": 3,
        "Sink": 4,
        "Capacity": 3,
        "Cost": 1
      }
    ]
 }

• Num_nodes: number of nodes of the graph;
• Edges: JSON array containing all the edges;
• Source: source node of the direct edge;
• Sink: sink node of the edge;
• Capacity: maximum capacity of the edge;
• Cost: cost (or weight) per unit flow of the edge,

Note:

• The first node (source) has index 0;
• The last node (sink) has index Num_nodes - 1;
• Each edge must have positive (> 0) capacity and cost.

See data directory for more examples.

Build

1. Clone the repo:

    git clone [email protected]:LorenzoDrudi/network-flows.git

2. Enter the repo:

    cd network-flows

3. Generate project build system:

    cmake -S . -B build

This command creates a build folder containing all the cmake files and the executable.

4. Build the project:

    cmake --build build

Run

1. After doing the build, enter the build folder:

  cd build

2. Run the project:

  ./network_flows path/filename.json

The argument passed to the executable is the full or relative path of the JSON file of the graph
(e.g. ./network_flows ../data/graph1.json).
The filename argument is optional, you can enter it during the execution.

Python Tester

Inside the pyTest directory there is a simple python solver developed using Networkx library. The solver permits to:

• draw a graph using matplotlib
• solve the maximum flow problem
• solve the minimum cost maximum flow problem

Requirements:

Python3: see here how to install

How to use:

The following commands are for a generic linux system, you may need to adapt them depending on your os

1. Enter the directory:

  cd pyTest

(You can ignore the next 2 steps (2, 3) if you want to install Python dependencies locally)

2. Create a python virtual environment where install all the required dependencies:

  python3 -m venv venv

3. Activate the virtual environment:

  source venv/bin/activate

4. Install requirements:

  pip install -r requirements.txt

5. Execute the Python solver:

  python3 graph_solver.py path/filename.json

(e.g. python3 graph_solver.py ../data/graph1.json)

6. Then, when you don't need anymore the python solver, deactivate the virtual environment:

  deactivate