Maximum Flow Algorithms Benchmarking and Testing

Overview

This project implements and benchmarks three variations of the Ford-Fulkerson algorithm: Edmonds-Karp (BFS-based), Fattest Path (maximum-capacity augmenting path), and Randomized DFS. It supports a variety of testing scenarios, including correctness validation and performance evaluation across multiple graph types. The project also includes a reduction from the Winning a Tournament problem to a max-flow instance, allowing evaluation of whether a given team can still win based on current tournament results.

Directory Structure

data/
  ├── graphs/         # DIMACS graphs for testing
  ├── outputs/        # Output .csv files from benchmark runs
  ├── plots/          # Generated plots (.png) from python scripts
include/
reports/              # Reports analyzing and benchmarking the implementations
scripts/              # Bash scripts for generating graphs and running tests
src/
  ├── algorithms/     # Ford-Fulkerson algorithm variants
  ├── data_analysis/  # Python scripts for generating plots and tables
  ├── data_structs/   # Supporting data structures
  ├── generator/      # Graph generator implementation
  ├── helper/         # Helper functions for metric calculation and logging.
  ├── tournament/     # Tournament instance generator and flow graph reduction
  boost_maxflow.cpp   # Boost-based max flow reference implementation
  main.cpp            # Project's main max flow implementation

Features

• Regular Execution

  • The main program runs a selected Ford-Fulkerson variant algorithm on a user-provided DIMACS graph.

  • It expects one command-line argument: the index of the variant to use (0 = Edmonds-Karp, 1 = Randomized DFS, 2 = Fattest Path).

  • The graph must be provided via standard input.

  • Example usage:

    ./bin/flow_solver 1 < test.graph

• Benchmark Execution

  • The main program can run benchmarks over a group of .graph files located in a directory. Each graph is executed multiple times, and performance metrics are averaged and saved to a .csv file.

  • It expects three command-line arguments:

    1. Algorithm index
       0 = Edmonds-Karp, 1 = Randomized DFS, 2 = Fattest Path
    2. Graphs folder path
       Path to a folder containing .graph files
    3. Output file name
       Name of the .csv file to store the aggregated results

  • Example usage:

    ./bin/flow_solver 2 ./data/graphs/mesh/ mesh_fattest.csv

• Graph Dataset Generation

  • The script ./scripts/generate_datasets.sh uses the graph_generator executable to create collections of .graph files for benchmarking.

  • Supports multiple dataset types:

    • mesh: Grid graphs of varying aspect ratios and sizes
    • matching: Random bipartite matchings with controlled degrees
    • random_mesh: Randomized versions of mesh graphs

  • Run the script with all (default) or a specific dataset name:

    ./scripts/generate_datasets.sh            # Generates all datasets
    ./scripts/generate_datasets.sh mesh       # Only generates mesh graphs

• Automated Batch Benchmarking

  • The script ./scripts/run_all_benchmarks.sh automatically benchmarks all .graph files inside each subdirectory of data/graphs/ using all three Ford-Fulkerson variants (0 = Edmonds-Karp, 1 = Randomized DFS, 2 = Fattest Path).
  • For each subdirectory, it produces one CSV output file per algorithm and stores them in data/outputs/.
  • This script is useful for large-scale testing and comparison across multiple graph families with minimal manual intervention.

• Correctness Testing

  • The script ./scripts/correctness_test.sh compares the max flow results for all .graph files inside the data/ directory or any subdirectory, using both the main implementation (for each of the 3 variants) and a reference implementation (boost_maxflow). It checks whether the outputs match and issues a warning if any discrepancies are found.

• Tournament Input Reduction

  • The project supports tournament-based instances where the goal is to determine whether team 1 can still win.
  • These inputs are converted into flow graphs using a custom reduction described in
    src/tournament/generator/README.md.

Build Instructions

To compile the full project, run:

make

To compile only the MaxFlow implementation, run:

make main

To compile only the tournament implementation, run:

make tournament

To clean all compiled files:

make clean

@Dependencies

• GCC with C++17 support
• Make (for building the project)
• Python 3 (optional, for data plotting only) with:
  • @pandas
  • @matplotlib
  • @seaborn

Authors

Diego Hommerding Amorim GitHub • Email

Developed as part of an academic project for the Advanced Algorithms course at UFRGS.