graph

-module(graph).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/graph.gleam").
-export([new/0, nodes/1, size/1, has_node/2, get_context/2, has_edge/3, insert_node/2, insert_directed_edge/4, insert_undirected_edge/4, remove_directed_edge/3, remove_undirected_edge/3, reverse_edges/1, to_directed/1, remove_node/2, match/2, match_any/1]).
-export_type([directed/0, undirected/0, graph/3, node_/1, context/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.

?MODULEDOC(
    "\n"
    " Here's a handy index you can use to browse through the various graph\n"
    " functions.\n"
    "\n"
    " | operation kind | functions |\n"
    " |---|---|\n"
    " | creating graphs | [`new`](#new) |\n"
    " | turning graphs into lists | [`nodes`](#nodes) |\n"
    " | querying a graph | [`size`](#size), [`has_node`](#has_node), [`has_edge`](#has_edge), [`get_context`](#get_context), [`match`](#match), [`match_any`](#match_any) |\n"
    " | adding/removing elements from a graph | [`insert_node`](#insert_node), [`insert_directed_edge`](#insert_directed_edge), [`insert_undirected_edge`](#insert_undirected_edge), [`remove_node`](#remove_node), [`remove_directed_edge`](#remove_directed_edge), [`remove_undirected_edge`](#remove_undirected_edge) |\n"
    " | transforming graphs | [`reverse_edges`](#reverse_edges), [`to_directed`](#to_directed) |\n"
    "\n"
).

-type directed() :: any().

-type undirected() :: any().

-opaque graph(DQP, DQQ, DQR) :: {graph,
        gleam@dict:dict(integer(), context(DQQ, DQR))} |
    {gleam_phantom, DQP}.

-type node_(DQS) :: {node, integer(), DQS}.

-type context(DQT, DQU) :: {context,
        gleam@dict:dict(integer(), DQU),
        node_(DQT),
        gleam@dict:dict(integer(), DQU)}.

-file("src/graph.gleam", 61).
?DOC(" Creates a new empty graph.\n").
-spec new() -> graph(any(), any(), any()).
new() ->
    {graph, maps:new()}.

-file("src/graph.gleam", 79).
?DOC(
    " Returns a list of all the nodes contained in the graph.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " assert [] == graph.new() |> graph.nodes\n"
    " assert [graph.Node(1, \"\")]\n"
    "   == graph.new()\n"
    "   |> graph.insert_node(graph.Node(1, \"a node\"))\n"
    "   |> graph.nodes\n"
    " ```\n"
).
-spec nodes(graph(any(), DRC, any())) -> list(node_(DRC)).
nodes(Graph) ->
    {graph, Graph@1} = Graph,
    gleam@dict:fold(
        Graph@1,
        [],
        fun(Acc, _, _use2) ->
            {context, _, Node, _} = _use2,
            [Node | Acc]
        end
    ).

-file("src/graph.gleam", 99).
?DOC(
    " Returns the number of nodes of the graph.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " assert 0 == graph.new() |> graph.size\n"
    " assert 1\n"
    "   == graph.new()\n"
    "   |> graph.insert_node(graph.Node(1, \"a node\"))\n"
    "   |> graph.size\n"
    " ```\n"
).
-spec size(graph(any(), any(), any())) -> integer().
size(Graph) ->
    {graph, Graph@1} = Graph,
    maps:size(Graph@1).

-file("src/graph.gleam", 117).
?DOC(
    " Returns `True` if the graph contains a node with the given id.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   graph.new()\n"
    "   |> graph.insert_node(graph.Node(1, \"a node\"))\n"
    "\n"
    " assert graph.has_node(graph, 1)\n"
    " assert !graph.has_node(graph, 2)\n"
    " ```\n"
).
-spec has_node(graph(any(), any(), any()), integer()) -> boolean().
has_node(Graph, Node_id) ->
    {graph, Graph@1} = Graph,
    gleam@dict:has_key(Graph@1, Node_id).

-file("src/graph.gleam", 162).
?DOC(
    " Returns the context associated with the node with the given id, if present.\n"
    " Otherwise returns `Error(Nil)`.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " assert Error(Nil) == graph.new() |> graph.get_context(of: 1)\n"
    " let assert Ok(graph.Context(node: Node(1, \"a node\"), ..)) =\n"
    "   graph.new()\n"
    "   |> graph.insert_node(graph.Node(1, \"a node\"))\n"
    "   |> graph.get_context(of: 1)\n"
    " ```\n"
).
-spec get_context(graph(any(), DSC, DSD), integer()) -> {ok, context(DSC, DSD)} |
    {error, nil}.
get_context(Graph, Node) ->
    {graph, Graph@1} = Graph,
    gleam_stdlib:map_get(Graph@1, Node).

-file("src/graph.gleam", 138).
?DOC(
    " Returns `True` if the graph has an edge connecting the two nodes with the\n"
    " given ids.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   graph.new()\n"
    "   |> graph.insert_node(graph.Node(1, \"a node\"))\n"
    "   |> graph.insert_node(graph.Node(2, \"another node\"))\n"
    "   |> graph.insert_directed_edge(\"label\", from: 1, to: 2)\n"
    "\n"
    " assert graph.has_edge(graph, from: 1, to: 2)\n"
    " assert !graph.has_edge(graph, from: 2, to: 1)\n"
    " ```\n"
).
-spec has_edge(graph(any(), any(), any()), integer(), integer()) -> boolean().
has_edge(Graph, Source, Destination) ->
    case get_context(Graph, Source) of
        {ok, {context, _, _, Outgoing}} ->
            gleam@dict:has_key(Outgoing, Destination);

        {error, _} ->
            false
    end.

-file("src/graph.gleam", 210).
?DOC(
    " Adds a node to the given graph.\n"
    " If the graph already contains a node with the same id, that will be replaced\n"
    " by the new one.\n"
    " The newly added node won't be connected to any existing node.\n"
).
-spec insert_node(graph(DTL, DTM, DTN), node_(DTM)) -> graph(DTL, DTM, DTN).
insert_node(Graph, Node) ->
    {graph, Graph@1} = Graph,
    Empty_context = {context, maps:new(), Node, maps:new()},
    New_graph = gleam@dict:insert(
        Graph@1,
        erlang:element(2, Node),
        Empty_context
    ),
    {graph, New_graph}.

-file("src/graph.gleam", 252).
-spec update_context(
    graph(DUL, DUM, DUN),
    integer(),
    fun((context(DUM, DUN)) -> context(DUM, DUN))
) -> graph(DUL, DUM, DUN).
update_context(Graph, Node, Fun) ->
    {graph, Graph@1} = Graph,
    case gleam_stdlib:map_get(Graph@1, Node) of
        {ok, Context} ->
            {graph, gleam@dict:insert(Graph@1, Node, Fun(Context))};

        {error, _} ->
            {graph, Graph@1}
    end.

-file("src/graph.gleam", 264).
-spec add_outgoing_edge(context(DUY, DUZ), integer(), DUZ) -> context(DUY, DUZ).
add_outgoing_edge(Context, Node, Label) ->
    {context, _, _, Outgoing} = Context,
    {context,
        erlang:element(2, Context),
        erlang:element(3, Context),
        gleam@dict:insert(Outgoing, Node, Label)}.

-file("src/graph.gleam", 273).
-spec remove_outgoing_edge(context(DVE, DVF), integer()) -> context(DVE, DVF).
remove_outgoing_edge(Context, Node) ->
    {context, _, _, Outgoing} = Context,
    {context,
        erlang:element(2, Context),
        erlang:element(3, Context),
        gleam@dict:delete(Outgoing, Node)}.

-file("src/graph.gleam", 281).
-spec add_incoming_edge(context(DVK, DVL), integer(), DVL) -> context(DVK, DVL).
add_incoming_edge(Context, Node, Label) ->
    {context, Incoming, _, _} = Context,
    {context,
        gleam@dict:insert(Incoming, Node, Label),
        erlang:element(3, Context),
        erlang:element(4, Context)}.

-file("src/graph.gleam", 222).
?DOC(" Adds an edge connecting two nodes in a directed graph.\n").
-spec insert_directed_edge(
    graph(directed(), DTV, DTW),
    DTW,
    integer(),
    integer()
) -> graph(directed(), DTV, DTW).
insert_directed_edge(Graph, Label, Source, Destination) ->
    _pipe = Graph,
    _pipe@1 = update_context(
        _pipe,
        Source,
        fun(_capture) -> add_outgoing_edge(_capture, Destination, Label) end
    ),
    update_context(
        _pipe@1,
        Destination,
        fun(_capture@1) -> add_incoming_edge(_capture@1, Source, Label) end
    ).

-file("src/graph.gleam", 235).
?DOC(" Adds an edge connecting two nodes in an undirected graph.\n").
-spec insert_undirected_edge(
    graph(undirected(), DUD, DUE),
    DUE,
    integer(),
    integer()
) -> graph(undirected(), DUD, DUE).
insert_undirected_edge(Graph, Label, One, Other) ->
    _pipe = Graph,
    _pipe@2 = update_context(
        _pipe,
        One,
        fun(Context) -> _pipe@1 = add_outgoing_edge(Context, Other, Label),
            add_incoming_edge(_pipe@1, Other, Label) end
    ),
    update_context(
        _pipe@2,
        Other,
        fun(Context@1) -> _pipe@3 = add_outgoing_edge(Context@1, One, Label),
            add_incoming_edge(_pipe@3, One, Label) end
    ).

-file("src/graph.gleam", 290).
-spec remove_incoming_edge(context(DVQ, DVR), integer()) -> context(DVQ, DVR).
remove_incoming_edge(Context, Node) ->
    {context, Incoming, _, _} = Context,
    {context,
        gleam@dict:delete(Incoming, Node),
        erlang:element(3, Context),
        erlang:element(4, Context)}.

-file("src/graph.gleam", 337).
?DOC(" Removes a directed edge connecting two nodes from a graph.\n").
-spec remove_directed_edge(graph(directed(), DXF, DXG), integer(), integer()) -> graph(directed(), DXF, DXG).
remove_directed_edge(Graph, Source, Destination) ->
    _pipe = Graph,
    _pipe@1 = update_context(
        _pipe,
        Source,
        fun(_capture) -> remove_outgoing_edge(_capture, Destination) end
    ),
    update_context(
        _pipe@1,
        Destination,
        fun(_capture@1) -> remove_incoming_edge(_capture@1, Source) end
    ).

-file("src/graph.gleam", 349).
?DOC(" Removes an undirected edge connecting two nodes from a graph.\n").
-spec remove_undirected_edge(
    graph(undirected(), DXN, DXO),
    integer(),
    integer()
) -> graph(undirected(), DXN, DXO).
remove_undirected_edge(Graph, One, Other) ->
    _pipe = Graph,
    _pipe@2 = update_context(
        _pipe,
        One,
        fun(Context) -> _pipe@1 = remove_outgoing_edge(Context, Other),
            remove_incoming_edge(_pipe@1, Other) end
    ),
    update_context(
        _pipe@2,
        Other,
        fun(Context@1) -> _pipe@3 = remove_outgoing_edge(Context@1, One),
            remove_incoming_edge(_pipe@3, One) end
    ).

-file("src/graph.gleam", 499).
?DOC(
    " Flips the direction of every edge in the graph. All incoming edges will\n"
    " become outgoing and vice-versa.\n"
).
-spec reverse_edges(graph(directed(), DXV, DXW)) -> graph(directed(), DXV, DXW).
reverse_edges(Graph) ->
    {graph, Graph@1} = Graph,
    {graph,
        begin
            gleam@dict:map_values(
                Graph@1,
                fun(_, Context) ->
                    {context, Incoming, Node, Outgoing} = Context,
                    {context, Outgoing, Node, Incoming}
                end
            )
        end}.

-file("src/graph.gleam", 518).
?DOC(
    " Turns an undirected graph into a directed one. Every edge connecting two\n"
    " nodes in the original graph will be considered as a pair of edges connecting\n"
    " the nodes going in both directions.\n"
).
-spec to_directed(graph(undirected(), DYD, DYE)) -> graph(directed(), DYD, DYE).
to_directed(Graph) ->
    {graph, Graph@1} = Graph,
    {graph, Graph@1}.

-file("src/graph.gleam", 527).
-spec dict_map_shared_keys(
    gleam@dict:dict(DYL, DYM),
    gleam@dict:dict(DYL, DYP),
    fun((DYM, DYP) -> DYM)
) -> gleam@dict:dict(DYL, DYM).
dict_map_shared_keys(One, Other, Fun) ->
    gleam@dict:fold(
        Other,
        One,
        fun(One@1, Key, Other_value) -> case gleam_stdlib:map_get(One@1, Key) of
                {ok, One_value} ->
                    gleam@dict:insert(One@1, Key, Fun(One_value, Other_value));

                {error, _} ->
                    One@1
            end end
    ).

-file("src/graph.gleam", 315).
-spec remove_incoming_occurrences(
    gleam@dict:dict(integer(), context(DWF, DWG)),
    integer(),
    gleam@dict:dict(integer(), any())
) -> gleam@dict:dict(integer(), context(DWF, DWG)).
remove_incoming_occurrences(Graph, Node, Nodes) ->
    dict_map_shared_keys(
        Graph,
        Nodes,
        fun(Context, _) ->
            {context, Incoming, _, _} = Context,
            {context,
                gleam@dict:delete(Incoming, Node),
                erlang:element(3, Context),
                erlang:element(4, Context)}
        end
    ).

-file("src/graph.gleam", 325).
-spec remove_outgoing_occurrences(
    gleam@dict:dict(integer(), context(DWS, DWT)),
    integer(),
    gleam@dict:dict(integer(), any())
) -> gleam@dict:dict(integer(), context(DWS, DWT)).
remove_outgoing_occurrences(Graph, Node, Nodes) ->
    dict_map_shared_keys(
        Graph,
        Nodes,
        fun(Context, _) ->
            {context, _, _, Outgoing} = Context,
            {context,
                erlang:element(2, Context),
                erlang:element(3, Context),
                gleam@dict:delete(Outgoing, Node)}
        end
    ).

-file("src/graph.gleam", 301).
?DOC(
    " Removes a node with the given id from the graph. If there's no node with the\n"
    " given id it does nothing.\n"
).
-spec remove_node(graph(DVW, DVX, DVY), integer()) -> graph(DVW, DVX, DVY).
remove_node(Graph, Node_id) ->
    case {Graph, get_context(Graph, Node_id)} of
        {_, {error, _}} ->
            Graph;

        {{graph, Graph@1}, {ok, {context, Incoming, _, Outgoing}}} ->
            _pipe = gleam@dict:delete(Graph@1, Node_id),
            _pipe@1 = remove_incoming_occurrences(_pipe, Node_id, Outgoing),
            _pipe@2 = remove_outgoing_occurrences(_pipe@1, Node_id, Incoming),
            {graph, _pipe@2}
    end.

-file("src/graph.gleam", 175).
?DOC(
    " If the graph contains a node with the given id, returns a tuple containing\n"
    " the context of that node (with all edges looping back to itself removed) and\n"
    " the \"remaining\" graph: that is, the original graph where that node has been\n"
    " removed.\n"
).
-spec match(graph(DSL, DSM, DSN), integer()) -> {ok,
        {context(DSM, DSN), graph(DSL, DSM, DSN)}} |
    {error, nil}.
match(Graph, Node_id) ->
    gleam@result:'try'(
        get_context(Graph, Node_id),
        fun(_use0) ->
            {context, Incoming, Node, Outgoing} = _use0,
            Rest = remove_node(Graph, Node_id),
            New_incoming = gleam@dict:delete(Incoming, Node_id),
            New_outgoing = gleam@dict:delete(Outgoing, Node_id),
            {ok, {{context, New_incoming, Node, New_outgoing}, Rest}}
        end
    ).

-file("src/graph.gleam", 193).
?DOC(
    " If the graph contains any node, returns a tuple containing a node of the\n"
    " graph (with all edges looping back to itself removed) and the \"remaining\"\n"
    " graph: that is, the original graph where that node has been removed.\n"
).
-spec match_any(graph(DSY, DSZ, DTA)) -> {ok,
        {context(DSZ, DTA), graph(DSY, DSZ, DTA)}} |
    {error, nil}.
match_any(Graph) ->
    {graph, Dict} = Graph,
    case maps:keys(Dict) of
        [] ->
            {error, nil};

        [First | _] ->
            match(Graph, First)
    end.