Network Simplex algorithm for minimum cost flow. More...

#include <tpl_netcost.H>

Collaboration diagram for Aleph::Network_Simplex< Net >:

Public Types
using	Node = typename Net::Node

using	Arc = typename Net::Arc

using	Flow_Type = typename Net::Flow_Type

using	Node_Info = Simplex_Node_Info< Flow_Type >

using	Arc_Info = Simplex_Arc_Info< Flow_Type >

Public Member Functions
	Network_Simplex (Net &network)
	Construct Network Simplex solver.

void	set_lower_bound (Arc *a, Flow_Type lower_bound)
	Set lower bound for an arc.

Flow_Type	get_lower_bound (Arc *a) const
	Get lower bound for an arc.

bool	is_at_lower_bound (Arc *a) const
	Check if arc flow is at lower bound.

bool	is_at_upper_bound (Arc *a) const
	Check if arc flow is at upper bound (capacity).

Flow_Type	residual_capacity (Arc *a) const
	Get residual capacity (room to increase flow).

Flow_Type	residual_lower (Arc *a) const
	Get residual lower (room to decrease flow).

size_t	run (Flow_Type unused=0)
	Execute Network Simplex algorithm.

size_t	get_num_pivots () const
	Return number of pivots performed in last run.

const NetworkSimplexStats &	get_stats () const noexcept
	Return execution statistics from last run.

void	print_stats () const
	Print execution statistics to stdout.

size_t	force_partial_arcs_into_tree ()
	Phase I: Force all partial-flow arcs into the spanning tree.

bool	is_valid_basic_solution () const
	Check if current solution is a valid basic feasible solution.

size_t	count_non_tree_partial_arcs () const
	Count arcs with partial flow not in tree.

bool	verify_tree_reduced_costs () const
	Verify that tree arcs have zero reduced cost.

bool	verify_tree_integrity () const
	Verify tree integrity - all parent_arcs should be Tree arcs.

void	print_diagnostics () const
	Print diagnostic information about current state.

Private Member Functions
Node_Info &	ninfo (Node *p)
	Get node info reference.

const Node_Info &	ninfo (Node *p) const
	Get node info const reference.

Arc_Info &	ainfo (Arc *a)
	Get arc info reference.

const Arc_Info &	ainfo (Arc *a) const
	Get arc info const reference.

Node *	parent (Node *p) const
	Get parent node.

Arc *	parent_arc (Node *p) const
	Get parent arc.

long	depth (Node *p) const
	Get depth.

Flow_Type	potential (Node *p) const
	Get potential.

bool	is_zero (Flow_Type x) const
	Check if value is effectively zero.

Flow_Type	reduced_cost (Arc *a) const
	Compute reduced cost of an arc.

void	init_structures ()
	Initialize data structures.

bool	is_partial_flow (Arc *a) const
	Check if arc has partial flow (strictly between bounds).

void	build_spanning_tree ()
	Build initial spanning tree from source.

Arc *	find_entering_arc ()
	Find entering arc using most negative reduced cost.

Node *	find_lca (Node u, Node v)
	Find the lowest common ancestor of two nodes.

bool	augment_and_find_leaving (Arc entering, Flow_Type &delta, Arc &leaving, bool &leaving_goes_lower)
	Augment flow around the cycle and find leaving arc.

void	pivot_tree (Arc entering, Arc leaving, bool leaving_goes_lower)
	Update tree structure after pivot.

Static Private Member Functions
static Flow_Type	eps ()
	Epsilon for floating-point comparisons.

Private Attributes
Net &	net

DynArray< Node_Info >	node_info

DynArray< Arc_Info >	arc_info

DynMapTree< Node *, size_t >	node_to_idx

DynMapTree< Arc *, size_t >	arc_to_idx

Node *	root = nullptr

size_t	num_pivots = 0

long	lca_mark = 0

NetworkSimplexStats	stats

bool	support_lower_bounds = false

Static Private Attributes
static constexpr Flow_Type	Inf = std::numeric_limits<Flow_Type>::max()

Detailed Description

template<FlowNetwork Net>
class Aleph::Network_Simplex< Net >

Network Simplex algorithm for minimum cost flow.

This class implements the Network Simplex algorithm, a specialized version of the Simplex method for minimum cost network flow problems. It maintains a spanning tree of basic arcs and iteratively improves the solution through pivoting operations.

Algorithm Overview

