yog - v3.1.0

yog/flow/network_simplex

Network Simplex algorithm for minimum cost flow.

Note: This implementation uses list-based data structures for the internal spanning tree representation. While algorithmically correct, random access and updates are O(n) rather than O(1). For large flow networks (1000+ nodes/edges), this may impact performance. Consider using alternative approaches for very large-scale problems:

  • Erlang FFI to :digraph or optimized C libraries
  • Specialized MCF solvers for production-scale optimization

See GitHub issue #TODO for potential future optimization to Dict-based arrays.

Types

EnteringEdge

</> 
pub type EnteringEdge =
  #(Int, Int, Int, Int)

FlowMap

</>

A flow vector assigning an amount of flow to each edge.

pub type FlowMap =
  List(#(Int, Int, Int))

MinCostFlowResult

</>

Returned when Network Simplex succeeds.

pub type MinCostFlowResult {
  MinCostFlowResult(cost: Int, flow: List(#(Int, Int, Int)))
}

Constructors 

  • MinCostFlowResult(cost: Int, flow: List(#(Int, Int, Int)))

    Arguments

    cost

    The optimal minimum cost of the flow routing.

    flow

    The flow amounts assigned to each edge to achieve the minimum cost.

NetworkSimplexError

</>

Errors that can occur during Network Simplex optimization.

pub type NetworkSimplexError {
  Infeasible
  Unbounded
  UnbalancedDemands
}

Constructors 

  • Infeasible

    The demands of the network cannot be satisfied given the edge capacities.

  • Unbounded

    The network contains a negative-cost cycle with infinite capacity.

  • UnbalancedDemands

    The sum of all node demands does not equal 0.

Values

min_cost_flow

</> 
pub fn min_cost_flow(
  graph: model.Graph(n, e),
  get_demand: fn(n) -> Int,
  get_capacity: fn(e) -> Int,
  get_cost: fn(e) -> Int,
) -> Result(MinCostFlowResult, NetworkSimplexError)

Solves the Minimum Cost Flow problem using the Network Simplex algorithm.

Returns either the optimal flow assignment or an error.

Time Complexity: O(V²E) worst case.

Parameters

  • graph: The flow network
  • get_demand: Node demand mapping
  • get_capacity: Edge capacity mapping
  • get_cost: Edge unit cost mapping
✨ Search Document