tpl_mincost.H File Reference

Advanced minimum cost flow algorithms. More...

#include <limits>
#include <queue>
#include <functional>
#include <tpl_netcost.H>
#include <tpl_dynBinHeap.H>
#include <ah-errors.H>

Include dependency graph for tpl_mincost.H:

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

Go to the source code of this file.

Classes
struct	Aleph::SSP_Node_Info< Flow_Type >
	Node info for SSP algorithm. More...
struct	Aleph::Successive_Shortest_Paths< Net >
	Functor wrapper for SSP algorithm. More...
struct	Aleph::Transshipment_Node_Info< Flow_Type >
	Node with supply/demand for transshipment problems. More...
struct	Aleph::TransshipmentResult< Flow_Type >
	Result of transshipment problem. More...
struct	Aleph::AssignmentResult< Cost_Type >
	Result of assignment problem. More...
struct	Aleph::TransportationResult< Cost_Type >
	Result of transportation problem. More...
struct	Aleph::MinCostFlowStats< Flow_Type >
	Statistics for min-cost flow algorithms. More...

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

Functions
template<class Net >
SSP_Node_Info< typename Net::Flow_Type > &	Aleph::ssp_info (typename Net::Node *p) noexcept
	Access SSP node info.
template<class Net >
Net::Flow_Type	Aleph::reduced_cost (const Net &net, typename Net::Arc *arc, typename Net::Node *from, bool forward)
	Compute reduced cost of an arc.
template<class Net >
bool	Aleph::ssp_shortest_path (Net &net, typename Net::Node *source, typename Net::Node *sink)
	Find shortest path using Dijkstra with potentials.
template<class Net >
std::pair< typename Net::Flow_Type, typename Net::Flow_Type >	Aleph::successive_shortest_paths (Net &net)
	Compute minimum cost maximum flow using Successive Shortest Paths.
template<class Net >
bool	Aleph::ssp_init_potentials (Net &net, typename Net::Node *source)
	Initialize potentials using Bellman-Ford.
template<class Net , class GetDemand >
TransshipmentResult< typename Net::Flow_Type >	Aleph::solve_transshipment (Net &net, GetDemand get_demand)
	Solve minimum cost transshipment problem.
template<typename Cost_Type >
AssignmentResult< Cost_Type >	Aleph::solve_assignment (const std::vector< std::vector< Cost_Type > > &costs)
	Solve the assignment problem using min-cost flow.
template<typename Cost_Type >
TransportationResult< Cost_Type >	Aleph::solve_transportation (const std::vector< Cost_Type > &supplies, const std::vector< Cost_Type > &demands, const std::vector< std::vector< Cost_Type > > &costs)
	Solve the transportation problem using min-cost flow.
template<class Net >
DynMapTree< typename Net::Arc *, typename Net::Flow_Type >	Aleph::save_flow_solution (const Net &net)
	Save network simplex solution for warm start.
template<class Net >
void	Aleph::restore_flow_solution (Net &net, const DynMapTree< typename Net::Arc *, typename Net::Flow_Type > &solution)
	Restore network simplex solution from warm start.

Detailed Description

Advanced minimum cost flow algorithms.

This file provides additional algorithms for the minimum cost flow problem, complementing the algorithms in tpl_netcost.H.

Algorithms Included

Successive Shortest Paths (SSP)

• Complexity: O(V * E + V * U * SP) where SP is shortest path time
• Best for: Sparse graphs with small flow values
• Intuitive algorithm that repeatedly finds min-cost augmenting paths

Cost Scaling

• Complexity: O(V³ log(V * C)) strongly polynomial
• Best for: Dense graphs with large costs
• Uses epsilon-scaling to achieve polynomial time

Primal-Dual (Hungarian Method variant)

• Complexity: O(V² * E)
• Best for: Assignment and transportation problems

Comparison

Algorithm	Time Complexity	Best Use Case
Cycle Canceling	O(V*E²*C*U)	Simple implementation
Network Simplex	O(n*m*log(n*C))	General purpose
SSP	O(V*U*m*log(V))	Small flow values
Cost Scaling	O(V³*log(V*C))	Dense, large costs

See also

tpl_netcost.H Basic min-cost flow algorithms

tpl_net.H Network flow structures

Author

Leandro Rabindranath León

Definition in file tpl_mincost.H.