tpl_net.H File Reference

Network flow graph structures. More...

#include <limits>
#include <set>
#include <tuple>
#include <type_traits>
#include <utility>
#include <tpl_dynDlist.H>
#include <tpl_dynListStack.H>
#include <tpl_dynBinHeap.H>
#include <tpl_dynSetTree.H>
#include <tpl_dynSetHash.H>
#include <tpl_random_queue.H>
#include <tpl_graph_utils.H>
#include <tpl_find_path.H>
#include <graph-traverse.H>
#include <ah-errors.H>

Include dependency graph for tpl_net.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Net_Arc_Info< Arc_Info, Flow_Type >
	Arc info extension that stores capacity and flow values. More...
struct	Aleph::Net_Arc< Arc_Info, F_Type >
	Arc of a flow network implemented with adjacency lists. More...
struct	Aleph::Net_Filt< Net >
	Arc filter for residual traversal in flow networks. More...
struct	Aleph::Net_Graph< NodeT, ArcT >
	Flow network implemented with adjacency lists. More...
class	Aleph::Find_Aumenting_Path< Net, Q >
	Augmenting-path search over a directed network. More...
struct	Aleph::PP_Res_Node< Net >
	Residual node used by preflow-push algorithms. More...
struct	Aleph::__Res_Arc< Net >
struct	Aleph::Res_F< Rnet >
	Residual arc filter: keep arcs with residual capacity. More...
struct	Aleph::Ford_Fulkerson_Maximum_Flow< Net >
	Functor wrapper for ford_fulkerson_maximum_flow(). More...
struct	Aleph::Edmonds_Karp_Maximum_Flow< Net >
	Functor wrapper for edmonds_karp_maximum_flow(). More...
struct	Aleph::Fifo_Preflow_Maximum_Flow< Net >
	Functor wrapper for fifo_preflow_maximum_flow(). More...
struct	Aleph::Compare_Height< Net >
	Compare nodes by height (higher first). More...
struct	Aleph::Heap_Preflow_Maximum_Flow< Net >
	Functor wrapper for heap_preflow_maximum_flow(). More...
struct	Aleph::Random_Preflow_Maximum_Flow< Net >
	Functor wrapper for random_preflow_maximum_flow(). More...
struct	Aleph::Min_Cut< Net, Maxflow >
	Functor wrapper for min_cut(). More...

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

Typedefs
template<class Net >
using	Aleph::__Net_Iterator = Digraph_Iterator< Net, Net_Filt< Net > >
template<class Net , class Show_Arc = Dft_Show_Arc<Net>>
using	Aleph::Net_Iterator = Filter_Iterator< typename Net::Node *, __Net_Iterator< Net >, Show_Arc >
	Residual-graph iterator adapter for flow networks.
template<typename Node_Info = Empty_Class>
using	Aleph::Net_Node = Graph_Anode< Node_Info >
	Node type for flow networks.
template<class Net >
using	Aleph::Parc = std::tuple< typename Net::Arc *, bool >
	Arc entry for a semi-path.
template<class Net >
using	Aleph::SemiPath = std::tuple< bool, typename Net::Flow_Type, DynList< Parc< Net > > >
	Semi-path tuple:
template<class Net >
using	Aleph::Find_Aumenting_Path_DFS = Find_Aumenting_Path< Net, DynListStack >
	Augmenting-path finder using DFS (stack).
template<class Net >
using	Aleph::Find_Aumenting_Path_BFS = Find_Aumenting_Path< Net, DynListQueue >
	Augmenting-path finder using BFS (queue).
template<class Net >
using	Aleph::AP_Res_Net = Array_Digraph< Net_Node< Empty_Class >, __Res_Arc< Net > >
	Residual network for augmenting-path algorithms.
template<class Net >
using	Aleph::PP_Res_Net = Array_Digraph< PP_Res_Node< Net >, __Res_Arc< Net > >
	Residual network for preflow-push algorithms.

Functions
template<class Net >
bool	Aleph::is_residual (typename Net::Node *src, typename Net::Arc *a) noexcept
	Return true if arc a is residual with respect to src.
template<class Net >
Net::Flow_Type	Aleph::remaining_flow (typename Net::Node *src, typename Net::Arc *a) noexcept
	Return the remaining flow of a as seen from src.
template<class Net >
void	Aleph::print (const DynList< Parc< Net > > &sp)
	Print a semi-path to stdout.
template<class Net >
Net::Flow_Type	Aleph::increase_flow (Net &net, const Path< Net > &path)
	Increase flow along an augmenting path.
template<class Net >
void	Aleph::increase_flow (Net &net, const DynList< Parc< Net > > &semi_path, const typename Net::Flow_Type slack)
	Increase flow along a semi-path by a given slack.
template<class Net >
void	Aleph::decrease_flow (Net &net, const DynList< Parc< Net > > &semi_path, const typename Net::Flow_Type slack)
	Decrease flow along a semi-path by a given slack.
template<class Net , template< typename T > class Q>
Path< Net >	Aleph::find_aumenting_path (const Net &net, const typename Net::Flow_Type &min_slack)
	Find an augmenting path using DFS or BFS based on Q.
template<class Net >
Path< Net >	Aleph::find_aumenting_path_dfs (const Net &net, const typename Net::Flow_Type &min_slack)
	Find an augmenting path using DFS.
