yog

-module(yog@multi@model).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/multi/model.gleam").
-export([new/1, directed/0, undirected/0, add_node/3, all_nodes/1, order/1, add_edge/4, has_edge/2, all_edge_ids/1, size/1, edges_between/3, successors/2, predecessors/2, out_degree/2, in_degree/2, to_simple_graph/2, to_simple_graph_min_edges/2, to_simple_graph_sum_edges/2, remove_node/2, remove_edge/2]).
-export_type([multi_graph/2]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

-type multi_graph(SOO, SOP) :: {multi_graph,
        yog@model:graph_type(),
        gleam@dict:dict(integer(), SOO),
        gleam@dict:dict(integer(), {integer(), integer(), SOP}),
        gleam@dict:dict(integer(), list(integer())),
        gleam@dict:dict(integer(), list(integer())),
        integer()}.

-file("src/yog/multi/model.gleam", 39).
?DOC(" Creates a new, empty multigraph of the given type.\n").
-spec new(yog@model:graph_type()) -> multi_graph(any(), any()).
new(Graph_type) ->
    {multi_graph, Graph_type, maps:new(), maps:new(), maps:new(), maps:new(), 0}.

-file("src/yog/multi/model.gleam", 51).
?DOC(" Creates a new, empty **directed** multigraph.\n").
-spec directed() -> multi_graph(any(), any()).
directed() ->
    new(directed).

-file("src/yog/multi/model.gleam", 56).
?DOC(" Creates a new, empty **undirected** multigraph.\n").
-spec undirected() -> multi_graph(any(), any()).
undirected() ->
    new(undirected).

-file("src/yog/multi/model.gleam", 66).
?DOC(
    " Adds a node with the given ID and data.\n"
    " If the node already exists its data is replaced (edges are unaffected).\n"
).
-spec add_node(multi_graph(SPC, SPD), integer(), SPC) -> multi_graph(SPC, SPD).
add_node(Graph, Id, Data) ->
    {multi_graph,
        erlang:element(2, Graph),
        gleam@dict:insert(erlang:element(3, Graph), Id, Data),
        erlang:element(4, Graph),
        erlang:element(5, Graph),
        erlang:element(6, Graph),
        erlang:element(7, Graph)}.

-file("src/yog/multi/model.gleam", 93).
?DOC(" Returns all node IDs in the graph.\n").
-spec all_nodes(multi_graph(any(), any())) -> list(integer()).
all_nodes(Graph) ->
    maps:keys(erlang:element(3, Graph)).

-file("src/yog/multi/model.gleam", 98).
?DOC(" Returns the number of nodes (graph order).\n").
-spec order(multi_graph(any(), any())) -> integer().
order(Graph) ->
    maps:size(erlang:element(3, Graph)).

-file("src/yog/multi/model.gleam", 121).
?DOC(
    " Adds an edge from `from` to `to` with the given data.\n"
    "\n"
    " Returns `#(updated_graph, new_edge_id)` so the caller can reference\n"
    " this specific edge later (e.g. for `remove_edge`).\n"
    "\n"
    " For undirected graphs a **single** `EdgeId` is issued and the reverse\n"
    " direction is indexed automatically — removing by ID removes both directions.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let graph = multi.directed()\n"
    " let #(graph, e1) = multi.add_edge(graph, from: 1, to: 2, with: \"flight\")\n"
    " let #(graph, e2) = multi.add_edge(graph, from: 1, to: 2, with: \"train\")\n"
    " // e1 != e2 — two independent parallel edges\n"
    " ```\n"
).
-spec add_edge(multi_graph(SPX, SPY), integer(), integer(), SPY) -> {multi_graph(SPX, SPY),
    integer()}.
add_edge(Graph, Src, Dst, Data) ->
    Eid = erlang:element(7, Graph),
    New_edges = gleam@dict:insert(
        erlang:element(4, Graph),
        Eid,
        {Src, Dst, Data}
    ),
    New_out = gleam@dict:upsert(
        erlang:element(5, Graph),
        Src,
        fun(Maybe) -> case Maybe of
                {some, Ids} ->
                    [Eid | Ids];

                none ->
                    [Eid]
            end end
    ),
    New_in = gleam@dict:upsert(
        erlang:element(6, Graph),
        Dst,
        fun(Maybe@1) -> case Maybe@1 of
                {some, Ids@1} ->
                    [Eid | Ids@1];

                none ->
                    [Eid]
            end end
    ),
    {New_out2, New_in2} = case erlang:element(2, Graph) of
        directed ->
            {New_out, New_in};

        undirected ->
            Rev_out = gleam@dict:upsert(
                New_out,
                Dst,
                fun(Maybe@2) -> case Maybe@2 of
                        {some, Ids@2} ->
                            [Eid | Ids@2];

                        none ->
                            [Eid]
                    end end
            ),
            Rev_in = gleam@dict:upsert(
                New_in,
                Src,
                fun(Maybe@3) -> case Maybe@3 of
                        {some, Ids@3} ->
                            [Eid | Ids@3];

                        none ->
                            [Eid]
                    end end
            ),
            {Rev_out, Rev_in}
    end,
    Updated = {multi_graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        New_edges,
        New_out2,
        New_in2,
        Eid + 1},
    {Updated, Eid}.

-file("src/yog/multi/model.gleam", 187).
?DOC(" Returns `True` if an edge with this ID exists in the graph.\n").
-spec has_edge(multi_graph(any(), any()), integer()) -> boolean().
has_edge(Graph, Edge_id) ->
    gleam@dict:has_key(erlang:element(4, Graph), Edge_id).

-file("src/yog/multi/model.gleam", 192).
?DOC(" Returns all edge IDs in the graph.\n").
-spec all_edge_ids(multi_graph(any(), any())) -> list(integer()).
all_edge_ids(Graph) ->
    maps:keys(erlang:element(4, Graph)).

-file("src/yog/multi/model.gleam", 198).
?DOC(
    " Returns the total number of edges (graph size).\n"
    " For undirected graphs each physical edge is counted once.\n"
).
-spec size(multi_graph(any(), any())) -> integer().
size(Graph) ->
    maps:size(erlang:element(4, Graph)).

-file("src/yog/multi/model.gleam", 204).
?DOC(
    " Returns all parallel edges between `from` and `to` as\n"
    " `List(#(EdgeId, edge_data))`.\n"
).
-spec edges_between(multi_graph(any(), SQX), integer(), integer()) -> list({integer(),
    SQX}).
edges_between(Graph, Src, Dst) ->
    _pipe = gleam_stdlib:map_get(erlang:element(5, Graph), Src),
    _pipe@1 = gleam@result:unwrap(_pipe, []),
    gleam@list:filter_map(
        _pipe@1,
        fun(Eid) -> case gleam_stdlib:map_get(erlang:element(4, Graph), Eid) of
                {ok, {_, D, Data}} when D =:= Dst ->
                    {ok, {Eid, Data}};

                _ ->
                    {error, nil}
            end end
    ).

-file("src/yog/multi/model.gleam", 224).
?DOC(" Returns all outgoing edges from `id` as `List(#(NodeId, EdgeId, e))`.\n").
-spec successors(multi_graph(any(), SRC), integer()) -> list({integer(),
    integer(),
    SRC}).
successors(Graph, Id) ->
    _pipe = gleam_stdlib:map_get(erlang:element(5, Graph), Id),
    _pipe@1 = gleam@result:unwrap(_pipe, []),
    gleam@list:filter_map(
        _pipe@1,
        fun(Eid) -> case gleam_stdlib:map_get(erlang:element(4, Graph), Eid) of
                {ok, {Src, Dst, Data}} when Src =:= Id ->
                    {ok, {Dst, Eid, Data}};

                {ok, {Src@1, Dst@1, Data@1}} when Dst@1 =:= Id ->
                    case erlang:element(2, Graph) of
                        undirected ->
                            {ok, {Src@1, Eid, Data@1}};

                        directed ->
                            {error, nil}
                    end;

                _ ->
                    {error, nil}
            end end
    ).

-file("src/yog/multi/model.gleam", 245).
?DOC(" Returns all incoming edges to `id` as `List(#(NodeId, EdgeId, e))`.\n").
-spec predecessors(multi_graph(any(), SRH), integer()) -> list({integer(),
    integer(),
    SRH}).
predecessors(Graph, Id) ->
    _pipe = gleam_stdlib:map_get(erlang:element(6, Graph), Id),
    _pipe@1 = gleam@result:unwrap(_pipe, []),
    gleam@list:filter_map(
        _pipe@1,
        fun(Eid) -> case gleam_stdlib:map_get(erlang:element(4, Graph), Eid) of
                {ok, {Src, Dst, Data}} when Dst =:= Id ->
                    {ok, {Src, Eid, Data}};

                {ok, {Src@1, Dst@1, Data@1}} when Src@1 =:= Id ->
                    case erlang:element(2, Graph) of
                        undirected ->
                            {ok, {Dst@1, Eid, Data@1}};

                        directed ->
                            {error, nil}
                    end;

                _ ->
                    {error, nil}
            end end
    ).

-file("src/yog/multi/model.gleam", 266).
?DOC(
    " Returns the out-degree of a node (number of outgoing edges).\n"
    " For undirected graphs this equals the total degree.\n"
).
-spec out_degree(multi_graph(any(), any()), integer()) -> integer().
out_degree(Graph, Id) ->
    erlang:length(successors(Graph, Id)).

-file("src/yog/multi/model.gleam", 271).
?DOC(" Returns the in-degree of a node (number of incoming edges).\n").
-spec in_degree(multi_graph(any(), any()), integer()) -> integer().
in_degree(Graph, Id) ->
    erlang:length(predecessors(Graph, Id)).

-file("src/yog/multi/model.gleam", 287).
?DOC(
    " Collapses the multigraph into a simple `yog/model.Graph` by combining\n"
    " parallel edges with `combine_fn(existing, new)`.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " // Keep minimum weight among parallel edges\n"
    " multi.to_simple_graph(mg, fn(a, b) { int.min(a, b) })\n"
    " ```\n"
).
-spec to_simple_graph(multi_graph(SRT, SRU), fun((SRU, SRU) -> SRU)) -> yog@model:graph(SRT, SRU).
to_simple_graph(Graph, Combine_fn) ->
    Base = gleam@dict:fold(
        erlang:element(3, Graph),
        yog@model:new(erlang:element(2, Graph)),
        fun(G, Id, Data) -> yog@model:add_node(G, Id, Data) end
    ),
    gleam@dict:fold(
        erlang:element(4, Graph),
        Base,
        fun(G@1, _, Edge) ->
            {Src, Dst, Data@1} = Edge,
            Result@1 = case yog@model:add_edge_with_combine(
                G@1,
                Src,
                Dst,
                Data@1,
                Combine_fn
            ) of
                {ok, Result} -> Result;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/multi/model"/utf8>>,
                                function => <<"to_simple_graph"/utf8>>,
                                line => 299,
                                value => _assert_fail,
                                start => 9067,
                                'end' => 9227,
                                pattern_start => 9078,
                                pattern_end => 9088})
            end,
            Result@1
        end
    ).

