Advanced Maximum Flow Algorithms Comparison. More...

#include <iostream>
#include <iomanip>
#include <chrono>
#include <vector>
#include <string>
#include <cstring>
#include <tpl_net.H>
#include <tpl_maxflow.H>

Include dependency graph for maxflow_advanced_example.cc:

Typedefs
using	FlowType = double

using	Net = Net_Graph< Net_Node< string >, Net_Arc< Empty_Class, FlowType > >

using	Node = Net::Node

Functions
static void	usage (const char *prog)

static bool	has_flag (int argc, char argv[], const char flag)

static const char *	get_opt_value (int argc, char argv[], const char opt)

Net	build_supply_chain ()
	Build a supply chain network.

Net	build_grid_network (int rows, int cols, FlowType base_cap=10.0)
	Build a grid network for stress testing.

template<typename Algorithm >
pair< FlowType, double >	time_algorithm (Net net)
	Time a max-flow algorithm execution.

void	print_flow_stats (Net &net, const string &title)
	Print network flow statistics.

void	demonstrate_flow_decomposition (Net &net)
	Demonstrate flow decomposition into paths.

void	compare_algorithms (int grid_size)
	Compare all algorithms on the same network.

void	demonstrate_min_cut (Net &net)
	Demonstrate min-cut duality.

int	main (int argc, char *argv[])

Detailed Description

Advanced Maximum Flow Algorithms Comparison.

This example demonstrates and compares different maximum flow algorithms available in Aleph-w. While basic Ford-Fulkerson/Edmonds-Karp works well for many cases, advanced algorithms offer better performance for specific graph types and scenarios.

Why Multiple Algorithms?

Different max-flow algorithms excel in different scenarios:

Graph density: Sparse vs dense graphs
Capacity size: Small vs large capacities
Graph structure: Special properties
Performance requirements: Speed vs simplicity

Algorithms Covered

1. Edmonds-Karp (Ford-Fulkerson with BFS)

Strategy: Use BFS to find shortest augmenting paths

Complexity: O(V × E²)

Each BFS: O(E)
At most O(VE) augmentations

Pros:

Simple to understand and implement
Predictable performance
Good for sparse graphs

Cons:

Slower for dense graphs
May do many augmentations

2. Dinic's Algorithm

Strategy: Use level graphs and blocking flows

How it works:

Build level graph (BFS layers)
Find blocking flow (saturate all paths in level graph)
Repeat until no augmenting path

Complexity: O(V² × E)

O(V) blocking flow computations
Each blocking flow: O(VE)

Pros:

Faster than Edmonds-Karp
Good for both sparse and dense graphs
Practical performance often better than worst case

Cons:

More complex implementation

3. Capacity Scaling

Strategy: Process edges in rounds by capacity threshold

How it works:

Start with large capacity threshold Δ
Only consider edges with capacity ≥ Δ
Find augmenting paths in this subgraph
Reduce Δ and repeat

Complexity: O(V × E × log U)

U = maximum capacity
log U rounds
O(VE) work per round

Pros:

Efficient for large capacities
Good when capacities vary widely

Cons:

Overhead for small capacities

4. HLPP (Highest Label Preflow-Push)

Strategy: Push-relabel with highest label selection

How it works:

Push flow from active vertices
Relabel vertices when stuck
Always process highest label vertex

Complexity: O(V² × √E)

Best theoretical for dense graphs

Pros:

Best complexity for dense graphs
Efficient in practice

Cons:

Most complex implementation
May be slower for sparse graphs

Complexity Comparison

Algorithm	Time Complexity	Best For
Edmonds-Karp	O(V × E²)	Sparse graphs, simplicity
Dinic	O(V² × E)	General purpose
Capacity Scaling	O(V × E × log U)	Large capacities
HLPP	O(V² × √E)	Dense graphs

Note: Actual performance depends heavily on graph structure!

When to Use Each Algorithm

Small Graphs (< 100 vertices)

Any algorithm works: Performance difference negligible
Recommendation: Edmonds-Karp (simplest)

Sparse Graphs (E ≈ V)

Edmonds-Karp: Simple, O(V³) effective
Dinic: Better worst-case, often faster
Recommendation: Dinic (best balance)

Dense Graphs (E ≈ V²)

Dinic: O(V⁴) but practical
HLPP: O(V² × √E) = O(V³) theoretical best
Recommendation: HLPP for large graphs, Dinic for medium

Large Capacities (U >> V)

Capacity Scaling: O(V × E × log U) efficient
Others: May be slower
Recommendation: Capacity Scaling

General Purpose

Dinic: Good balance of speed and simplicity
Recommendation: Default choice

Performance Characteristics

Sparse Graph (E = O(V))

Algorithm	Complexity	Relative Speed
Edmonds-Karp	O(V³)	1×
Dinic	O(V³)	2-5× faster
HLPP	O(V².5)	3-10× faster

Dense Graph (E = O(V²))

Algorithm	Complexity	Relative Speed
Edmonds-Karp	O(V⁵)	1×
Dinic	O(V⁴)	10-100× faster
HLPP	O(V³)	100-1000× faster

Applications

Network Bandwidth Optimization

Internet routing: Maximize data flow
Content delivery: Distribute content efficiently

Supply Chain Logistics

Transportation: Maximize goods flow
Resource allocation: Optimize resource usage

Image Segmentation

Min-cut: Find optimal segmentation
Computer vision: Separate foreground/background

Matching Problems

Bipartite matching: Reduce to max-flow
Job assignment: Match workers to tasks

Game Theory

Baseball elimination: Determine if team can win
Tournament analysis: Analyze possible outcomes

Usage

# Run all demos (supply chain + algorithm comparisons + large capacity demo)
./maxflow_advanced_example
 
# Choose the algorithm used for the supply chain demo
./maxflow_advanced_example --algorithm dinic
./maxflow_advanced_example --algorithm hlpp
 
# Run the benchmark comparison on a grid network
./maxflow_advanced_example --sparse
./maxflow_advanced_example --dense

See also: tpl_maxflow.H Advanced max-flow algorithm implementations; network_flow_example.C Basic max-flow example (Ford-Fulkerson); tpl_net.H Network graph structures

Author: Leandro Rabindranath León

Definition in file maxflow_advanced_example.cc.

Typedef Documentation

◆ FlowType

using FlowType = double

Definition at line 270 of file maxflow_advanced_example.cc.

◆ Net

using Net = Net_Graph<Net_Node<string>, Net_Arc<Empty_Class, FlowType> >

Definition at line 271 of file maxflow_advanced_example.cc.

◆ Node

using Node = Net::Node

Definition at line 272 of file maxflow_advanced_example.cc.

Function Documentation

◆ build_grid_network()

Net build_grid_network	(	int	rows,
		int	cols,
		FlowType	base_cap = `10.0`
	)

Build a grid network for stress testing.

Creates a rows x cols grid with right and down connections. Source is automatically detected as the top-left corner, and sink as the bottom-right corner.

Definition at line 326 of file maxflow_advanced_example.cc.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::maps(), nodes, and Aleph::to_string().

Referenced by compare_algorithms(), main(), TEST(), TEST(), and TEST().

◆ build_supply_chain()

Net build_supply_chain ( )

Build a supply chain network.

   [Factory1]----10---->[Warehouse1]----8----+
     |                       |               |
     12                      5               |
     |                       v               v
  [Source]                [Hub]---------->[Sink]
     |                       ^               ^
     15                      6               |
     |                       |               |
   [Factory2]----12---->[Warehouse2]----9---+

Definition at line 287 of file maxflow_advanced_example.cc.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and Aleph::maps().

Referenced by main().