The algorithm uses a two-phase approach:

Phase I: Establish Basic Feasible Solution

After Ford-Fulkerson, some arcs may have partial flow (0 < flow < cap). For a valid basic solution, these arcs MUST be in the spanning tree (non-basic arcs must be at their bounds). Phase I forces all partial-flow arcs into the tree through pivots.

Phase II: Cost Optimization

Standard Network Simplex that iteratively:

Finds an entering arc with negative reduced cost
Identifies the cycle created by adding this arc
Determines the leaving arc (blocking arc in the cycle)
Performs the pivot: updates flows and tree structure

Implementation Notes

This implementation follows the presentation in Sedgewick's "Algorithms" with some adaptations for the Aleph-w graph representation and the addition of Phase I to handle the basic feasibility requirement.

The algorithm assumes the network already has a feasible flow (typically from a max-flow algorithm like Ford-Fulkerson). It then optimizes the cost while maintaining the same flow value.

Template Parameters

Net	Network type (must be Net_Cost_Graph or compatible).

See also: max_flow_min_cost_by_network_simplex; max_flow_min_cost_by_cycle_canceling

Definition at line 1042 of file tpl_netcost.H.

Member Typedef Documentation

◆ Arc

template<FlowNetwork Net>

using Aleph::Network_Simplex< Net >::Arc = typename Net::Arc

Definition at line 1046 of file tpl_netcost.H.

◆ Arc_Info

template<FlowNetwork Net>

using Aleph::Network_Simplex< Net >::Arc_Info = Simplex_Arc_Info<Flow_Type>

Definition at line 1049 of file tpl_netcost.H.

◆ Flow_Type

template<FlowNetwork Net>

using Aleph::Network_Simplex< Net >::Flow_Type = typename Net::Flow_Type

Definition at line 1047 of file tpl_netcost.H.

◆ Node

template<FlowNetwork Net>

using Aleph::Network_Simplex< Net >::Node = typename Net::Node

Definition at line 1045 of file tpl_netcost.H.

◆ Node_Info

template<FlowNetwork Net>

using Aleph::Network_Simplex< Net >::Node_Info = Simplex_Node_Info<Flow_Type>

Definition at line 1048 of file tpl_netcost.H.

Constructor & Destructor Documentation

◆ Network_Simplex()

template<FlowNetwork Net>

Aleph::Network_Simplex< Net >::Network_Simplex ( Net & network )

inlineexplicit

Construct Network Simplex solver.

Parameters

[in,out] network The network to optimize.

Definition at line 1767 of file tpl_netcost.H.

Member Function Documentation

◆ ainfo() [1/2]

template<FlowNetwork Net>

Arc_Info & Aleph::Network_Simplex< Net >::ainfo ( Arc * a )

inlineprivate

Get arc info reference.

Definition at line 1081 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::arc_info, Aleph::Network_Simplex< Net >::arc_to_idx, and Aleph::DynMapTree< Key, Data, Tree, Compare >::find().

◆ ainfo() [2/2]

template<FlowNetwork Net>

const Arc_Info & Aleph::Network_Simplex< Net >::ainfo ( Arc * a ) const

inlineprivate

Get arc info const reference.

Definition at line 1084 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::arc_info, Aleph::Network_Simplex< Net >::arc_to_idx, and Aleph::DynMapTree< Key, Data, Tree, Compare >::find().

◆ augment_and_find_leaving()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::augment_and_find_leaving	(	Arc *	entering,
		Flow_Type &	delta,
		Arc *&	leaving,
		bool &	leaving_goes_lower
	)

inlineprivate

Augment flow around the cycle and find leaving arc.

When entering arc is added, it creates a cycle. This function:

Finds the bottleneck (minimum slack) in the cycle
Updates flows around the cycle
Identifies the leaving arc

For a valid cycle that allows flow redistribution, we need arcs going in both directions (considering the entering arc). If all arcs in the cycle go in the same "global" direction (e.g., all from source towards sink), then we cannot redistribute flow without changing the total flow value.

Parameters

[in]	entering	The entering arc.
[out]	delta	Flow change amount.
[out]	leaving	The leaving arc (becomes non-basic).
[out]	leaving_goes_lower	True if leaving arc goes to lower bound.

Returns: true if a valid augmentation was performed.