-file("src/yog/multi/model.gleam", 328).
?DOC(
    " Collapses the multigraph by keeping the **minimum** weight among parallel edges.\n"
    "\n"
    " **Use this for:** Shortest path, MST, and any algorithm where only the best\n"
    " (lowest cost) edge between two nodes matters.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " // Dijkstra's on multigraph\n"
    " graph\n"
    " |> multi.to_simple_graph_min_edges(int.compare)\n"
    " |> dijkstra.shortest_path(from: 1, to: 5, ...)\n"
    "\n"
    " // MST on multigraph  \n"
    " graph\n"
    " |> multi.to_simple_graph_min_edges(int.compare)\n"
    " |> mst.kruskal(with_compare: int.compare)\n"
    " ```\n"
).
-spec to_simple_graph_min_edges(
    multi_graph(SRZ, SSA),
    fun((SSA, SSA) -> gleam@order:order())
) -> yog@model:graph(SRZ, SSA).
to_simple_graph_min_edges(Graph, Compare) ->
    Min_fn = fun(A, B) -> case Compare(A, B) of
            gt ->
                B;

            _ ->
                A
        end end,
    to_simple_graph(Graph, Min_fn).

-file("src/yog/multi/model.gleam", 358).
?DOC(
    " Collapses the multigraph by **summing** weights of parallel edges.\n"
    "\n"
    " **Use this for:** Min-cut, max-cut, max-flow, and any algorithm where all\n"
    " parallel edges contribute additively to the total capacity/cost.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " // S-T min cut / max flow on multigraph\n"
    " graph\n"
    " |> multi.to_simple_graph_sum_edges(int.add)\n"
    " |> max_flow.edmonds_karp(from: source, to: sink, ...)\n"
    "\n"
    " // Global min cut on multigraph\n"
    " graph\n"
    " |> multi.to_simple_graph_sum_edges(int.add)\n"
    " |> min_cut.global_min_cut()\n"
    " ```\n"
).
-spec to_simple_graph_sum_edges(multi_graph(SSF, SSG), fun((SSG, SSG) -> SSG)) -> yog@model:graph(SSF, SSG).
to_simple_graph_sum_edges(Graph, Add) ->
    to_simple_graph(Graph, Add).

