FlowMax

A comprehensive benchmarking suite for maximum flow algorithms with specialized datasets and real-world case studies.

Usage

Running Algorithm Benchmarks

Each algorithm folder contains implementations and scripts to run all 21 datasets:

# Edmonds-Karp Algorithm
cd edmonds_karp
./run_all_datasets.sh    # Runs edmonds_karp.py on all datasets
python3 edmonds_karp.py ../datasets/DATASET_NAME.txt  # Single dataset

# Dinic's Algorithm  
cd dinic
./run_all_datasets.sh    # Runs dinic.py on all datasets
python3 dinic.py ../datasets/DATASET_NAME.txt  # Single dataset

# Push-Relabel Algorithm (includes Gap Heuristic)
cd push_relabel
./run_all_datasets.sh    # Runs both standard and gap-optimized versions
python3 push_relabel.py ../datasets/DATASET_NAME.txt  # Single dataset

Output Files:

• output.txt - Detailed execution log with flow values and paths
• metrics.txt - Performance summary table with runtime and memory usage

Running Case Studies

Each case study demonstrates real-world applications:

# Airline Crew Scheduling (Hopcroft-Karp for bipartite matching)
cd case_studies/airline_scheduling
python3 Hopcroft-Karp_Implementation/hopcroft_karp_scheduler.py

# Image Segmentation (Boykov-Kolmogorov for grid graphs)
cd case_studies/image_segmentation
python3 Boykov-Kolmogorov_Implementation/boykov_kolmogorov_segmentation.py

# Video Segmentation (Temporal extension)
cd case_studies/video_segmentation
python3 video_segmentation.py

# Network Routing (Bandwidth optimization)
cd case_studies/network_routing
python3 Edmonds-Karp_Implementation/edmonds_karp_router.py

Generating Test Datasets

To regenerate the 21 specialized benchmark datasets:

cd datasets
python3 generate_test_graphs.py

This creates 7 categories of graphs (Dense, Sparse, Bipartite, Grid, LongPath, MultiStage, RandomDAG) with 3 datasets each.

Running Full Benchmark Suite

To run all algorithms on all datasets and generate comparison results:

python3 run_full_benchmark.py

This executes all algorithms, collects metrics, and generates benchmark_results.csv.

Visualization Dashboard

To view interactive performance visualizations:

python3 dashboard.py

Opens a web-based dashboard with:

• Runtime comparison charts
• Memory usage analysis
• Algorithm performance by dataset category
• Case study results

Algorithms Implemented

Python implementations with comprehensive metrics collection:

1. Edmonds-Karp
2. Dinic's Algorithm
3. Push-Relabel (FIFO)

Datasets:

1. BIPARTITE_250x1000.txt
2. BIPARTITE_500x2000.txt
3. BIPARTITE_1000x4000.txt
4. DENSE_0050.txt
5. DENSE_0100.txt
6. DENSE_0200.txt
7. GRID_20x20.txt
8. GRID_30x30.txt
9. GRID_40x40.txt
10. LONGPATH_0100.txt
11. LONGPATH_0200.txt
12. LONGPATH_0500.txt
13. MULTISTAGE_5x20.txt
14. MULTISTAGE_7x15.txt
15. MULTISTAGE_10x10.txt
16. RANDOM_DAG_0100.txt
17. RANDOM_DAG_0300.txt
18. RANDOM_DAG_0500.txt
19. SPARSE_0500.txt
20. SPARSE_1000.txt
21. SPARSE_2000.txt

Algorithm Performance by Dataset

Dataset	Edmonds-Karp	Dinic	Push-Relabel
BIPARTITE_250x1000	✓	Best	✓
BIPARTITE_500x2000	✓	Best	✓
BIPARTITE_1000x4000	✓	Best	✓
DENSE_0050	✓	✓	Best
DENSE_0100	✓	✓	Best
DENSE_0200	✓	✓	Best
GRID_20x20	✓	✓	Best
GRID_30x30	✓	✓	Best
GRID_40x40	✓	✓	Best
LONGPATH_0100	Slow	Best	✓
LONGPATH_0200	Slow	Best	✓
LONGPATH_0500	Slow	Best	✓
MULTISTAGE_5x20	✓	Best	✓
MULTISTAGE_7x15	✓	Best	✓
MULTISTAGE_10x10	✓	Best	✓
RANDOM_DAG_0100	✓	Best	✓
RANDOM_DAG_0300	✓	Best	✓
RANDOM_DAG_0500	✓	Best	✓
SPARSE_0500	✓	Best	✓
SPARSE_1000	✓	Best	✓
SPARSE_2000	✓	Best	✓

Case Studies

Real-world applications using max flow algorithms:

1. Airline Scheduling (pilot-flight matching)
2. Image Segmentation (foreground/background separation)
3. Network Routing (bandwidth optimization)

Algorithm Performance by Case Study

Case Study	Edmonds-Karp	Dinic	Push-Relabel
Airline Scheduling	Used	✓	✓
Image Segmentation	Used	✓	✓
Network Routing	Used	✓	✓