Definition at line 1396 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::Simplex_Node_Info< Ftype >::arc_from_parent, Aleph::blossom_maximum_cardinality_matching(), Aleph::Network_Simplex< Net >::find_lca(), Aleph::Lower, Aleph::Network_Simplex< Net >::ninfo(), Aleph::Network_Simplex< Net >::parent(), Aleph::Network_Simplex< Net >::parent_arc(), and Aleph::Simplex_Arc_Info< Ftype >::state.

Referenced by Aleph::Network_Simplex< Net >::force_partial_arcs_into_tree(), and Aleph::Network_Simplex< Net >::run().

◆ build_spanning_tree()

template<FlowNetwork Net>

void Aleph::Network_Simplex< Net >::build_spanning_tree ( )

inlineprivate

Build initial spanning tree from source.

Creates a spanning tree rooted at the source node and computes initial potentials. Prioritizes arcs with partial flow.

Non-tree arcs are classified as Lower or Upper based on their current flow relative to capacity.

Definition at line 1163 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Simplex_Node_Info< Ftype >::depth, Aleph::Network_Simplex< Net >::depth(), Aleph::Network_Simplex< Net >::eps(), Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), Aleph::DynListQueue< T >::is_empty(), Aleph::Network_Simplex< Net >::is_partial_flow(), Aleph::Lower, Aleph::Network_Simplex< Net >::net, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::Network_Simplex< Net >::ninfo(), Aleph::Simplex_Node_Info< Ftype >::potential, Aleph::DynListQueue< T >::put(), Aleph::Network_Simplex< Net >::reduced_cost(), Aleph::Network_Simplex< Net >::root, Aleph::Simplex_Arc_Info< Ftype >::state, Aleph::Tree, Aleph::Upper, and GraphCommon< GT, Node, Arc >::vsize().

Referenced by Aleph::Network_Simplex< Net >::run().

◆ count_non_tree_partial_arcs()

template<FlowNetwork Net>

size_t Aleph::Network_Simplex< Net >::count_non_tree_partial_arcs ( ) const

inline

Count arcs with partial flow not in tree.

Definition at line 2060 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::count(), Aleph::Network_Simplex< Net >::is_partial_flow(), Aleph::Network_Simplex< Net >::net, and Aleph::Tree.

Referenced by Aleph::Network_Simplex< Net >::run().

◆ depth()

template<FlowNetwork Net>

long Aleph::Network_Simplex< Net >::depth ( Node * p ) const

inlineprivate

Get depth.

Definition at line 1093 of file tpl_netcost.H.

References Aleph::Simplex_Node_Info< Ftype >::depth, and Aleph::Network_Simplex< Net >::ninfo().

Referenced by Aleph::Network_Simplex< Net >::build_spanning_tree().

◆ eps()

template<FlowNetwork Net>

static Flow_Type Aleph::Network_Simplex< Net >::eps ( )

inlinestaticprivate

Epsilon for floating-point comparisons.

Definition at line 1066 of file tpl_netcost.H.

◆ find_entering_arc()

template<FlowNetwork Net>

Arc * Aleph::Network_Simplex< Net >::find_entering_arc ( )

inlineprivate

Find entering arc using most negative reduced cost.

Scans all non-tree arcs and selects the one with the largest violation of the optimality conditions:

Arc at Lower bound (flow=0): should have reduced_cost >= 0
Arc at Upper bound (flow=cap): should have reduced_cost <= 0

This implementation checks BOTH directions for each arc:

Forward direction: increase flow (requires flow < cap, benefits if rc < 0)
Backward direction: decrease flow (requires flow > 0, benefits if rc > 0)

This is essential for finding all negative cycles, including those that require reversing flow through arcs with flow > 0.

Returns: Entering arc, or nullptr if optimal.

Definition at line 1300 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Network_Simplex< Net >::eps(), Aleph::Lower, Aleph::Network_Simplex< Net >::net, Aleph::Network_Simplex< Net >::reduced_cost(), Aleph::Simplex_Arc_Info< Ftype >::state, Aleph::Tree, and Aleph::Upper.

Referenced by Aleph::Network_Simplex< Net >::run().

◆ find_lca()

template<FlowNetwork Net>

Node * Aleph::Network_Simplex< Net >::find_lca	(	Node *	u,
		Node *	v
	)

inlineprivate

Find the lowest common ancestor of two nodes.

Uses marking to efficiently find the LCA in O(d) where d is depth.

Parameters

[in]	u	First node.
[in]	v	Second node.