-file("src/yog/multi/model.gleam", 369).
-spec do_remove_edge(multi_graph(SSL, SSM), integer()) -> multi_graph(SSL, SSM).
do_remove_edge(Graph, Eid) ->
    case gleam_stdlib:map_get(erlang:element(4, Graph), Eid) of
        {error, _} ->
            Graph;

        {ok, {Src, Dst, _}} ->
            New_edges = gleam@dict:delete(erlang:element(4, Graph), Eid),
            Remove_id = fun(Maybe_ids) -> case Maybe_ids of
                    {some, Ids} ->
                        gleam@list:filter(Ids, fun(Id) -> Id /= Eid end);

                    none ->
                        []
                end end,
            New_out = gleam@dict:upsert(
                erlang:element(5, Graph),
                Src,
                Remove_id
            ),
            New_in = gleam@dict:upsert(erlang:element(6, Graph), Dst, Remove_id),
            {New_out2, New_in2} = case erlang:element(2, Graph) of
                directed ->
                    {New_out, New_in};

                undirected ->
                    Rev_out = gleam@dict:upsert(New_out, Dst, Remove_id),
                    Rev_in = gleam@dict:upsert(New_in, Src, Remove_id),
                    {Rev_out, Rev_in}
            end,
            {multi_graph,
                erlang:element(2, Graph),
                erlang:element(3, Graph),
                New_edges,
                New_out2,
                New_in2,
                erlang:element(7, Graph)}
    end.

