yog

-module(yog@dag).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/dag.gleam").
-export([from_graph/1, to_graph/1, add_node/3, remove_node/2, remove_edge/3, add_edge/4, topological_sort/1, shortest_path/3, longest_path/1, transitive_closure/2, transitive_reduction/2, count_reachability/2, lowest_common_ancestors/3]).

-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(
    " # Frugal Directed Acyclic Graphs\n"
    " \n"
    " This module provides a strictly typed wrapper `Dag(n, e)` for modeling \n"
    " Directed Acyclic Graphs (DAGs) without runtime cycle-checking overhead during\n"
    " standard graph building. \n"
    " \n"
    " ## The Frugal DAG Philosophy\n"
    " \n"
    " Yog treats DAGs as a specialized _view_ of a graph, rather than a fundamentally \n"
    " different structure. The standard way to create a DAG is to:\n"
    " \n"
    " 1. Build a normal graph first using `yog.directed()` and standard `add_node`/`add_edge`.\n"
    " 2. Once built, \"seal\" it as a DAG using `dag.from_graph(graph)`. This runs\n"
    "    a fast $O(V+E)$ validation.\n"
    " 3. Utilize DAG-only algorithms (like $O(V+E)$ longest paths or transitive closures) \n"
    "    on the returned `Dag` instance.\n"
    " \n"
    " **Do not build graphs exclusively with `dag.add_edge()`!** \n"
    " \n"
    " While mutating functions like `add_node`, `remove_node`, and `add_edge` are \n"
    " available here, they are designed strictly for *experimentation* or *minor updates* \n"
    " to an already-validated DAG. Because `add_edge` can introduce a cycle, calling it \n"
    " forces an $O(V+E)$ property check immediately, returning a `Result(Dag, DagError)`.\n"
    " Attempting to build a 100,000-edge graph using `dag.add_edge` will result in \n"
    " $O(N \\cdot (V+E))$ performance decay.\n"
).

-file("src/yog/dag.gleam", 34).
-spec from_graph(yog@model:graph(LBZ, LCA)) -> {ok,
        yog@dag@models:dag(LBZ, LCA)} |
    {error, yog@dag@models:dag_error()}.
from_graph(Graph) ->
    yog@dag@models:from_graph(Graph).

-file("src/yog/dag.gleam", 38).
-spec to_graph(yog@dag@models:dag(KZK, KZL)) -> yog@model:graph(KZK, KZL).
to_graph(Dag) ->
    yog@dag@models:to_graph(Dag).

-file("src/yog/dag.gleam", 42).
-spec add_node(yog@dag@models:dag(KZP, KZQ), integer(), KZP) -> yog@dag@models:dag(KZP, KZQ).
add_node(Dag, Id, Data) ->
    yog@dag@models:add_node(Dag, Id, Data).

-file("src/yog/dag.gleam", 46).
-spec remove_node(yog@dag@models:dag(KZV, KZW), integer()) -> yog@dag@models:dag(KZV, KZW).
remove_node(Dag, Id) ->
    yog@dag@models:remove_node(Dag, Id).

-file("src/yog/dag.gleam", 50).
-spec remove_edge(yog@dag@models:dag(LAB, LAC), integer(), integer()) -> yog@dag@models:dag(LAB, LAC).
remove_edge(Dag, Src, Dst) ->
    yog@dag@models:remove_edge(Dag, Src, Dst).

-file("src/yog/dag.gleam", 54).
-spec add_edge(yog@dag@models:dag(LAI, LAJ), integer(), integer(), LAJ) -> {ok,
        yog@dag@models:dag(LAI, LAJ)} |
    {error, yog@dag@models:dag_error()}.
add_edge(Dag, Src, Dst, Weight) ->
    yog@dag@models:add_edge(Dag, Src, Dst, Weight).

-file("src/yog/dag.gleam", 59).
-spec topological_sort(yog@dag@models:dag(any(), any())) -> list(integer()).
topological_sort(Dag) ->
    yog@dag@algorithms:topological_sort(Dag).

-file("src/yog/dag.gleam", 63).
-spec shortest_path(yog@dag@models:dag(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path(Dag, Start, Goal) ->
    yog@dag@algorithms:shortest_path(Dag, Start, Goal).

-file("src/yog/dag.gleam", 71).
-spec longest_path(yog@dag@models:dag(any(), integer())) -> list(integer()).
longest_path(Dag) ->
    yog@dag@algorithms:longest_path(Dag).

-file("src/yog/dag.gleam", 75).
-spec transitive_closure(yog@dag@models:dag(LBD, LBE), fun((LBE, LBE) -> LBE)) -> yog@dag@models:dag(LBD, LBE).
transitive_closure(Dag, Merge_fn) ->
    yog@dag@algorithms:transitive_closure(Dag, Merge_fn).

-file("src/yog/dag.gleam", 79).
-spec transitive_reduction(yog@dag@models:dag(LBI, LBJ), fun((LBJ, LBJ) -> LBJ)) -> yog@dag@models:dag(LBI, LBJ).
transitive_reduction(Dag, Merge_fn) ->
    yog@dag@algorithms:transitive_reduction(Dag, Merge_fn).

-file("src/yog/dag.gleam", 83).
-spec count_reachability(
    yog@dag@models:dag(any(), any()),
    yog@dag@algorithms:direction()
) -> gleam@dict:dict(integer(), integer()).
count_reachability(Dag, Direction) ->
    yog@dag@algorithms:count_reachability(Dag, Direction).

-file("src/yog/dag.gleam", 87).
-spec lowest_common_ancestors(
    yog@dag@models:dag(any(), any()),
    integer(),
    integer()
) -> list(integer()).
lowest_common_ancestors(Dag, Node_a, Node_b) ->
    yog@dag@algorithms:lowest_common_ancestors(Dag, Node_a, Node_b).