Skip to content

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

License

Notifications You must be signed in to change notification settings

drudilorenzo/network-flows

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

66 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

c++ CMake Python License: MIT Linux

  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:

Minimum Cost Flow:

Basic algorithms:

(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 git@github.com:LorenzoDrudi/network-flows.git
  1. Enter the repo:
    cd network-flows
  1. Generate project build system:
    cmake -S . -B build

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

  1. Build the project:
    cmake --build build

Run

  1. After doing the build, enter the build folder:
  cd build
  1. 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)

  1. Create a python virtual environment where install all the required dependencies:
  python3 -m venv venv
  1. Activate the virtual environment:
  source venv/bin/activate
  1. Install requirements:
  pip install -r requirements.txt
  1. Execute the Python solver:
  python3 graph_solver.py path/filename.json

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

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