template<class Net >
Path< Net >	Aleph::find_aumenting_path_bfs (const Net &net, const typename Net::Flow_Type &min_slack)
	Find an augmenting path using BFS.
template<class Net , template< typename T > class Q>
SemiPath< Net >	Aleph::find_aumenting_semi_path (const Net &net, const typename Net::Flow_Type &slack)
	Find an augmenting semi-path using DFS or BFS based on Q.
template<class Net >
SemiPath< Net >	Aleph::find_aumenting_semi_path_dfs (const Net &net, const typename Net::Flow_Type &slack)
	Find an augmenting semi-path using DFS.
template<class Net >
SemiPath< Net >	Aleph::find_aumenting_semi_path_bfs (const Net &net, const typename Net::Flow_Type &slack)
	Find an augmenting semi-path using BFS.
template<class Net , template< typename T > class Q>
SemiPath< Net >	Aleph::find_decrementing_path (const Net &net, const typename Net::Flow_Type &slack)
	Find a decrementing semi-path using DFS or BFS based on Q.
template<class Net >
SemiPath< Net >	Aleph::find_decrementing_path_dfs (const Net &net, const typename Net::Flow_Type &slack)
	Find a decrementing semi-path using DFS.
template<class Net >
SemiPath< Net >	Aleph::find_decrementing_path_bfs (const Net &net, const typename Net::Flow_Type &slack)
	Find a decrementing semi-path using BFS.
template<class Net >
void	Aleph::create_residual_arc (const Net &net, PP_Res_Net< Net > &rnet, typename Net::Arc *a)
	Create residual arcs for a in the residual network.
template<class Net >
std::tuple< PP_Res_Net< Net >, typename PP_Res_Net< Net >::Node *, typename PP_Res_Net< Net >::Node * >	Aleph::preflow_create_residual_net (Net &net)
	Build the residual network for preflow-push algorithms.
template<class Rnet >
void	Aleph::update_flow (const Rnet &rnet)
	Propagate residual arc flows back to their original arcs.
template<class Net , template< class > class Find_Path>
Net::Flow_Type	Aleph::aumenting_path_maximum_flow (Net &net)
	Maximize flow using repeated augmenting-path searches.
template<class Net >
Net::Flow_Type	Aleph::ford_fulkerson_maximum_flow (Net &net)
	Maximize flow using the Ford-Fulkerson algorithm.
template<class Net >
Net::Flow_Type	Aleph::edmonds_karp_maximum_flow (Net &net)
	Maximize flow using the Edmonds-Karp algorithm.
template<class Net >
static bool	Aleph::is_node_active (const Net &net, typename Net::Node *p)
	Return true if p has excess flow in net.
template<class Rnet >
static bool	Aleph::is_node_active (typename Rnet::Node *p)
	Return true if residual node p has excess flow.
template<class Net >
static long &	Aleph::node_height (typename Net::Node *p)
	Access the height label stored in NODE_COUNTER.
template<class Net >
static void	Aleph::init_height_in_nodes (Net &net)
	Initialize node heights with BFS distance to the sink.
template<class Q_Type >
static void	Aleph::put_in_active_queue (Q_Type &q, typename Q_Type::Item_Type &p)
	Enqueue an active node if it is not already enqueued.
template<class Q_Type >
static Q_Type::Item_Type	Aleph::get_from_active_queue (Q_Type &q)
	Dequeue an active node and clear its queue mark.
template<class Q_Type >
static void	Aleph::remove_from_active_queue (Q_Type &q, typename Q_Type::Item_Type &p)
	Remove a node from the active queue and clear its queue mark.
template<class Net , class Q_Type >
Net::Flow_Type	Aleph::generic_preflow_vertex_push_maximum_flow (Net &net)
	Generic preflow-push maximum flow (vertex-oriented).
template<class Rnet >
void	Aleph::init_height_in_nodes (Rnet &rnet, typename Rnet::Node *sink)
	Initialize node heights in a residual network from sink.
template<class Net >
Net::Flow_Type	Aleph::fifo_preflow_maximum_flow (Net &net)
	Preflow-push maximum flow using a FIFO queue of active nodes.
template<class Net >
Net::Flow_Type	Aleph::heap_preflow_maximum_flow (Net &net)
	Preflow-push maximum flow using a height-ordered heap.
template<class Net >
Net::Flow_Type	Aleph::random_preflow_maximum_flow (Net &net)
	Preflow-push maximum flow using a random active-node queue.
template<class Net , template< class > class Maxflow>
Net::Flow_Type	Aleph::min_cut (Net &net, DynSetTree< typename Net::Node * > &vs, DynSetTree< typename Net::Node * > &vt, DynList< typename Net::Arc * > &cuts, DynList< typename Net::Arc * > &cutt)
	Compute max flow and the corresponding minimum cut.

Detailed Description

Network flow graph structures.

Defines graph structures for network flow problems with capacities, flows, and source/sink management.

Features

• Capacity and flow on arcs
• Source and sink node management
• Residual graph computation

See also

tpl_maxflow.H Maximum flow algorithms

tpl_netcost.H Minimum cost flow

Author

Leandro Rabindranath León

Definition in file tpl_net.H.