Returns: LCA of u and v.

Definition at line 1357 of file tpl_netcost.H.

References Aleph::and, Aleph::Network_Simplex< Net >::lca_mark, Aleph::Simplex_Node_Info< Ftype >::mark, Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Network_Simplex< Net >::parent().

Referenced by Aleph::Network_Simplex< Net >::augment_and_find_leaving().

◆ force_partial_arcs_into_tree()

template<FlowNetwork Net>

size_t Aleph::Network_Simplex< Net >::force_partial_arcs_into_tree ( )

inline

Phase I: Force all partial-flow arcs into the spanning tree.

For a valid basic feasible solution in Network Simplex, all arcs with flow strictly between bounds (0 < flow < cap) MUST be in the spanning tree. Non-basic arcs must be at their bounds.

This method identifies arcs with partial flow that are not in the tree and forces pivots to include them. Each pivot replaces one tree arc with the entering arc, maintaining exactly N-1 tree arcs.

Returns: Number of forced pivots performed.

Definition at line 1962 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::Network_Simplex< Net >::augment_and_find_leaving(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Network_Simplex< Net >::eps(), Aleph::Network_Simplex< Net >::is_partial_flow(), Aleph::Lower, Aleph::Network_Simplex< Net >::net, Aleph::Network_Simplex< Net >::pivot_tree(), Aleph::Simplex_Arc_Info< Ftype >::state, Aleph::Tree, and Aleph::Upper.

Referenced by Aleph::Network_Simplex< Net >::run().

◆ get_lower_bound()

template<FlowNetwork Net>

Flow_Type Aleph::Network_Simplex< Net >::get_lower_bound ( Arc * a ) const

inline

Get lower bound for an arc.

Parameters

[in] a Arc to query.

Returns: Lower bound value (0 if not set).

Definition at line 1790 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), and Aleph::Simplex_Arc_Info< Ftype >::lower_bound.

◆ get_num_pivots()

template<FlowNetwork Net>

size_t Aleph::Network_Simplex< Net >::get_num_pivots ( ) const

inline

Return number of pivots performed in last run.

Definition at line 1928 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::num_pivots.

◆ get_stats()

template<FlowNetwork Net>

const NetworkSimplexStats & Aleph::Network_Simplex< Net >::get_stats ( ) const

inlinenoexcept

Return execution statistics from last run.

Definition at line 1931 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::stats.

◆ init_structures()

template<FlowNetwork Net>

void Aleph::Network_Simplex< Net >::init_structures ( )

inlineprivate

Initialize data structures.

Definition at line 1119 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::arc_info, Aleph::Network_Simplex< Net >::arc_to_idx, Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::Lower, Aleph::Network_Simplex< Net >::net, Aleph::Network_Simplex< Net >::node_info, Aleph::Network_Simplex< Net >::node_to_idx, and Aleph::Simplex_Arc_Info< Ftype >::state.

Referenced by Aleph::Network_Simplex< Net >::run().

◆ is_at_lower_bound()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::is_at_lower_bound ( Arc * a ) const

inline

Check if arc flow is at lower bound.

Parameters

[in] a Arc to check.

Returns: true if flow equals lower bound.

Definition at line 1800 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::Network_Simplex< Net >::eps(), and Aleph::lower_bound().

◆ is_at_upper_bound()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::is_at_upper_bound ( Arc * a ) const

inline

Check if arc flow is at upper bound (capacity).

Parameters

[in] a Arc to check.

Returns: true if flow equals capacity.

Definition at line 1810 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::eps().

◆ is_partial_flow()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::is_partial_flow ( Arc * a ) const

inlineprivate

Check if arc has partial flow (strictly between bounds).

Definition at line 1150 of file tpl_netcost.H.

References Aleph::and, and Aleph::Network_Simplex< Net >::eps().

Referenced by Aleph::Network_Simplex< Net >::build_spanning_tree(), Aleph::Network_Simplex< Net >::count_non_tree_partial_arcs(), Aleph::Network_Simplex< Net >::force_partial_arcs_into_tree(), and Aleph::Network_Simplex< Net >::is_valid_basic_solution().

◆ is_valid_basic_solution()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::is_valid_basic_solution ( ) const

inline

Check if current solution is a valid basic feasible solution.

A valid BFS requires:

All tree arcs can have any flow
All non-tree arcs must be at their bounds (flow=0 or flow=cap)

Returns: true if valid BFS, false otherwise.

