tpl_maxflow.H File Reference

Advanced maximum flow algorithms. More...

#include <cassert>
#include <limits>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <tpl_array.H>
#include <tpl_dynListQueue.H>
#include <tpl_net.H>
#include <tpl_dynDlist.H>
#include <ah-errors.H>
#include <cookie_guard.H>

Include dependency graph for tpl_maxflow.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Dinic_Node_Info< Flow_Type >
	Level information for Dinic's algorithm. More...
struct	Aleph::Dinic_Maximum_Flow< Net >
	Functor wrapper for Dinic's algorithm. More...
struct	Aleph::Capacity_Scaling_Maximum_Flow< Net >
	Functor wrapper for capacity scaling. More...
struct	Aleph::FlowPath< Net >
	Represents a flow path from source to sink. More...
struct	Aleph::FlowCycle< Net >
	Represents a flow cycle in the network. More...
struct	Aleph::FlowDecomposition< Net >
	Result of flow decomposition. More...
struct	Aleph::Decompose_Flow< Net >
	Functor wrapper for flow decomposition. More...
struct	Aleph::HLPP_Node_Info< Flow_Type >
	Node info for HLPP algorithm. More...
struct	Aleph::HLPP_Maximum_Flow< Net >
	Functor wrapper for HLPP. More...
struct	Aleph::FlowStatistics< Flow_Type >
	Statistics about a network flow. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class Net >
long &	Aleph::dinic_level (typename Net::Node *p) noexcept
	Access the node level in Dinic's algorithm.
template<class Net >
bool &	Aleph::dinic_blocked (typename Net::Node *p) noexcept
	Check if a node is blocked in Dinic's algorithm.
template<class Net >
size_t &	Aleph::dinic_current_arc (typename Net::Node *p) noexcept
	Access the current arc index in Dinic's algorithm.
template<class Net >
bool	Aleph::is_dinic_cookie_valid (typename Net::Node *p) noexcept
	Check if a node's cookie is properly initialized for Dinic's algorithm.
template<class Net >
bool	Aleph::build_level_graph (Net &net, typename Net::Node *source, typename Net::Node *sink)
	Build level graph using BFS from source.
template<class Net >
Net::Flow_Type	Aleph::dinic_blocking_flow (Net &net, typename Net::Node *source, typename Net::Node *sink)
	Find all blocking flows using iterative DFS with current-arc optimization.
template<class Net >
Net::Flow_Type	Aleph::dinic_maximum_flow (Net &net)
	Compute maximum flow using Dinic's algorithm.
template<class Net >
Net::Flow_Type	Aleph::capacity_scaling_maximum_flow (Net &net)
	Compute maximum flow using capacity scaling.
template<class Net >
FlowDecomposition< Net >	Aleph::decompose_flow (const Net &net)
	Decompose network flow into paths and cycles.
template<class Net >
long &	Aleph::hlpp_height (typename Net::Node *p) noexcept
	Access the height label stored in the node's cookie.
template<class Net >
Net::Flow_Type &	Aleph::hlpp_excess (typename Net::Node *p) noexcept
	Access the excess flow stored in the node's cookie.
template<class Net >
Net::Flow_Type	Aleph::hlpp_maximum_flow (Net &net)
	Compute maximum flow using Highest-Label Preflow-Push.
template<class Net >
FlowStatistics< typename Net::Flow_Type >	Aleph::compute_flow_statistics (const Net &net)
	Compute statistics about the current flow in a network.

Detailed Description

Advanced maximum flow algorithms.

This file provides advanced algorithms for the maximum flow problem, complementing the basic algorithms in tpl_net.H.

Algorithms Included

Dinic's Algorithm

• Complexity: O(V²E) for general graphs, O(E√V) for unit capacity
• Best for: Dense graphs, unit capacity networks
• Uses level graphs and blocking flows for efficiency

Capacity Scaling

• Complexity: O(E² log U) where U is max capacity
• Best for: Networks with large capacity values
• Uses scaling phases to reduce augmenting path searches

Flow Decomposition

• Decomposes a flow into s-t paths and cycles
• Useful for routing, analysis, and visualization

Usage Example

#include <tpl_maxflow.H>
 
Net_Graph<> net;
// ... build network ...
 
// Using Dinic's algorithm
auto flow = dinic_maximum_flow(net);
 
// Using Capacity Scaling
auto flow = capacity_scaling_maximum_flow(net);
 
// Decompose the flow
auto [paths, cycles] = decompose_flow(net);
for (const auto& path : paths)
  std::cout << "Path with flow " << path.flow << "\n";

See also

tpl_net.H Basic network flow structures and algorithms

tpl_netcost.H Minimum cost flow algorithms

Author

Leandro Rabindranath León

Definition in file tpl_maxflow.H.