tpl_netcost.H File Reference

Maximum flow minimum cost network algorithms. More...

#include <limits>
#include <chrono>
#include <tpl_net.H>
#include <tpl_dynMapTree.H>
#include <tpl_find_path.H>
#include <tpl_cut_nodes.H>
#include <Bellman_Ford.H>
#include <generate_graph.H>
#include <ah-errors.H>

Include dependency graph for tpl_netcost.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Net_Cost_Arc< Arc_Info, F_Type >
	Arc type for maximum flow minimum cost networks. More...
struct	Aleph::Net_Cost_Graph< NodeT, ArcT >
	Capacitated flow network with costs associated to arcs. More...
struct	Aleph::Res_Filt< Net >
	Arc filter for residual networks. More...
struct	Aleph::Rcost< Net >
	Cost distance functor for Bellman-Ford on residual networks. More...
struct	Aleph::Res_Arc< Ftype >
	Residual arc type with mirror pointer. More...
struct	Aleph::Max_Flow_Min_Cost_By_Cycle_Canceling< Net, Max_Flow_Algo >
	Functor wrapper for maximum flow minimum cost algorithm. More...
struct	Aleph::Simplex_Node_Info< Ftype >
	Node information for Network Simplex algorithm. More...
struct	Aleph::Simplex_Arc_Info< Ftype >
	Arc information for Network Simplex algorithm. More...
struct	Aleph::NetworkSimplexStats
	Execution statistics for Network Simplex algorithm. More...
class	Aleph::Network_Simplex< Net >
	Network Simplex algorithm for minimum cost flow. More...
struct	Aleph::Max_Flow_Min_Cost_By_Network_Simplex< Net, Max_Flow_Algo >
	Functor wrapper for Network Simplex algorithm. More...

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

Typedefs
template<typename Node_Info = Empty_Class>
using	Aleph::Net_Cost_Node = Net_Node< Node_Info >
	Node type alias for cost networks.
template<typename Ftype >
using	Aleph::Residual_Net = Net_Cost_Graph< Net_Node< Empty_Class >, Res_Arc< Ftype > >
	Residual network type alias.
template<class Net >
using	Aleph::Feasible_Tree = std::tuple< DynList< typename Net::Arc * >, DynList< typename Net::Arc * >, DynList< typename Net::Arc * > >
	Feasible spanning tree classification.

Enumerations
enum class	Aleph::Simplex_Arc_State : unsigned char { Aleph::Lower , Aleph::Upper , Aleph::Tree }
	Arc state in Network Simplex. More...

Functions
template<class Res_Net >
Res_Net::Arc *	Aleph::create_residual_arc (Res_Net &residual_net, typename Res_Net::Node *src, typename Res_Net::Node *tgt, const typename Res_Net::Flow_Type cap, const typename Res_Net::Flow_Type flow, const typename Res_Net::Flow_Type cost)
	Create a pair of residual arcs in the residual network.
template<class Net >
Residual_Net< typenameNet::Flow_Type >::Node *	Aleph::build_residual_net (const Net &net, Residual_Net< typename Net::Flow_Type > &rnet, DynMapTree< void *, void * > &arcs)
	Build a residual network from a flow network.
template<class Res_Net >
bool	Aleph::check_residual_net (const Res_Net &net)
	Verify residual network consistency.
template<class Res_Net >
void	Aleph::cancel_cycle (const Res_Net &, const Path< Res_Net > &path)
	Cancel a negative cycle by augmenting flow.
template<class Net >
void	Aleph::residual_to_net (const DynMapTree< void *, void * > &arcs)
	Transfer flow values from residual network back to original.
template<class Net , template< class > class Max_Flow_Algo = Ford_Fulkerson_Maximum_Flow>
std::tuple< size_t, double >	Aleph::max_flow_min_cost_by_cycle_canceling (Net &net, double it_factor=0.4, size_t step=10)
	Compute maximum flow at minimum cost using cycle canceling.
template<class Net >
void	Aleph::print_net_cost (const Net &net, std::ostream &out)
	Output a flow network to Graphviz format.
template<class Net >
void	Aleph::print_residual_net (const Residual_Net< typename Net::Flow_Type > &net, std::ostream &out)
	Output a residual network to Graphviz format.
template<class Net >
Feasible_Tree< Net >	Aleph::build_feasible_spanning_tree (const Net &net)
	Build feasible spanning tree classification.
template<class Net >
DynList< typename Net::Arc * >	Aleph::get_partial_arcs (const Net &net)
	Get arcs with partial flow (0 < flow < cap).
template<class Net , template< class > class Max_Flow_Algo = Ford_Fulkerson_Maximum_Flow>
size_t	Aleph::max_flow_min_cost_by_network_simplex (Net &net)
	Compute maximum flow at minimum cost using Network Simplex.

Detailed Description

Maximum flow minimum cost network algorithms.

This file provides data structures and algorithms for solving the maximum flow minimum cost problem on capacitated networks.

The main algorithm implemented is cycle-canceling, which first computes a maximum flow using Ford-Fulkerson (or another max-flow algorithm), then iteratively finds and cancels negative-cost cycles in the residual network using Bellman-Ford until no more negative cycles exist.

Author

Leandro Rabindranath León

Definition in file tpl_netcost.H.