Definition at line 2044 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::Network_Simplex< Net >::is_partial_flow(), Aleph::Network_Simplex< Net >::net, and Aleph::Tree.

◆ is_zero()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::is_zero ( Flow_Type x ) const

inlineprivate

Check if value is effectively zero.

Definition at line 1099 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::eps().

◆ ninfo() [1/2]

template<FlowNetwork Net>

Node_Info & Aleph::Network_Simplex< Net >::ninfo ( Node * p )

inlineprivate

Get node info reference.

Definition at line 1075 of file tpl_netcost.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Network_Simplex< Net >::node_info, and Aleph::Network_Simplex< Net >::node_to_idx.

Referenced by Aleph::Network_Simplex< Net >::augment_and_find_leaving(), Aleph::Network_Simplex< Net >::build_spanning_tree(), Aleph::Network_Simplex< Net >::depth(), Aleph::Network_Simplex< Net >::find_lca(), Aleph::Network_Simplex< Net >::parent(), Aleph::Network_Simplex< Net >::parent_arc(), Aleph::Network_Simplex< Net >::pivot_tree(), Aleph::Network_Simplex< Net >::potential(), and Aleph::Network_Simplex< Net >::reduced_cost().

◆ ninfo() [2/2]

template<FlowNetwork Net>

const Node_Info & Aleph::Network_Simplex< Net >::ninfo ( Node * p ) const

inlineprivate

Get node info const reference.

Definition at line 1078 of file tpl_netcost.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Network_Simplex< Net >::node_info, and Aleph::Network_Simplex< Net >::node_to_idx.

◆ parent()

template<FlowNetwork Net>

Node * Aleph::Network_Simplex< Net >::parent ( Node * p ) const

inlineprivate

Get parent node.

Definition at line 1087 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Simplex_Node_Info< Ftype >::parent.

Referenced by Aleph::Network_Simplex< Net >::augment_and_find_leaving(), Aleph::Network_Simplex< Net >::find_lca(), and Aleph::Network_Simplex< Net >::pivot_tree().

◆ parent_arc()

template<FlowNetwork Net>

Arc * Aleph::Network_Simplex< Net >::parent_arc ( Node * p ) const

inlineprivate

Get parent arc.

Definition at line 1090 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Simplex_Node_Info< Ftype >::parent_arc.

Referenced by Aleph::Network_Simplex< Net >::augment_and_find_leaving(), Aleph::Network_Simplex< Net >::pivot_tree(), and Aleph::Network_Simplex< Net >::verify_tree_integrity().

◆ pivot_tree()

template<FlowNetwork Net>

void Aleph::Network_Simplex< Net >::pivot_tree	(	Arc *	entering,
		Arc *	leaving,
		bool	leaving_goes_lower
	)

inlineprivate

Update tree structure after pivot.

Replaces the leaving arc with the entering arc and updates parent pointers, depths, and potentials.

Parameters

[in]	entering	The entering arc.
[in]	leaving	The leaving arc.
[in]	leaving_goes_lower	True if leaving goes to lower bound.

Definition at line 1604 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::DynListQueue< T >::get(), LocateFunctions< Container, Type >::get_it(), Aleph::DynList< T >::insert(), Aleph::DynListQueue< T >::is_empty(), Aleph::Lower, Aleph::Network_Simplex< Net >::net, Aleph::next(), Aleph::Network_Simplex< Net >::ninfo(), Aleph::Network_Simplex< Net >::parent(), Aleph::Network_Simplex< Net >::parent_arc(), Aleph::DynListQueue< T >::put(), Aleph::Simplex_Arc_Info< Ftype >::state, Aleph::Tree, and Aleph::Upper.

Referenced by Aleph::Network_Simplex< Net >::force_partial_arcs_into_tree(), and Aleph::Network_Simplex< Net >::run().

◆ potential()

template<FlowNetwork Net>

Flow_Type Aleph::Network_Simplex< Net >::potential ( Node * p ) const

inlineprivate

Get potential.

Definition at line 1096 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Simplex_Node_Info< Ftype >::potential.

◆ print_diagnostics()

template<FlowNetwork Net>

void Aleph::Network_Simplex< Net >::print_diagnostics ( ) const

inline

Print diagnostic information about current state.