-file("src/yog/multi/model.gleam", 75).
?DOC(" Removes a node and **all** edges connected to it.\n").
-spec remove_node(multi_graph(SPI, SPJ), integer()) -> multi_graph(SPI, SPJ).
remove_node(Graph, Id) ->
    Out_ids = begin
        _pipe = gleam_stdlib:map_get(erlang:element(5, Graph), Id),
        gleam@result:unwrap(_pipe, [])
    end,
    In_ids = begin
        _pipe@1 = gleam_stdlib:map_get(erlang:element(6, Graph), Id),
        gleam@result:unwrap(_pipe@1, [])
    end,
    Ids_to_remove = begin
        _pipe@2 = lists:append(Out_ids, In_ids),
        gleam@list:unique(_pipe@2)
    end,
    _pipe@3 = gleam@list:fold(
        Ids_to_remove,
        Graph,
        fun(G, Eid) -> do_remove_edge(G, Eid) end
    ),
    (fun(G@1) ->
        {multi_graph,
            erlang:element(2, G@1),
            gleam@dict:delete(erlang:element(3, G@1), Id),
            erlang:element(4, G@1),
            gleam@dict:delete(erlang:element(5, G@1), Id),
            gleam@dict:delete(erlang:element(6, G@1), Id),
            erlang:element(7, G@1)}
    end)(_pipe@3).

-file("src/yog/multi/model.gleam", 182).
?DOC(
    " Removes a single edge by its `EdgeId`.\n"
    " For undirected graphs both direction-index entries are removed.\n"
).
-spec remove_edge(multi_graph(SQD, SQE), integer()) -> multi_graph(SQD, SQE).
remove_edge(Graph, Edge_id) ->
    do_remove_edge(Graph, Edge_id).