yog

-module(yog@multi@traversal).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/multi/traversal.gleam").
-export([bfs/2, fold_walk/4, dfs/2]).
-export_type([walk_control/0, walk_metadata/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.

-type walk_control() :: continue | stop | halt.

-type walk_metadata() :: {walk_metadata,
        integer(),
        gleam@option:option({integer(), integer()})}.

-file("src/yog/multi/traversal.gleam", 140).
-spec do_bfs(
    yog@multi@model:multi_graph(any(), any()),
    list(integer()),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    list(integer())
) -> list(integer()).
do_bfs(Graph, Queue, Visited_nodes, Used_edges, Acc) ->
    case Queue of
        [] ->
            lists:reverse(Acc);

        [Current | Rest_queue] ->
            {New_nodes, New_edges, Next_queue} = begin
                _pipe = yog@multi@model:successors(Graph, Current),
                gleam@list:fold(
                    _pipe,
                    {Visited_nodes, Used_edges, Rest_queue},
                    fun(State, Succ) ->
                        {Vn, Ue, Q} = State,
                        {Dst, Eid, _} = Succ,
                        case gleam@set:contains(Ue, Eid) orelse gleam@set:contains(
                            Vn,
                            Dst
                        ) of
                            true ->
                                State;

                            false ->
                                {gleam@set:insert(Vn, Dst),
                                    gleam@set:insert(Ue, Eid),
                                    [Dst | Q]}
                        end
                    end
                )
            end,
            do_bfs(Graph, Next_queue, New_nodes, New_edges, [Current | Acc])
    end.

-file("src/yog/multi/traversal.gleam", 37).
?DOC(
    " Performs a Breadth-First Search from `source`, returning visited node IDs\n"
    " in BFS order.\n"
    "\n"
    " Unlike simple-graph BFS, this traversal uses edge IDs to correctly handle\n"
    " parallel edges — each **edge** is traversed at most once, but a node may be\n"
    " reached via multiple edges (the first visit wins for ordering purposes).\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec bfs(yog@multi@model:multi_graph(any(), any()), integer()) -> list(integer()).
bfs(Graph, Source) ->
    do_bfs(Graph, [Source], gleam@set:from_list([Source]), gleam@set:new(), []).

-file("src/yog/multi/traversal.gleam", 253).
-spec do_fold_walk_bfs(
    yog@multi@model:multi_graph(any(), any()),
    list({integer(), walk_metadata()}),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    TSO,
    fun((TSO, integer(), walk_metadata()) -> {walk_control(), TSO})
) -> TSO.
do_fold_walk_bfs(Graph, Queue, Visited_nodes, Used_edges, Acc, Folder) ->
    case Queue of
        [] ->
            Acc;

        [{Node_id, Metadata} | Rest_queue] ->
            case gleam@set:contains(Visited_nodes, Node_id) of
                true ->
                    do_fold_walk_bfs(
                        Graph,
                        Rest_queue,
                        Visited_nodes,
                        Used_edges,
                        Acc,
                        Folder
                    );

                false ->
                    {Control, New_acc} = Folder(Acc, Node_id, Metadata),
                    New_visited = gleam@set:insert(Visited_nodes, Node_id),
                    case Control of
                        halt ->
                            New_acc;

                        stop ->
                            do_fold_walk_bfs(
                                Graph,
                                Rest_queue,
                                New_visited,
                                Used_edges,
                                New_acc,
                                Folder
                            );

                        continue ->
                            {Next_queue, New_used_edges} = begin
                                _pipe = yog@multi@model:successors(
                                    Graph,
                                    Node_id
                                ),
                                gleam@list:fold(
                                    _pipe,
                                    {Rest_queue, Used_edges},
                                    fun(State, Succ) ->
                                        {Q, Ue} = State,
                                        {Dst, Eid, _} = Succ,
                                        case gleam@set:contains(Ue, Eid) of
                                            true ->
                                                State;

                                            false ->
                                                Next_meta = {walk_metadata,
                                                    erlang:element(2, Metadata)
                                                    + 1,
                                                    {some, {Node_id, Eid}}},
                                                {[{Dst, Next_meta} | Q],
                                                    gleam@set:insert(Ue, Eid)}
                                        end
                                    end
                                )
                            end,
                            do_fold_walk_bfs(
                                Graph,
                                Next_queue,
                                New_visited,
                                New_used_edges,
                                New_acc,
                                Folder
                            )
                    end
            end
    end.

-file("src/yog/multi/traversal.gleam", 118).
?DOC(
    " Folds over nodes during multigraph traversal, accumulating state with metadata.\n"
    "\n"
    " This function combines traversal with state accumulation, providing metadata\n"
    " about each visited node including which specific edge was used to reach it.\n"
    " The folder function controls the traversal flow:\n"
    "\n"
    " - `Continue`: Explore successors of the current node normally\n"
    " - `Stop`: Skip successors of this node, but continue processing other queued nodes\n"
    " - `Halt`: Stop the entire traversal immediately and return the accumulator\n"
    "\n"
    " **For multigraphs**: The metadata includes the specific `EdgeId` used to reach\n"
    " each node, which is important when parallel edges exist.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `folder`: Called for each visited node with (accumulator, node_id, metadata).\n"
    "   Returns `#(WalkControl, new_accumulator)`.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " import gleam/dict\n"
    " import yog/multi/traversal.{Continue, Halt, Stop, WalkMetadata}\n"
    "\n"
    " // Build a parent map tracking which edge led to each node\n"
    " let parents = traversal.fold_walk(\n"
    "   over: graph,\n"
    "   from: start,\n"
    "   initial: dict.new(),\n"
    "   with: fn(acc, node_id, meta) {\n"
    "     let new_acc = case meta.parent {\n"
    "       Some(#(parent_node, edge_id)) ->\n"
    "         dict.insert(acc, node_id, #(parent_node, edge_id))\n"
    "       None -> acc\n"
    "     }\n"
    "     #(Continue, new_acc)\n"
    "   }\n"
    " )\n"
    "\n"
    " // Find all nodes within distance 3\n"
    " let nearby = traversal.fold_walk(\n"
    "   over: graph,\n"
    "   from: start,\n"
    "   initial: [],\n"
    "   with: fn(acc, node_id, meta) {\n"
    "     case meta.depth <= 3 {\n"
    "       True -> #(Continue, [node_id, ..acc])\n"
    "       False -> #(Stop, acc)  // Don't explore beyond depth 3\n"
    "     }\n"
    "   }\n"
    " )\n"
    "\n"
    " // Collect all edges in the traversal path\n"
    " let path_edges = traversal.fold_walk(\n"
    "   over: graph,\n"
    "   from: start,\n"
    "   initial: [],\n"
    "   with: fn(acc, _node_id, meta) {\n"
    "     let new_acc = case meta.parent {\n"
    "       Some(#(_, edge_id)) -> [edge_id, ..acc]\n"
    "       None -> acc\n"
    "     }\n"
    "     #(Continue, new_acc)\n"
    "   }\n"
    " )\n"
    " ```\n"
).
-spec fold_walk(
    yog@multi@model:multi_graph(any(), any()),
    integer(),
    TQM,
    fun((TQM, integer(), walk_metadata()) -> {walk_control(), TQM})
) -> TQM.
fold_walk(Graph, Start, Acc, Folder) ->
    Start_metadata = {walk_metadata, 0, none},
    do_fold_walk_bfs(
        Graph,
        [{Start, Start_metadata}],
        gleam@set:new(),
        gleam@set:new(),
        Acc,
        Folder
    ).

-file("src/yog/multi/traversal.gleam", 210).
-spec process_successors_cps(
    yog@multi@model:multi_graph(any(), TRT),
    list({integer(), integer(), TRT}),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    list(integer()),
    fun((gleam@set:set(integer()), gleam@set:set(integer()), list(integer())) -> {gleam@set:set(integer()),
        list(integer())})
) -> {gleam@set:set(integer()), list(integer())}.
process_successors_cps(Graph, Successors, Visited, Used_edges, Acc, Cont) ->
    case Successors of
        [] ->
            Cont(Visited, Used_edges, Acc);

        [{Dst, Eid, _} | Rest] ->
            case gleam@set:contains(Used_edges, Eid) of
                true ->
                    process_successors_cps(
                        Graph,
                        Rest,
                        Visited,
                        Used_edges,
                        Acc,
                        Cont
                    );

                false ->
                    Used2 = gleam@set:insert(Used_edges, Eid),
                    do_dfs_cps(
                        Graph,
                        Dst,
                        Visited,
                        Used2,
                        Acc,
                        fun(V_after, Ue_after, Acc_after) ->
                            process_successors_cps(
                                Graph,
                                Rest,
                                V_after,
                                Ue_after,
                                Acc_after,
                                Cont
                            )
                        end
                    )
            end
    end.

-file("src/yog/multi/traversal.gleam", 181).
-spec do_dfs_cps(
    yog@multi@model:multi_graph(any(), any()),
    integer(),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    list(integer()),
    fun((gleam@set:set(integer()), gleam@set:set(integer()), list(integer())) -> {gleam@set:set(integer()),
        list(integer())})
) -> {gleam@set:set(integer()), list(integer())}.
do_dfs_cps(Graph, Current, Visited_nodes, Used_edges, Acc, Cont) ->
    case gleam@set:contains(Visited_nodes, Current) of
        true ->
            Cont(Visited_nodes, Used_edges, Acc);

        false ->
            Visited2 = gleam@set:insert(Visited_nodes, Current),
            Acc2 = [Current | Acc],
            Successors = yog@multi@model:successors(Graph, Current),
            process_successors_cps(
                Graph,
                Successors,
                Visited2,
                Used_edges,
                Acc2,
                Cont
            )
    end.

-file("src/yog/multi/traversal.gleam", 166).
-spec do_dfs(
    yog@multi@model:multi_graph(any(), any()),
    integer(),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    list(integer())
) -> list(integer()).
do_dfs(Graph, Current, Visited_nodes, Used_edges, Acc) ->
    _pipe = do_dfs_cps(
        Graph,
        Current,
        Visited_nodes,
        Used_edges,
        Acc,
        fun(V, _, A) -> {V, A} end
    ),
    (fun(R) -> erlang:element(2, R) end)(_pipe).

-file("src/yog/multi/traversal.gleam", 45).
?DOC(
    " Performs a Depth-First Search from `source`, returning visited node IDs\n"
    " in DFS pre-order.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec dfs(yog@multi@model:multi_graph(any(), any()), integer()) -> list(integer()).
dfs(Graph, Source) ->
    _pipe = do_dfs(Graph, Source, gleam@set:new(), gleam@set:new(), []),
    lists:reverse(_pipe).