Definition at line 2117 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Network_Simplex< Net >::eps(), GraphCommon< GT, Node, Arc >::esize(), Aleph::Lower, Aleph::Network_Simplex< Net >::net, Aleph::Network_Simplex< Net >::reduced_cost(), Aleph::Simplex_Arc_Info< Ftype >::state, Aleph::Tree, Aleph::Upper, Aleph::Network_Simplex< Net >::verify_tree_reduced_costs(), and GraphCommon< GT, Node, Arc >::vsize().

◆ print_stats()

template<FlowNetwork Net>

void Aleph::Network_Simplex< Net >::print_stats ( ) const

inline

Print execution statistics to stdout.

Definition at line 1934 of file tpl_netcost.H.

◆ reduced_cost()

template<FlowNetwork Net>

Flow_Type Aleph::Network_Simplex< Net >::reduced_cost ( Arc * a ) const

inlineprivate

Compute reduced cost of an arc.

Reduced cost = c_ij - pi_i + pi_j For optimality: reduced cost >= 0 for arcs at lower bound (flow = 0) reduced cost <= 0 for arcs at upper bound (flow = cap)

Definition at line 1111 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Simplex_Node_Info< Ftype >::potential.

Referenced by Aleph::Network_Simplex< Net >::build_spanning_tree(), Aleph::Network_Simplex< Net >::find_entering_arc(), Aleph::Network_Simplex< Net >::print_diagnostics(), and Aleph::Network_Simplex< Net >::verify_tree_reduced_costs().

◆ residual_capacity()

template<FlowNetwork Net>

Flow_Type Aleph::Network_Simplex< Net >::residual_capacity ( Arc * a ) const

inline

Get residual capacity (room to increase flow).

Parameters

[in] a Arc to query.

Returns: Available capacity above current flow.

Definition at line 1820 of file tpl_netcost.H.

◆ residual_lower()

template<FlowNetwork Net>

Flow_Type Aleph::Network_Simplex< Net >::residual_lower ( Arc * a ) const

inline

Get residual lower (room to decrease flow).

Parameters

[in] a Arc to query.

Returns: Available decrease to lower bound.

Definition at line 1830 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), and Aleph::Simplex_Arc_Info< Ftype >::lower_bound.

◆ run()

template<FlowNetwork Net>

size_t Aleph::Network_Simplex< Net >::run ( Flow_Type unused = 0 )

inline

Execute Network Simplex algorithm.

Computes minimum cost flow. If the network already has a feasible flow (e.g., from Ford-Fulkerson), it optimizes starting from there.

Parameters

[in] unused Kept for API compatibility.

Returns: Number of pivots performed.

Definition at line 1845 of file tpl_netcost.H.

◆ set_lower_bound()

template<FlowNetwork Net>

void Aleph::Network_Simplex< Net >::set_lower_bound	(	Arc *	a,
		Flow_Type	lower_bound
	)

inline

Set lower bound for an arc.

Sets the minimum flow that must pass through an arc. Default lower bound is 0.

Parameters

[in]	a	Arc to set lower bound for.
[in]	lower_bound	Minimum flow value.

Note: Must be called before run().

Definition at line 1779 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::lower_bound(), Aleph::Simplex_Arc_Info< Ftype >::lower_bound, and Aleph::Network_Simplex< Net >::support_lower_bounds.

◆ verify_tree_integrity()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::verify_tree_integrity ( ) const

inline

Verify tree integrity - all parent_arcs should be Tree arcs.

Returns: true if tree structure is consistent.

Definition at line 2098 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Network_Simplex< Net >::net, Aleph::Network_Simplex< Net >::parent_arc(), Aleph::Network_Simplex< Net >::root, and Aleph::Tree.

◆ verify_tree_reduced_costs()

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::verify_tree_reduced_costs ( ) const

inline

Verify that tree arcs have zero reduced cost.

In a valid basic solution, all tree arcs must have reduced cost = 0. This is a consistency check for the potential values.

Returns: true if all tree arcs have rc=0, false otherwise.

Definition at line 2079 of file tpl_netcost.H.

