Current section
Files
Jump to
Current section
Files
src/yog@flow@network_simplex.erl
-module(yog@flow@network_simplex).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/flow/network_simplex.gleam").
-export([min_cost_flow/4]).
-export_type([min_cost_flow_result/0, network_simplex_error/0, omni_state/0]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" Network Simplex algorithm for minimum cost flow optimization.\n"
"\n"
" > [!CAUTION]\n"
" > **Experimental**: This module has not been extensively tested against edge cases,\n"
" > large networks, or adversarial inputs. The API and error behavior may change in\n"
" > future releases. Use with caution in production.\n"
"\n"
" This module solves the [minimum cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem):\n"
" find the cheapest way to send a given amount of flow through a network where\n"
" edges have both capacities and costs per unit of flow.\n"
"\n"
" ## Algorithm\n"
"\n"
" | Algorithm | Function | Complexity | Best For |\n"
" |-----------|----------|------------|----------|\n"
" | [Network Simplex](https://en.wikipedia.org/wiki/Network_simplex_algorithm) | `min_cost_flow/4` | O(V²E) practical | Large sparse networks |\n"
"\n"
" The Network Simplex is a specialized version of the [simplex algorithm](https://en.wikipedia.org/wiki/Simplex_algorithm)\n"
" for network flow problems. It maintains a spanning tree of basic edges and\n"
" iteratively pivots to improve the solution, similar to how the transportation\n"
" simplex works for assignment problems.\n"
"\n"
" ## Key Concepts\n"
"\n"
" - **Minimum Cost Flow**: Route flow to satisfy demands at minimum total cost\n"
" - **Node Demands**: Supply nodes (negative demand) and demand nodes (positive demand)\n"
" - **Edge Costs**: Price per unit of flow on each edge\n"
" - **Potentials (π)**: Dual variables for reduced cost computation\n"
" - **Reduced Costs**: Modified costs ensuring optimality conditions\n"
" - **Spanning Tree**: Basis for the simplex method on networks\n"
"\n"
" ## Problem Formulation\n"
"\n"
" Given:\n"
" - Graph G = (V, E) with capacities u(e) and costs c(e)\n"
" - Node demands b(v) where Σb(v) = 0 (conservation)\n"
"\n"
" Find flow f(e) that:\n"
" - Minimizes: Σ c(e) × f(e) (total cost)\n"
" - Subject to: 0 ≤ f(e) ≤ u(e) (capacity constraints)\n"
" - And: flow conservation at each node\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import yog\n"
" import yog/flow/network_simplex\n"
"\n"
" let graph =\n"
" yog.directed()\n"
" |> yog.add_node(1, 10) // supply 10\n"
" |> yog.add_node(2, 0) // transshipment\n"
" |> yog.add_node(3, -10) // demand 10\n"
" |> yog.add_edges([\n"
" #(1, 2, #(5, 2)), // capacity 5, cost 2\n"
" #(1, 3, #(10, 5)), // capacity 10, cost 5\n"
" #(2, 3, #(5, 1)), // capacity 5, cost 1\n"
" ])\n"
"\n"
" let result = network_simplex.min_cost_flow(\n"
" graph,\n"
" get_demand: fn(d) { d },\n"
" get_capacity: fn(e) { e.0 },\n"
" get_cost: fn(e) { e.1 },\n"
" )\n"
"\n"
" // result = Ok(MinCostFlowResult(cost: 40, flow: [#(1, 2, 5), #(1, 3, 5), #(2, 3, 5)]))\n"
" ```\n"
"\n"
" ## Use Cases\n"
"\n"
" - **Transportation planning**: Minimize shipping costs with vehicle capacities\n"
" - **Supply chain**: Optimize distribution from warehouses to retailers\n"
" - **Telecommunications**: Route calls at minimum cost with link capacities\n"
" - **Workforce scheduling**: Assign workers to shifts minimizing total cost\n"
" - **Circulation problems**: Fleet management and inventory routing\n"
"\n"
" ## Known Limitations\n"
"\n"
" - **List-based internals**: The spanning tree uses `List` for random access, making\n"
" reads and updates O(n) rather than O(1). Networks with 1000+ nodes/edges may\n"
" experience significantly reduced performance.\n"
" - **Cycle timeout**: If the algorithm fails to converge within `max(500, 5·E)` pivots,\n"
" it returns `Error(Timeout)`.\n"
" - **No convenience wrappers**: Unlike `yog/mst`, this module does not yet provide\n"
" pre-baked `*_int` or `*_record` variants; you must supply extractor functions.\n"
" - **Integer only**: Costs, capacities, and flows are all `Int`. Float weights are\n"
" not supported.\n"
" - **No Elixir equivalent**: `yog_ex` provides Successive Shortest Path for min-cost\n"
" flow instead of Network Simplex.\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Minimum-Cost Flow Problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem)\n"
" - [Wikipedia: Network Simplex Algorithm](https://en.wikipedia.org/wiki/Network_simplex_algorithm)\n"
" - [Network Flows - Ahuja, Magnanti, Orlin](https://www.pearson.com/en-us/subject-catalog/p/network-flows/P200000005792)\n"
" - [CP-Algorithms: Min-Cost Flow](https://cp-algorithms.com/graph/min_cost_flow.html)\n"
).
-type min_cost_flow_result() :: {min_cost_flow_result,
integer(),
list({integer(), integer(), integer()})}.
-type network_simplex_error() :: infeasible |
unbounded |
unbalanced_demands |
timeout.
-type omni_state() :: {omni_state,
integer(),
integer(),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
list(integer()),
integer(),
integer()}.
-file("src/yog/flow/network_simplex.gleam", 168).
-spec wget(list(PZX), integer()) -> PZX.
wget(Collection, Index) ->
Len = erlang:length(Collection),
Mod_idx = case Len of
0 -> 0;
Gleam@denominator -> Index rem Gleam@denominator
end,
True_idx = case Mod_idx < 0 of
true ->
Mod_idx + Len;
false ->
Mod_idx
end,
Val@1 = case begin
_pipe = Collection,
_pipe@1 = gleam@list:drop(_pipe, True_idx),
gleam@list:first(_pipe@1)
end of
{ok, Val} -> Val;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"wget"/utf8>>,
line => 175,
value => _assert_fail,
start => 6753,
'end' => 6823,
pattern_start => 6764,
pattern_end => 6771})
end,
Val@1.
-file("src/yog/flow/network_simplex.gleam", 179).
-spec wupdate(list(PZZ), integer(), fun((PZZ) -> PZZ)) -> list(PZZ).
wupdate(Collection, Index, Update) ->
Len = erlang:length(Collection),
Mod_idx = case Len of
0 -> 0;
Gleam@denominator -> Index rem Gleam@denominator
end,
True_idx = case Mod_idx < 0 of
true ->
Mod_idx + Len;
false ->
Mod_idx
end,
Before = gleam@list:take(Collection, True_idx),
After = gleam@list:drop(Collection, True_idx + 1),
Val@1 = case begin
_pipe = Collection,
_pipe@1 = gleam@list:drop(_pipe, True_idx),
gleam@list:first(_pipe@1)
end of
{ok, Val} -> Val;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"wupdate"/utf8>>,
line => 188,
value => _assert_fail,
start => 7160,
'end' => 7230,
pattern_start => 7171,
pattern_end => 7178})
end,
lists:append([Before, [Update(Val@1)], After]).
-file("src/yog/flow/network_simplex.gleam", 192).
-spec wassoc(list(QAC), integer(), QAC) -> list(QAC).
wassoc(Collection, Index, Value) ->
wupdate(Collection, Index, fun(_) -> Value end).
-file("src/yog/flow/network_simplex.gleam", 196).
-spec seq_do(integer(), integer(), list(integer())) -> list(integer()).
seq_do(Start, End, Acc) ->
case Start > End of
true ->
lists:reverse(Acc);
false ->
seq_do(Start + 1, End, [Start | Acc])
end.
-file("src/yog/flow/network_simplex.gleam", 203).
-spec seq(integer(), integer()) -> list(integer()).
seq(Start, End) ->
seq_do(Start, End, []).
-file("src/yog/flow/network_simplex.gleam", 249).
-spec extract(
yog@model:graph(QAO, QAP),
fun((QAO) -> integer()),
fun((QAP) -> integer()),
fun((QAP) -> integer())
) -> {ok, omni_state()} | {error, network_simplex_error()}.
extract(Graph, Get_demand, Get_capacity, Get_cost) ->
Nodes = yog@model:all_nodes(Graph),
Nc = erlang:length(Nodes),
_ = case Nc > 0 of
true ->
nil;
false ->
erlang:error(#{gleam_error => panic,
message => <<"Graph has no nodes"/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"extract"/utf8>>,
line => 259})
end,
_ = Nodes,
Node_indices = begin
_pipe = Nodes,
_pipe@1 = gleam@list:index_map(_pipe, fun(N, I) -> {N, I} end),
maps:from_list(_pipe@1)
end,
Demands = begin
_pipe@2 = Nodes,
gleam@list:map(
_pipe@2,
fun(N@1) ->
Ndata@1 = case gleam_stdlib:map_get(
erlang:element(3, Graph),
N@1
) of
{ok, Ndata} -> Ndata;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"extract"/utf8>>,
line => 272,
value => _assert_fail,
start => 9391,
'end' => 9438,
pattern_start => 9402,
pattern_end => 9411})
end,
Get_demand(Ndata@1)
end
)
end,
Total_demand = gleam@list:fold(Demands, 0, fun gleam@int:add/2),
case Total_demand =:= 0 of
false ->
{error, unbalanced_demands};
true ->
Edges = gleam@dict:fold(
erlang:element(4, Graph),
[],
fun(Acc_out, Src, Targets) ->
gleam@dict:fold(
Targets,
Acc_out,
fun(Acc_in, Dst, Weight) ->
[{Src, Dst, Weight} | Acc_in]
end
)
end
),
Ec = erlang:length(Edges),
Edge_sources = begin
_pipe@3 = Edges,
gleam@list:map(
_pipe@3,
fun(E_val) ->
{Src@1, _, _} = E_val,
Idx@1 = case gleam_stdlib:map_get(Node_indices, Src@1) of
{ok, Idx} -> Idx;
_assert_fail@1 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"extract"/utf8>>,
line => 295,
value => _assert_fail@1,
start => 10082,
'end' => 10130,
pattern_start => 10093,
pattern_end => 10100})
end,
Idx@1
end
)
end,
Edge_targets = begin
_pipe@4 = Edges,
gleam@list:map(
_pipe@4,
fun(E_val@1) ->
{_, Dst@1, _} = E_val@1,
Idx@3 = case gleam_stdlib:map_get(Node_indices, Dst@1) of
{ok, Idx@2} -> Idx@2;
_assert_fail@2 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"extract"/utf8>>,
line => 302,
value => _assert_fail@2,
start => 10276,
'end' => 10324,
pattern_start => 10287,
pattern_end => 10294})
end,
Idx@3
end
)
end,
Edge_costs = gleam@list:map(
Edges,
fun(E_val@2) ->
{_, _, W} = E_val@2,
Get_cost(W)
end
),
Edge_capacities = gleam@list:map(
Edges,
fun(E_val@3) ->
{_, _, W@1} = E_val@3,
Get_capacity(W@1)
end
),
Sum_cap = gleam@int:absolute_value(
gleam@list:fold(Edge_capacities, 0, fun gleam@int:add/2)
),
Sum_cost = gleam@list:fold(
Edge_costs,
0,
fun(Acc, C) -> Acc + gleam@int:absolute_value(C) end
),
Max_demand = gleam@list:fold(
Demands,
0,
fun(Acc@1, D) ->
gleam@int:max(Acc@1, gleam@int:absolute_value(D))
end
),
Inf = begin
_pipe@5 = (gleam@int:max(
gleam@int:max(Sum_cap, Sum_cost),
Max_demand
)
* 3),
gleam@int:max(_pipe@5, 1)
end,
Invalid_caps = gleam@list:any(
Edge_capacities,
fun(C@1) -> C@1 < 0 end
),
case Invalid_caps of
true ->
erlang:error(#{gleam_error => panic,
message => <<"Negative capacity encountered"/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"extract"/utf8>>,
line => 330});
false ->
nil
end,
{ok,
{omni_state,
Nc,
Ec,
Nodes,
Demands,
Edge_sources,
Edge_targets,
Edge_capacities,
Edge_costs,
[],
[],
[],
[],
[],
[],
[],
[],
0,
Inf}}
end.
-file("src/yog/flow/network_simplex.gleam", 359).
-spec add_super_source(omni_state()) -> omni_state().
add_super_source(Omni) ->
Nc = erlang:element(2, Omni),
Ss_edges = begin
_pipe = erlang:element(5, Omni),
gleam@list:index_map(_pipe, fun(D, P) -> case D > 0 of
true ->
{P, Nc};
false ->
{Nc, P}
end end)
end,
New_sources = lists:append(
[erlang:element(6, Omni),
gleam@list:map(Ss_edges, fun(E) -> erlang:element(1, E) end)]
),
New_targets = lists:append(
[erlang:element(7, Omni),
gleam@list:map(Ss_edges, fun(E@1) -> erlang:element(2, E@1) end)]
),
New_costs = lists:append(
[erlang:element(9, Omni),
gleam@list:repeat(erlang:element(19, Omni), Nc)]
),
New_caps = lists:append(
[erlang:element(8, Omni),
gleam@list:repeat(erlang:element(19, Omni), Nc)]
),
New_demands = lists:append(erlang:element(5, Omni), [0]),
{omni_state,
Nc + 1,
erlang:element(3, Omni) + Nc,
erlang:element(4, Omni),
New_demands,
New_sources,
New_targets,
New_caps,
New_costs,
erlang:element(10, Omni),
erlang:element(11, Omni),
erlang:element(12, Omni),
erlang:element(13, Omni),
erlang:element(14, Omni),
erlang:element(15, Omni),
erlang:element(16, Omni),
erlang:element(17, Omni),
erlang:element(18, Omni),
erlang:element(19, Omni)}.
-file("src/yog/flow/network_simplex.gleam", 397).
-spec init_spanning_tree(omni_state()) -> omni_state().
init_spanning_tree(Omni) ->
Nc = erlang:element(2, Omni),
Ec = erlang:element(3, Omni),
Old_nc = Nc - 1,
Old_ec = Ec - Old_nc,
Flows_base = gleam@list:repeat(0, Old_ec),
Flows_demands = gleam@list:map(
gleam@list:take(erlang:element(5, Omni), Old_nc),
fun gleam@int:absolute_value/1
),
Flows = lists:append([Flows_base, Flows_demands]),
Phis_base = gleam@list:map(
gleam@list:take(erlang:element(5, Omni), Old_nc),
fun(D) -> case D > 0 of
true ->
- erlang:element(19, Omni);
false ->
erlang:element(19, Omni)
end end
),
Phis = lists:append([Phis_base, [0]]),
Edges = lists:append([seq(Old_ec, Ec - 1), [-1]]),
Parents = lists:append([gleam@list:repeat(Old_nc, Old_nc), [-1]]),
Sizes = lists:append([gleam@list:repeat(1, Old_nc), [Nc]]),
Nexts = lists:append([seq(1, Old_nc - 1), [-1, 0]]),
Prevs = lists:append([[Old_nc], seq(0, Old_nc - 2), [-1]]),
Lasts = lists:append([seq(0, Old_nc - 1), [Old_nc - 1]]),
{omni_state,
erlang:element(2, Omni),
erlang:element(3, Omni),
erlang:element(4, Omni),
erlang:element(5, Omni),
erlang:element(6, Omni),
erlang:element(7, Omni),
erlang:element(8, Omni),
erlang:element(9, Omni),
Flows,
Phis,
Parents,
Edges,
Sizes,
Nexts,
Prevs,
Lasts,
erlang:element(18, Omni),
erlang:element(19, Omni)}.
-file("src/yog/flow/network_simplex.gleam", 454).
-spec reduced_cost(omni_state(), integer()) -> integer().
reduced_cost(Omni, I) ->
C = wget(erlang:element(9, Omni), I),
S = wget(erlang:element(6, Omni), I),
T = wget(erlang:element(7, Omni), I),
Phi_s = wget(erlang:element(11, Omni), S),
Phi_t = wget(erlang:element(11, Omni), T),
Base_cost = (C + Phi_s) - Phi_t,
case wget(erlang:element(10, Omni), I) =:= 0 of
true ->
Base_cost;
false ->
- Base_cost
end.
-file("src/yog/flow/network_simplex.gleam", 467).
-spec residual_capacity(omni_state(), integer(), integer()) -> integer().
residual_capacity(Omni, I, P) ->
S = wget(erlang:element(6, Omni), I),
U = wget(erlang:element(8, Omni), I),
F = wget(erlang:element(10, Omni), I),
case S =:= P of
true ->
U - F;
false ->
F
end.
-file("src/yog/flow/network_simplex.gleam", 481).
-spec do_find_apex(omni_state(), integer(), integer(), integer()) -> integer().
do_find_apex(Omni, P, Q, Max) ->
case (P =:= Q) orelse (Max =< 0) of
true ->
P;
false ->
Next_p = case wget(erlang:element(14, Omni), P) >= wget(
erlang:element(14, Omni),
Q
) of
true ->
P;
false ->
wget(erlang:element(12, Omni), P)
end,
Next_q = case wget(erlang:element(14, Omni), Q) >= wget(
erlang:element(14, Omni),
P
) of
true ->
Q;
false ->
wget(erlang:element(12, Omni), Q)
end,
Final_p = case (Next_p /= Next_q) andalso (wget(
erlang:element(14, Omni),
Next_p
)
=:= wget(erlang:element(14, Omni), Next_q)) of
true ->
wget(erlang:element(12, Omni), Next_p);
false ->
Next_p
end,
Final_q = case (Next_p /= Next_q) andalso (wget(
erlang:element(14, Omni),
Next_p
)
=:= wget(erlang:element(14, Omni), Next_q)) of
true ->
wget(erlang:element(12, Omni), Next_q);
false ->
Next_q
end,
do_find_apex(Omni, Final_p, Final_q, Max - 1)
end.
-file("src/yog/flow/network_simplex.gleam", 477).
-spec find_apex(omni_state(), integer(), integer()) -> integer().
find_apex(Omni, P, Q) ->
do_find_apex(Omni, P, Q, erlang:element(2, Omni)).
-file("src/yog/flow/network_simplex.gleam", 515).
-spec do_trace_path(
omni_state(),
integer(),
integer(),
list(integer()),
list(integer()),
integer()
) -> {list(integer()), list(integer())}.
do_trace_path(Omni, P, W, Wn, We, Max) ->
case (P =:= W) orelse (Max =< 0) of
true ->
{Wn, We};
false ->
Next_p = wget(erlang:element(12, Omni), P),
do_trace_path(
Omni,
Next_p,
W,
lists:append(Wn, [Next_p]),
lists:append(We, [wget(erlang:element(13, Omni), P)]),
Max - 1
)
end.
-file("src/yog/flow/network_simplex.gleam", 511).
-spec trace_path(omni_state(), integer(), integer()) -> {list(integer()),
list(integer())}.
trace_path(Omni, P, W) ->
do_trace_path(Omni, P, W, [P], [], erlang:element(2, Omni)).
-file("src/yog/flow/network_simplex.gleam", 539).
-spec find_cycle(omni_state(), integer(), integer(), integer()) -> {list(integer()),
list(integer()),
integer()}.
find_cycle(Omni, I, P, Q) ->
W = find_apex(Omni, P, Q),
{Wn_p, We_p} = trace_path(Omni, P, W),
Wn_p_rev = lists:reverse(Wn_p),
We_p_rev = lists:append(lists:reverse(We_p), [I]),
{Wn_q, We_q} = trace_path(Omni, Q, W),
Wn_q_rev = gleam@list:take(Wn_q, erlang:length(Wn_q) - 1),
{lists:append(Wn_p_rev, Wn_q_rev),
lists:append(We_p_rev, We_q),
erlang:length(Wn_p)}.
-file("src/yog/flow/network_simplex.gleam", 561).
-spec find_leaving_edge(omni_state(), list(integer()), list(integer())) -> {integer(),
integer()}.
find_leaving_edge(Omni, Wn, We) ->
Zipped = gleam@list:zip(We, Wn),
Min_edge = gleam@list:fold(
Zipped,
none,
fun(Acc, Ew) ->
{I, Cycle_source_node} = Ew,
Rc = residual_capacity(Omni, I, Cycle_source_node),
case Acc of
none ->
{some, {I, Rc}};
{some, {Min_i, Min_rc}} ->
case (Rc < Min_rc) orelse ((Rc =:= Min_rc) andalso (I < Min_i)) of
true ->
{some, {I, Rc}};
false ->
Acc
end
end
end
),
{J@1, Rc@2} = case Min_edge of
{some, {J, Rc@1}} -> {J, Rc@1};
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"find_leaving_edge"/utf8>>,
line => 582,
value => _assert_fail,
start => 17495,
'end' => 17538,
pattern_start => 17506,
pattern_end => 17527})
end,
{J@1, Rc@2}.
-file("src/yog/flow/network_simplex.gleam", 586).
-spec augment_flow(omni_state(), list(integer()), list(integer()), integer()) -> omni_state().
augment_flow(Omni, Wn, We, F) ->
Zipped = gleam@list:zip(We, Wn),
gleam@list:fold(
Zipped,
Omni,
fun(Acc, Ew) ->
{I, P} = Ew,
S = wget(erlang:element(6, Acc), I),
Update_amt = case S =:= P of
true ->
F;
false ->
- F
end,
{omni_state,
erlang:element(2, Acc),
erlang:element(3, Acc),
erlang:element(4, Acc),
erlang:element(5, Acc),
erlang:element(6, Acc),
erlang:element(7, Acc),
erlang:element(8, Acc),
erlang:element(9, Acc),
wupdate(
erlang:element(10, Acc),
I,
fun(Curr) -> Curr + Update_amt end
),
erlang:element(11, Acc),
erlang:element(12, Acc),
erlang:element(13, Acc),
erlang:element(14, Acc),
erlang:element(15, Acc),
erlang:element(16, Acc),
erlang:element(17, Acc),
erlang:element(18, Acc),
erlang:element(19, Acc)}
end
).
-file("src/yog/flow/network_simplex.gleam", 612).
-spec do_trace_subtree(omni_state(), integer(), integer(), integer()) -> list(integer()).
do_trace_subtree(Omni, P, L, Max) ->
case (P =:= L) orelse (Max =< 0) of
true ->
[P];
false ->
[P |
do_trace_subtree(
Omni,
wget(erlang:element(15, Omni), P),
L,
Max - 1
)]
end.
-file("src/yog/flow/network_simplex.gleam", 607).
-spec trace_subtree(omni_state(), integer()) -> list(integer()).
trace_subtree(Omni, P) ->
L = wget(erlang:element(17, Omni), P),
do_trace_subtree(Omni, P, L, erlang:element(2, Omni)).
-file("src/yog/flow/network_simplex.gleam", 646).
-spec do_remove_tree_edge_ancestors(
omni_state(),
integer(),
integer(),
integer(),
integer(),
integer()
) -> omni_state().
do_remove_tree_edge_ancestors(Omni, S, Size_t, Last_t, Prev_t, Max) ->
case (S < 0) orelse (Max =< 0) of
true ->
Omni;
false ->
Next_s = wget(erlang:element(12, Omni), S),
O1 = {omni_state,
erlang:element(2, Omni),
erlang:element(3, Omni),
erlang:element(4, Omni),
erlang:element(5, Omni),
erlang:element(6, Omni),
erlang:element(7, Omni),
erlang:element(8, Omni),
erlang:element(9, Omni),
erlang:element(10, Omni),
erlang:element(11, Omni),
erlang:element(12, Omni),
erlang:element(13, Omni),
wupdate(
erlang:element(14, Omni),
S,
fun(Curr) -> Curr - Size_t end
),
erlang:element(15, Omni),
erlang:element(16, Omni),
wupdate(
erlang:element(17, Omni),
S,
fun(Curr@1) -> case Curr@1 =:= Last_t of
true ->
Prev_t;
false ->
Curr@1
end end
),
erlang:element(18, Omni),
erlang:element(19, Omni)},
do_remove_tree_edge_ancestors(
O1,
Next_s,
Size_t,
Last_t,
Prev_t,
Max - 1
)
end.
-file("src/yog/flow/network_simplex.gleam", 619).
-spec remove_tree_edge(omni_state(), integer(), integer()) -> omni_state().
remove_tree_edge(Omni, S, T) ->
case S =:= wget(erlang:element(12, Omni), T) of
true -> nil;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/flow/network_simplex"/utf8>>,
function => <<"remove_tree_edge"/utf8>>,
line => 620,
value => _assert_fail,
start => 18379,
'end' => 18423,
pattern_start => 18390,
pattern_end => 18394})
end,
Size_t = wget(erlang:element(14, Omni), T),
Prev_t = wget(erlang:element(16, Omni), T),
Last_t = wget(erlang:element(17, Omni), T),
Next_last_t = wget(erlang:element(15, Omni), Last_t),
O1 = {omni_state,
erlang:element(2, Omni),
erlang:element(3, Omni),
erlang:element(4, Omni),
erlang:element(5, Omni),
erlang:element(6, Omni),
erlang:element(7, Omni),
erlang:element(8, Omni),
erlang:element(9, Omni),
erlang:element(10, Omni),
erlang:element(11, Omni),
wassoc(erlang:element(12, Omni), T, -1),
wassoc(erlang:element(13, Omni), T, -1),
erlang:element(14, Omni),
wassoc(erlang:element(15, Omni), Prev_t, Next_last_t),
wassoc(erlang:element(16, Omni), Next_last_t, Prev_t),
erlang:element(17, Omni),
erlang:element(18, Omni),
erlang:element(19, Omni)},
O2 = {omni_state,
erlang:element(2, O1),
erlang:element(3, O1),
erlang:element(4, O1),
erlang:element(5, O1),
erlang:element(6, O1),
erlang:element(7, O1),
erlang:element(8, O1),
erlang:element(9, O1),
erlang:element(10, O1),
erlang:element(11, O1),
erlang:element(12, O1),
erlang:element(13, O1),
erlang:element(14, O1),
wassoc(erlang:element(15, O1), Last_t, T),
wassoc(erlang:element(16, O1), T, Last_t),
erlang:element(17, O1),
erlang:element(18, O1),
erlang:element(19, O1)},
do_remove_tree_edge_ancestors(
O2,
S,
Size_t,
Last_t,
Prev_t,
erlang:element(2, Omni)
).
-file("src/yog/flow/network_simplex.gleam", 716).
-spec do_get_ancestors(omni_state(), integer(), list(integer()), integer()) -> {list(integer()),
integer()}.
do_get_ancestors(Omni, Q, Acc, Max) ->
case (Q < 0) orelse (Max =< 0) of
true ->
{Acc, Q};
false ->
do_get_ancestors(
Omni,
wget(erlang:element(12, Omni), Q),
lists:append(Acc, [Q]),
Max - 1
)
end.
-file("src/yog/flow/network_simplex.gleam", 674).
-spec make_root(omni_state(), integer()) -> omni_state().
make_root(Omni, Q) ->
{Ancestors, _} = do_get_ancestors(Omni, Q, [], erlang:element(2, Omni)),
Reversed_ancestors = lists:reverse(Ancestors),
Zipped = gleam@list:zip(
Reversed_ancestors,
gleam@list:drop(Reversed_ancestors, 1)
),
gleam@list:fold(
Zipped,
Omni,
fun(Acc, Pq) ->
{P, Q_curr} = Pq,
Size_p = wget(erlang:element(14, Acc), P),
Last_p = wget(erlang:element(17, Acc), P),
Prev_q = wget(erlang:element(16, Acc), Q_curr),
Last_q = wget(erlang:element(17, Acc), Q_curr),
Next_last_q = wget(erlang:element(15, Acc), Last_q),
Size_q = wget(erlang:element(14, Acc), Q_curr),
E_q = wget(erlang:element(13, Acc), Q_curr),
O1 = {omni_state,
erlang:element(2, Acc),
erlang:element(3, Acc),
erlang:element(4, Acc),
erlang:element(5, Acc),
erlang:element(6, Acc),
erlang:element(7, Acc),
erlang:element(8, Acc),
erlang:element(9, Acc),
erlang:element(10, Acc),
erlang:element(11, Acc),
wassoc(wassoc(erlang:element(12, Acc), P, Q_curr), Q_curr, -1),
wassoc(wassoc(erlang:element(13, Acc), P, E_q), Q_curr, -1),
wassoc(
wassoc(erlang:element(14, Acc), P, Size_p - Size_q),
Q_curr,
Size_p
),
wassoc(
wassoc(erlang:element(15, Acc), Prev_q, Next_last_q),
Last_q,
Q_curr
),
wassoc(
wassoc(erlang:element(16, Acc), Next_last_q, Prev_q),
Q_curr,
Last_q
),
erlang:element(17, Acc),
erlang:element(18, Acc),
erlang:element(19, Acc)},
O2 = case Last_p =:= Last_q of
true ->
{omni_state,
erlang:element(2, O1),
erlang:element(3, O1),
erlang:element(4, O1),
erlang:element(5, O1),
erlang:element(6, O1),
erlang:element(7, O1),
erlang:element(8, O1),
erlang:element(9, O1),
erlang:element(10, O1),
erlang:element(11, O1),
erlang:element(12, O1),
erlang:element(13, O1),
erlang:element(14, O1),
erlang:element(15, O1),
erlang:element(16, O1),
wassoc(erlang:element(17, O1), P, Prev_q),
erlang:element(18, O1),
erlang:element(19, O1)};
false ->
O1
end,
Last_p_new = wget(erlang:element(17, O2), P),
{omni_state,
erlang:element(2, O2),
erlang:element(3, O2),
erlang:element(4, O2),
erlang:element(5, O2),
erlang:element(6, O2),
erlang:element(7, O2),
erlang:element(8, O2),
erlang:element(9, O2),
erlang:element(10, O2),
erlang:element(11, O2),
erlang:element(12, O2),
erlang:element(13, O2),
erlang:element(14, O2),
wassoc(
wassoc(erlang:element(15, O2), Last_q, P),
Last_p_new,
Q_curr
),
wassoc(
wassoc(erlang:element(16, O2), P, Last_q),
Q_curr,
Last_p_new
),
wassoc(erlang:element(17, O2), Q_curr, Last_p_new),
erlang:element(18, O2),
erlang:element(19, O2)}
end
).
-file("src/yog/flow/network_simplex.gleam", 734).
-spec update_potentials(omni_state(), integer(), integer(), integer()) -> omni_state().
update_potentials(Omni, I, P, Q) ->
C = wget(erlang:element(9, Omni), I),
S = wget(erlang:element(6, Omni), I),
T = wget(erlang:element(7, Omni), I),
Phi_s = wget(erlang:element(11, Omni), S),
Phi_t = wget(erlang:element(11, Omni), T),
_ = wget(erlang:element(11, Omni), Q),
_ = wget(erlang:element(11, Omni), P),
Delta = case P =:= S of
true ->
(Phi_s + C) - Phi_t;
false ->
(Phi_t - C) - Phi_s
end,
Subtree_nodes = trace_subtree(Omni, Q),
gleam@list:fold(
Subtree_nodes,
Omni,
fun(Acc, N) ->
{omni_state,
erlang:element(2, Acc),
erlang:element(3, Acc),
erlang:element(4, Acc),
erlang:element(5, Acc),
erlang:element(6, Acc),
erlang:element(7, Acc),
erlang:element(8, Acc),
erlang:element(9, Acc),
erlang:element(10, Acc),
wupdate(
erlang:element(11, Acc),
N,
fun(Curr) -> Curr + Delta end
),
erlang:element(12, Acc),
erlang:element(13, Acc),
erlang:element(14, Acc),
erlang:element(15, Acc),
erlang:element(16, Acc),
erlang:element(17, Acc),
erlang:element(18, Acc),
erlang:element(19, Acc)}
end
).
-file("src/yog/flow/network_simplex.gleam", 764).
-spec find_entering_edges(omni_state()) -> gleam@option:option({integer(),
integer(),
integer(),
integer()}).
find_entering_edges(Omni) ->
Search_space = seq(0, erlang:element(3, Omni) - 1),
Result = gleam@list:fold_until(
Search_space,
none,
fun(Acc, Idx) ->
Offset = case erlang:element(3, Omni) of
0 -> 0;
Gleam@denominator -> (erlang:element(18, Omni) + Idx) rem Gleam@denominator
end,
Is_tree_edge = gleam@list:contains(erlang:element(13, Omni), Offset),
case Is_tree_edge of
true ->
{continue, Acc};
false ->
Rc = reduced_cost(Omni, Offset),
case Rc < 0 of
false ->
{continue, Acc};
true ->
S = wget(erlang:element(6, Omni), Offset),
T = wget(erlang:element(7, Omni), Offset),
F = wget(erlang:element(10, Omni), Offset),
{P, Q} = case F =:= 0 of
true ->
{S, T};
false ->
{T, S}
end,
{stop, {some, {Offset, P, Q, F}}}
end
end
end
),
case Result of
{some, {_, _, _, _}} ->
Result;
none ->
none
end.
-file("src/yog/flow/network_simplex.gleam", 859).
-spec do_add_tree_edge_ancestors(omni_state(), integer(), integer(), integer()) -> omni_state().
do_add_tree_edge_ancestors(Omni, P, Size_q, Max) ->
case (P < 0) orelse (Max =< 0) of
true ->
Omni;
false ->
O1 = {omni_state,
erlang:element(2, Omni),
erlang:element(3, Omni),
erlang:element(4, Omni),
erlang:element(5, Omni),
erlang:element(6, Omni),
erlang:element(7, Omni),
erlang:element(8, Omni),
erlang:element(9, Omni),
erlang:element(10, Omni),
erlang:element(11, Omni),
erlang:element(12, Omni),
erlang:element(13, Omni),
wupdate(
erlang:element(14, Omni),
P,
fun(Curr) -> Curr + Size_q end
),
erlang:element(15, Omni),
erlang:element(16, Omni),
erlang:element(17, Omni),
erlang:element(18, Omni),
erlang:element(19, Omni)},
do_add_tree_edge_ancestors(
O1,
wget(erlang:element(12, Omni), P),
Size_q,
Max - 1
)
end.
-file("src/yog/flow/network_simplex.gleam", 878).
-spec do_update_lasts_ancestors(
omni_state(),
integer(),
integer(),
integer(),
integer()
) -> omni_state().
do_update_lasts_ancestors(Omni, S, Last_s, Last_t, Max) ->
case (S < 0) orelse (Max =< 0) of
true ->
Omni;
false ->
O1 = {omni_state,
erlang:element(2, Omni),
erlang:element(3, Omni),
erlang:element(4, Omni),
erlang:element(5, Omni),
erlang:element(6, Omni),
erlang:element(7, Omni),
erlang:element(8, Omni),
erlang:element(9, Omni),
erlang:element(10, Omni),
erlang:element(11, Omni),
erlang:element(12, Omni),
erlang:element(13, Omni),
erlang:element(14, Omni),
erlang:element(15, Omni),
erlang:element(16, Omni),
wupdate(
erlang:element(17, Omni),
S,
fun(Curr) -> case Curr =:= Last_s of
true ->
Last_t;
false ->
Curr
end end
),
erlang:element(18, Omni),
erlang:element(19, Omni)},
Next_s = wget(erlang:element(12, O1), S),
do_update_lasts_ancestors(O1, Next_s, Last_s, Last_t, Max - 1)
end.
-file("src/yog/flow/network_simplex.gleam", 904).
-spec do_add_tree_edge_thread(omni_state(), integer(), integer()) -> omni_state().
do_add_tree_edge_thread(Omni, T, S) ->
Last_s = wget(erlang:element(17, Omni), S),
Next_last_s = wget(erlang:element(15, Omni), Last_s),
Last_t = wget(erlang:element(17, Omni), T),
O1 = do_update_lasts_ancestors(
Omni,
S,
Last_s,
Last_t,
erlang:element(2, Omni)
),
{omni_state,
erlang:element(2, O1),
erlang:element(3, O1),
erlang:element(4, O1),
erlang:element(5, O1),
erlang:element(6, O1),
erlang:element(7, O1),
erlang:element(8, O1),
erlang:element(9, O1),
erlang:element(10, O1),
erlang:element(11, O1),
erlang:element(12, O1),
erlang:element(13, O1),
erlang:element(14, O1),
wassoc(wassoc(erlang:element(15, O1), Last_s, T), Last_t, Next_last_s),
wassoc(wassoc(erlang:element(16, O1), T, Last_s), Next_last_s, Last_t),
erlang:element(17, O1),
erlang:element(18, O1),
erlang:element(19, O1)}.
-file("src/yog/flow/network_simplex.gleam", 806).
-spec pivot(omni_state(), {integer(), integer(), integer(), integer()}) -> omni_state().
pivot(Omni, Ee) ->
{I, P, Q, _} = Ee,
{Wn, We, Len_p} = find_cycle(Omni, I, P, Q),
{J, Rc} = find_leaving_edge(Omni, Wn, We),
J_on_p_side = begin
_pipe = gleam@list:take(We, Len_p),
gleam@list:contains(_pipe, J)
end,
{P_val, Q_val} = case J_on_p_side of
true ->
{Q, P};
false ->
{P, Q}
end,
Omni@1 = augment_flow(Omni, Wn, We, Rc),
case I =:= J of
true ->
Omni@1;
false ->
J_src = wget(erlang:element(6, Omni@1), J),
J_tgt = wget(erlang:element(7, Omni@1), J),
Leaving_child = case wget(erlang:element(12, Omni@1), J_src) =:= J_tgt of
true ->
J_src;
false ->
J_tgt
end,
Leaving_parent = wget(erlang:element(12, Omni@1), Leaving_child),
Omni@2 = remove_tree_edge(Omni@1, Leaving_parent, Leaving_child),
Omni@3 = make_root(Omni@2, Q_val),
Omni@4 = {omni_state,
erlang:element(2, Omni@3),
erlang:element(3, Omni@3),
erlang:element(4, Omni@3),
erlang:element(5, Omni@3),
erlang:element(6, Omni@3),
erlang:element(7, Omni@3),
erlang:element(8, Omni@3),
erlang:element(9, Omni@3),
erlang:element(10, Omni@3),
erlang:element(11, Omni@3),
wassoc(erlang:element(12, Omni@3), Q_val, P_val),
wassoc(erlang:element(13, Omni@3), Q_val, I),
erlang:element(14, Omni@3),
erlang:element(15, Omni@3),
erlang:element(16, Omni@3),
erlang:element(17, Omni@3),
erlang:element(18, Omni@3),
erlang:element(19, Omni@3)},
O1 = do_add_tree_edge_ancestors(
Omni@4,
P_val,
wget(erlang:element(14, Omni@4), Q_val),
erlang:element(2, Omni@4)
),
O2 = do_add_tree_edge_thread(O1, Q_val, P_val),
update_potentials(O2, I, P_val, Q_val)
end.
-file("src/yog/flow/network_simplex.gleam", 918).
-spec pivot_loop(omni_state(), integer()) -> {ok, omni_state()} |
{error, network_simplex_error()}.
pivot_loop(Omni, Max_iter) ->
case Max_iter =< 0 of
true ->
{error, timeout};
false ->
case find_entering_edges(Omni) of
none ->
{ok, Omni};
{some, Ee} ->
Next_omni = pivot(Omni, Ee),
pivot_loop(Next_omni, Max_iter - 1)
end
end.
-file("src/yog/flow/network_simplex.gleam", 936).
-spec summarize(omni_state(), yog@model:graph(any(), any())) -> {ok,
min_cost_flow_result()} |
{error, network_simplex_error()}.
summarize(Omni, _) ->
Onc = erlang:element(2, Omni) - 1,
Oec = erlang:element(3, Omni) - Onc,
Artificial_edges = seq(Oec, (Oec + Onc) - 1),
Is_infeasible = gleam@list:any(
Artificial_edges,
fun(I) -> wget(erlang:element(10, Omni), I) > 0 end
),
case Is_infeasible of
true ->
{error, infeasible};
false ->
Flow_list = seq(0, Oec - 1),
{Flow_map, Total_cost} = gleam@list:fold(
Flow_list,
{[], 0},
fun(Acc, I@1) ->
{Current_map, Current_cost} = Acc,
F = wget(erlang:element(10, Omni), I@1),
case F > 0 of
false ->
Acc;
true ->
S_idx = wget(erlang:element(6, Omni), I@1),
T_idx = wget(erlang:element(7, Omni), I@1),
C = wget(erlang:element(9, Omni), I@1),
S = wget(erlang:element(4, Omni), S_idx),
T = wget(erlang:element(4, Omni), T_idx),
{[{S, T, F} | Current_map], Current_cost + (F * C)}
end
end
),
{ok, {min_cost_flow_result, Total_cost, Flow_map}}
end.
-file("src/yog/flow/network_simplex.gleam", 223).
?DOC(
" Solves the Minimum Cost Flow problem using the Network Simplex algorithm.\n"
"\n"
" Returns either the optimal flow assignment or an error.\n"
"\n"
" **Time Complexity:** O(V²E) worst case.\n"
"\n"
" ## Parameters\n"
"\n"
" - `graph`: The flow network\n"
" - `get_demand`: Node demand mapping\n"
" - `get_capacity`: Edge capacity mapping\n"
" - `get_cost`: Edge unit cost mapping\n"
).
-spec min_cost_flow(
yog@model:graph(QAI, QAJ),
fun((QAI) -> integer()),
fun((QAJ) -> integer()),
fun((QAJ) -> integer())
) -> {ok, min_cost_flow_result()} | {error, network_simplex_error()}.
min_cost_flow(Graph, Get_demand, Get_capacity, Get_cost) ->
Extract_res = extract(Graph, Get_demand, Get_capacity, Get_cost),
case Extract_res of
{error, Err} ->
{error, Err};
{ok, Omni} ->
Max_pivots = gleam@int:max(500, erlang:element(3, Omni) * 5),
Ans = begin
_pipe = Omni,
_pipe@1 = add_super_source(_pipe),
_pipe@2 = init_spanning_tree(_pipe@1),
pivot_loop(_pipe@2, Max_pivots)
end,
case Ans of
{error, Err@1} ->
{error, Err@1};
{ok, Final_omni} ->
summarize(Final_omni, Graph)
end
end.