References Aleph::Network_Simplex< Net >::ainfo(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Network_Simplex< Net >::eps(), Aleph::Network_Simplex< Net >::net, Aleph::Network_Simplex< Net >::reduced_cost(), and Aleph::Tree.

Referenced by Aleph::Network_Simplex< Net >::print_diagnostics().

Member Data Documentation

◆ arc_info

template<FlowNetwork Net>

DynArray<Arc_Info> Aleph::Network_Simplex< Net >::arc_info

private

Definition at line 1054 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::ainfo(), Aleph::Network_Simplex< Net >::ainfo(), and Aleph::Network_Simplex< Net >::init_structures().

◆ arc_to_idx

template<FlowNetwork Net>

DynMapTree<Arc *, size_t> Aleph::Network_Simplex< Net >::arc_to_idx

private

Definition at line 1056 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::ainfo(), Aleph::Network_Simplex< Net >::ainfo(), and Aleph::Network_Simplex< Net >::init_structures().

◆ Inf

template<FlowNetwork Net>

constexpr Flow_Type Aleph::Network_Simplex< Net >::Inf = std::numeric_limits<Flow_Type>::max()

staticconstexprprivate

Definition at line 1063 of file tpl_netcost.H.

◆ lca_mark

template<FlowNetwork Net>

long Aleph::Network_Simplex< Net >::lca_mark = 0

private

Definition at line 1059 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::find_lca().

◆ net

template<FlowNetwork Net>

Net& Aleph::Network_Simplex< Net >::net

private

Definition at line 1052 of file tpl_netcost.H.

◆ node_info

template<FlowNetwork Net>

DynArray<Node_Info> Aleph::Network_Simplex< Net >::node_info

private

Definition at line 1053 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::init_structures(), Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Network_Simplex< Net >::ninfo().

◆ node_to_idx

template<FlowNetwork Net>

DynMapTree<Node *, size_t> Aleph::Network_Simplex< Net >::node_to_idx

private

Definition at line 1055 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::init_structures(), Aleph::Network_Simplex< Net >::ninfo(), and Aleph::Network_Simplex< Net >::ninfo().

◆ num_pivots

template<FlowNetwork Net>

size_t Aleph::Network_Simplex< Net >::num_pivots = 0

private

Definition at line 1058 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::get_num_pivots(), and Aleph::Network_Simplex< Net >::run().

◆ root

template<FlowNetwork Net>

Node* Aleph::Network_Simplex< Net >::root = nullptr

private

Definition at line 1057 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::build_spanning_tree(), and Aleph::Network_Simplex< Net >::verify_tree_integrity().

◆ stats

template<FlowNetwork Net>

NetworkSimplexStats Aleph::Network_Simplex< Net >::stats

mutableprivate

Definition at line 1060 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::get_stats(), Aleph::Network_Simplex< Net >::print_stats(), and Aleph::Network_Simplex< Net >::run().

◆ support_lower_bounds

template<FlowNetwork Net>

bool Aleph::Network_Simplex< Net >::support_lower_bounds = false

private

Definition at line 1061 of file tpl_netcost.H.

Referenced by Aleph::Network_Simplex< Net >::set_lower_bound().

The documentation for this class was generated from the following file:

tpl_netcost.H

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Algorithm Overview

Phase I: Establish Basic Feasible Solution

Phase II: Cost Optimization

Implementation Notes

Member Typedef Documentation

◆ Arc

◆ Arc_Info

◆ Flow_Type

◆ Node

◆ Node_Info

Constructor & Destructor Documentation

◆ Network_Simplex()

Member Function Documentation

◆ ainfo() [1/2]

◆ ainfo() [2/2]

◆ augment_and_find_leaving()

◆ build_spanning_tree()

◆ count_non_tree_partial_arcs()

◆ depth()

◆ eps()

◆ find_entering_arc()

◆ find_lca()

◆ force_partial_arcs_into_tree()

◆ get_lower_bound()

◆ get_num_pivots()

◆ get_stats()

◆ init_structures()

◆ is_at_lower_bound()

◆ is_at_upper_bound()

◆ is_partial_flow()

◆ is_valid_basic_solution()

◆ is_zero()

◆ ninfo() [1/2]

◆ ninfo() [2/2]

◆ parent()

◆ parent_arc()

◆ pivot_tree()

◆ potential()

◆ print_diagnostics()

◆ print_stats()

◆ reduced_cost()

◆ residual_capacity()

◆ residual_lower()

◆ run()

◆ set_lower_bound()

◆ verify_tree_integrity()

◆ verify_tree_reduced_costs()

Member Data Documentation

◆ arc_info

◆ arc_to_idx

◆ Inf

◆ lca_mark

◆ net

◆ node_info

◆ node_to_idx

◆ num_pivots

◆ root

◆ stats

◆ support_lower_bounds