yog

-module(yog).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog.gleam").
-export([new/1, directed/0, undirected/0, add_node/3, add_edge/4, add_edge_ensured/5, add_unweighted_edge/3, add_simple_edge/3, successors/2, predecessors/2, neighbors/2, all_nodes/1, from_edges/2, from_unweighted_edges/2, from_adjacency_list/2, successor_ids/2, is_cyclic/1, is_acyclic/1, walk/3, walk_until/4, fold_walk/5, transpose/1, map_nodes/2, map_edges/2, filter_nodes/2, filter_edges/2, complement/2, merge/2, subgraph/2, contract/4, to_directed/1, to_undirected/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(
    " Yog - A comprehensive graph algorithm library for Gleam.\n"
    "\n"
    " Provides efficient implementations of classic graph algorithms with a\n"
    " clean, functional API.\n"
    "\n"
    " ## Quick Start\n"
    "\n"
    " ```gleam\n"
    " import yog\n"
    " import yog/pathfinding/dijkstra as pathfinding\n"
    " import gleam/int\n"
    "\n"
    " pub fn main() {\n"
    "   let graph =\n"
    "     yog.directed()\n"
    "     |> yog.add_node(1, \"Start\")\n"
    "     |> yog.add_node(2, \"Middle\")\n"
    "     |> yog.add_node(3, \"End\")\n"
    "     |> yog.add_edge(from: 1, to: 2, with: 5)\n"
    "     |> yog.add_edge(from: 2, to: 3, with: 3)\n"
    "     |> yog.add_edge(from: 1, to: 3, with: 10)\n"
    "\n"
    "   case pathfinding.shortest_path(\n"
    "     in: graph,\n"
    "     from: 1,\n"
    "     to: 3,\n"
    "     with_zero: 0,\n"
    "     with_add: int.add,\n"
    "     with_compare: int.compare\n"
    "   ) {\n"
    "     Some(path) -> {\n"
    "       // Path(nodes: [1, 2, 3], total_weight: 8)\n"
    "       io.println(\"Shortest path found!\")\n"
    "     }\n"
    "     None -> io.println(\"No path exists\")\n"
    "   }\n"
    " }\n"
    " ```\n"
    "\n"
    " ## Modules\n"
    "\n"
    " ### Core\n"
    " - **`yog/model`** - Graph data structures and basic operations\n"
    "   - Create directed/undirected graphs\n"
    "   - Add nodes and edges\n"
    "   - Query successors, predecessors, neighbors\n"
    "\n"
    " - **`yog/builder/labeled`** - Build graphs with arbitrary labels\n"
    "   - Use strings or any type as node identifiers\n"
    "   - Automatically maps labels to internal integer IDs\n"
    "   - Convert to standard Graph for use with all algorithms\n"
    "\n"
    " ### Algorithms\n"
    " - **`yog/pathfinding`** - Shortest path algorithms\n"
    "   - Dijkstra's algorithm (non-negative weights)\n"
    "   - A* search (with heuristics)\n"
    "   - Bellman-Ford (negative weights, cycle detection)\n"
    "\n"
    " - **`yog/traversal`** - Graph traversal\n"
    "   - Breadth-First Search (BFS)\n"
    "   - Depth-First Search (DFS)\n"
    "   - Early termination support\n"
    "\n"
    " - **`yog/mst`** - Minimum Spanning Tree\n"
    "   - Kruskal's algorithm with Union-Find\n"
    "   - Prim's algorithm with priority queue\n"
    "\n"
    " - **`yog/traversal`** - Topological ordering\n"
    "   - Kahn's algorithm\n"
    "   - Lexicographical variant (heap-based)\n"
    "\n"
    " - **`yog/connectivity`** - Connected components\n"
    "   - Tarjan's algorithm for Strongly Connected Components (SCC)\n"
    "   - Kosaraju's algorithm for SCC (two-pass with transpose)\n"
    "\n"
    " - **`yog/connectivity`** - Graph connectivity analysis\n"
    "   - Tarjan's algorithm for bridges and articulation points\n"
    "\n"
    " - **`yog/flow`** - Minimum cut algorithms\n"
    "   - Stoer-Wagner algorithm for global minimum cut\n"
    "\n"
    " - **`yog/properties`** - Eulerian paths and circuits\n"
    "   - Detection of Eulerian paths and circuits\n"
    "   - Hierholzer's algorithm for finding paths\n"
    "   - Works on both directed and undirected graphs\n"
    "\n"
    " - **`yog/properties`** - Bipartite graph detection and matching\n"
    "   - Bipartite detection (2-coloring)\n"
    "   - Partition extraction (independent sets)\n"
    "   - Maximum matching (augmenting path algorithm)\n"
    "\n"
    " ### Data Structures\n"
    " - **`yog/disjoint_set`** - Union-Find / Disjoint Set\n"
    "   - Path compression and union by rank\n"
    "   - O(α(n)) amortized operations (practically constant)\n"
    "   - Dynamic connectivity queries\n"
    "   - Generic over any type\n"
    "\n"
    " ### Transformations\n"
    " - **`yog/transform`** - Graph transformations\n"
    "   - Transpose (O(1) edge reversal!)\n"
    "   - Map nodes and edges (functor operations)\n"
    "   - Filter nodes with auto-pruning\n"
    "   - Merge graphs\n"
    "\n"
    " ### Visualization\n"
    " - **`yog/render`** - Graph visualization\n"
    "   - Mermaid diagram generation (GitHub/GitLab compatible)\n"
    "   - Path highlighting for algorithm results\n"
    "   - Customizable node and edge labels\n"
    "\n"
    " ## Features\n"
    "\n"
    " - **Functional and Immutable**: All operations return new graphs\n"
    " - **Generic**: Works with any node/edge data types\n"
    " - **Type-Safe**: Leverages Gleam's type system\n"
    " - **Well-Tested**: 494+ tests covering all algorithms and data structures\n"
    " - **Efficient**: Optimal data structures (pairing heaps, union-find)\n"
    " - **Documented**: Every function has examples\n"
).

-file("src/yog.gleam", 169).
?DOC(
    " Creates a new empty graph of the specified type.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog\n"
    " import yog/model.{Directed}\n"
    "\n"
    " let graph = yog.new(Directed)\n"
    " ```\n"
).
-spec new(yog@model:graph_type()) -> yog@model:graph(any(), any()).
new(Graph_type) ->
    yog@model:new(Graph_type).

-file("src/yog.gleam", 189).
?DOC(
    " Creates a new empty directed graph.\n"
    "\n"
    " This is a convenience function that's equivalent to `yog.new(Directed)`,\n"
    " but requires only a single import.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog\n"
    "\n"
    " let graph =\n"
    "   yog.directed()\n"
    "   |> yog.add_node(1, \"Start\")\n"
    "   |> yog.add_node(2, \"End\")\n"
    "   |> yog.add_edge(from: 1, to: 2, with: 10)\n"
    " ```\n"
).
-spec directed() -> yog@model:graph(any(), any()).
directed() ->
    yog@model:new(directed).

-file("src/yog.gleam", 209).
?DOC(
    " Creates a new empty undirected graph.\n"
    "\n"
    " This is a convenience function that's equivalent to `yog.new(Undirected)`,\n"
    " but requires only a single import.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog\n"
    "\n"
    " let graph =\n"
    "   yog.undirected()\n"
    "   |> yog.add_node(1, \"A\")\n"
    "   |> yog.add_node(2, \"B\")\n"
    "   |> yog.add_edge(from: 1, to: 2, with: 5)\n"
    " ```\n"
).
-spec undirected() -> yog@model:graph(any(), any()).
undirected() ->
    yog@model:new(undirected).

-file("src/yog.gleam", 223).
?DOC(
    " Adds a node to the graph with the given ID and data.\n"
    " If a node with this ID already exists, its data will be replaced.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " graph\n"
    " |> yog.add_node(1, \"Node A\")\n"
    " |> yog.add_node(2, \"Node B\")\n"
    " ```\n"
).
-spec add_node(yog@model:graph(MAX, MAY), integer(), MAX) -> yog@model:graph(MAX, MAY).
add_node(Graph, Id, Data) ->
    yog@model:add_node(Graph, Id, Data).

-file("src/yog.gleam", 238).
?DOC(
    " Adds an edge to the graph with the given weight.\n"
    "\n"
    " For directed graphs, adds a single edge from `src` to `dst`.\n"
    " For undirected graphs, adds edges in both directions.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " graph\n"
    " |> yog.add_edge(from: 1, to: 2, with: 10)\n"
    " ```\n"
).
-spec add_edge(yog@model:graph(MBD, MBE), integer(), integer(), MBE) -> yog@model:graph(MBD, MBE).
add_edge(Graph, Src, Dst, Weight) ->
    yog@model:add_edge(Graph, Src, Dst, Weight).

-file("src/yog.gleam", 259).
?DOC(
    " Like `add_edge`, but ensures both endpoint nodes exist first.\n"
    "\n"
    " If `src` or `dst` is not already in the graph, it is created with\n"
    " the supplied `default` node data. Existing nodes are left unchanged.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " yog.directed()\n"
    " |> yog.add_edge_ensured(from: 1, to: 2, with: 10, default: \"anon\")\n"
    " // Nodes 1 and 2 are auto-created with data \"anon\"\n"
    " ```\n"
).
-spec add_edge_ensured(
    yog@model:graph(MBJ, MBK),
    integer(),
    integer(),
    MBK,
    MBJ
) -> yog@model:graph(MBJ, MBK).
add_edge_ensured(Graph, Src, Dst, Weight, Default) ->
    yog@model:add_edge_ensured(Graph, Src, Dst, Weight, Default).

-file("src/yog.gleam", 282).
?DOC(
    " Adds an unweighted edge to the graph.\n"
    "\n"
    " This is a convenience function for graphs where edges have no meaningful weight.\n"
    " Uses `Nil` as the edge data type.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph: Graph(String, Nil) = yog.directed()\n"
    "   |> yog.add_node(1, \"A\")\n"
    "   |> yog.add_node(2, \"B\")\n"
    "   |> yog.add_unweighted_edge(from: 1, to: 2)\n"
    " ```\n"
).
-spec add_unweighted_edge(yog@model:graph(MBP, nil), integer(), integer()) -> yog@model:graph(MBP, nil).
add_unweighted_edge(Graph, Src, Dst) ->
    yog@model:add_edge(Graph, Src, Dst, nil).

-file("src/yog.gleam", 303).
?DOC(
    " Adds a simple edge with weight 1.\n"
    "\n"
    " This is a convenience function for graphs with integer weights where\n"
    " a default weight of 1 is appropriate (e.g., unweighted graphs, hop counts).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " graph\n"
    " |> yog.add_simple_edge(from: 1, to: 2)\n"
    " |> yog.add_simple_edge(from: 2, to: 3)\n"
    " // Both edges have weight 1\n"
    " ```\n"
).
-spec add_simple_edge(yog@model:graph(MBU, integer()), integer(), integer()) -> yog@model:graph(MBU, integer()).
add_simple_edge(Graph, Src, Dst) ->
    yog@model:add_edge(Graph, Src, Dst, 1).

-file("src/yog.gleam", 313).
?DOC(
    " Gets nodes you can travel TO from the given node (successors).\n"
    " Returns a list of tuples containing the destination node ID and edge data.\n"
).
-spec successors(yog@model:graph(any(), MCA), integer()) -> list({integer(),
    MCA}).
successors(Graph, Id) ->
    yog@model:successors(Graph, Id).

-file("src/yog.gleam", 319).
?DOC(
    " Gets nodes you came FROM to reach the given node (predecessors).\n"
    " Returns a list of tuples containing the source node ID and edge data.\n"
).
-spec predecessors(yog@model:graph(any(), MCF), integer()) -> list({integer(),
    MCF}).
predecessors(Graph, Id) ->
    yog@model:predecessors(Graph, Id).

-file("src/yog.gleam", 326).
?DOC(
    " Gets all nodes connected to the given node, regardless of direction.\n"
    " For undirected graphs, this is equivalent to successors.\n"
    " For directed graphs, this combines successors and predecessors.\n"
).
-spec neighbors(yog@model:graph(any(), MCK), integer()) -> list({integer(), MCK}).
neighbors(Graph, Id) ->
    yog@model:neighbors(Graph, Id).

-file("src/yog.gleam", 331).
?DOC(" Returns all unique node IDs that have edges in the graph.\n").
-spec all_nodes(yog@model:graph(any(), any())) -> list(integer()).
all_nodes(Graph) ->
    yog@model:all_nodes(Graph).

-file("src/yog.gleam", 342).
?DOC(
    " Creates a graph from a list of edges #(src, dst, weight).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = yog.from_edges(model.Directed, [#(1, 2, 10), #(2, 3, 5)])\n"
    " ```\n"
).
-spec from_edges(yog@model:graph_type(), list({integer(), integer(), MCT})) -> yog@model:graph(nil, MCT).
from_edges(Graph_type, Edges) ->
    gleam@list:fold(
        Edges,
        new(Graph_type),
        fun(G, Edge) ->
            {Src, Dst, Weight} = Edge,
            _pipe = G,
            _pipe@1 = add_node(_pipe, Src, nil),
            _pipe@2 = add_node(_pipe@1, Dst, nil),
            add_edge(_pipe@2, Src, Dst, Weight)
        end
    ).

-file("src/yog.gleam", 362).
?DOC(
    " Creates a graph from a list of unweighted edges #(src, dst).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = yog.from_unweighted_edges(model.Directed, [#(1, 2), #(2, 3)])\n"
    " ```\n"
).
-spec from_unweighted_edges(
    yog@model:graph_type(),
    list({integer(), integer()})
) -> yog@model:graph(nil, nil).
from_unweighted_edges(Graph_type, Edges) ->
    gleam@list:fold(
        Edges,
        new(Graph_type),
        fun(G, Edge) ->
            {Src, Dst} = Edge,
            _pipe = G,
            _pipe@1 = add_node(_pipe, Src, nil),
            _pipe@2 = add_node(_pipe@1, Dst, nil),
            add_unweighted_edge(_pipe@2, Src, Dst)
        end
    ).

-file("src/yog.gleam", 382).
?DOC(
    " Creates a graph from an adjacency list #(src, List(#(dst, weight))).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = yog.from_adjacency_list(model.Directed, [#(1, [#(2, 10), #(3, 5)])])\n"
    " ```\n"
).
-spec from_adjacency_list(
    yog@model:graph_type(),
    list({integer(), list({integer(), MDA})})
) -> yog@model:graph(nil, MDA).
from_adjacency_list(Graph_type, Adj_list) ->
    gleam@list:fold(
        Adj_list,
        new(Graph_type),
        fun(G, Entry) ->
            {Src, Edges} = Entry,
            gleam@list:fold(
                Edges,
                add_node(G, Src, nil),
                fun(Acc, Edge) ->
                    {Dst, Weight} = Edge,
                    _pipe = Acc,
                    _pipe@1 = add_node(_pipe, Dst, nil),
                    add_edge(_pipe@1, Src, Dst, Weight)
                end
            )
        end
    ).

-file("src/yog.gleam", 399).
?DOC(
    " Returns just the NodeIds of successors (without edge data).\n"
    " Convenient for traversal algorithms that only need the IDs.\n"
).
-spec successor_ids(yog@model:graph(any(), any()), integer()) -> list(integer()).
successor_ids(Graph, Id) ->
    yog@model:successor_ids(Graph, Id).

-file("src/yog.gleam", 417).
?DOC(
    " Determines if a graph contains any cycles.\n"
    " \n"
    " For directed graphs, a cycle exists if there is a path from a node back to itself.\n"
    " For undirected graphs, a cycle exists if there is a path of length >= 3 from a node back to itself,\n"
    " or a self-loop.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " yog.is_cyclic(graph)\n"
    " // => True // Cycle detected\n"
    " ```\n"
).
-spec is_cyclic(yog@model:graph(any(), any())) -> boolean().
is_cyclic(Graph) ->
    yog@traversal:is_cyclic(Graph).

-file("src/yog.gleam", 434).
?DOC(
    " Determines if a graph is acyclic (contains no cycles).\n"
    "\n"
    " This is the logical opposite of `is_cyclic`. For directed graphs, returning\n"
    " `True` means the graph is a Directed Acyclic Graph (DAG).\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " yog.is_acyclic(graph)\n"
    " // => True // Valid DAG or undirected forest\n"
    " ```\n"
).
-spec is_acyclic(yog@model:graph(any(), any())) -> boolean().
is_acyclic(Graph) ->
    yog@traversal:is_acyclic(Graph).

-file("src/yog.gleam", 439).
-spec walk(yog@model:graph(any(), any()), integer(), yog@traversal:order()) -> list(integer()).
walk(Graph, Start_id, Order) ->
    yog@traversal:walk(Graph, Start_id, Order).

-file("src/yog.gleam", 447).
-spec walk_until(
    yog@model:graph(any(), any()),
    integer(),
    yog@traversal:order(),
    fun((integer()) -> boolean())
) -> list(integer()).
walk_until(Graph, Start_id, Order, Should_stop) ->
    yog@traversal:walk_until(Graph, Start_id, Order, Should_stop).

-file("src/yog.gleam", 456).
-spec fold_walk(
    yog@model:graph(any(), any()),
    integer(),
    yog@traversal:order(),
    MEG,
    fun((MEG, integer(), yog@traversal:walk_metadata(integer())) -> {yog@traversal:walk_control(),
        MEG})
) -> MEG.
fold_walk(Graph, Start, Order, Acc, Folder) ->
    yog@traversal:fold_walk(Graph, Start, Order, Acc, Folder).

-file("src/yog.gleam", 473).
-spec transpose(yog@model:graph(MEI, MEJ)) -> yog@model:graph(MEI, MEJ).
transpose(Graph) ->
    yog@transform:transpose(Graph).

-file("src/yog.gleam", 477).
-spec map_nodes(yog@model:graph(MEO, MEP), fun((MEO) -> MES)) -> yog@model:graph(MES, MEP).
map_nodes(Graph, Fun) ->
    yog@transform:map_nodes(Graph, Fun).

-file("src/yog.gleam", 481).
-spec map_edges(yog@model:graph(MEV, MEW), fun((MEW) -> MEZ)) -> yog@model:graph(MEV, MEZ).
map_edges(Graph, Fun) ->
    yog@transform:map_edges(Graph, Fun).

-file("src/yog.gleam", 485).
-spec filter_nodes(yog@model:graph(MFC, MFD), fun((MFC) -> boolean())) -> yog@model:graph(MFC, MFD).
filter_nodes(Graph, Predicate) ->
    yog@transform:filter_nodes(Graph, Predicate).

-file("src/yog.gleam", 492).
-spec filter_edges(
    yog@model:graph(MFI, MFJ),
    fun((integer(), integer(), MFJ) -> boolean())
) -> yog@model:graph(MFI, MFJ).
filter_edges(Graph, Predicate) ->
    yog@transform:filter_edges(Graph, Predicate).

-file("src/yog.gleam", 499).
-spec complement(yog@model:graph(MFO, MFP), MFP) -> yog@model:graph(MFO, MFP).
complement(Graph, Default_weight) ->
    yog@transform:complement(Graph, Default_weight).

-file("src/yog.gleam", 506).
-spec merge(yog@model:graph(MFU, MFV), yog@model:graph(MFU, MFV)) -> yog@model:graph(MFU, MFV).
merge(Base, Other) ->
    yog@transform:merge(Base, Other).

-file("src/yog.gleam", 510).
-spec subgraph(yog@model:graph(MGC, MGD), list(integer())) -> yog@model:graph(MGC, MGD).
subgraph(Graph, Ids) ->
    yog@transform:subgraph(Graph, Ids).

-file("src/yog.gleam", 514).
-spec contract(
    yog@model:graph(MGJ, MGK),
    integer(),
    integer(),
    fun((MGK, MGK) -> MGK)
) -> yog@model:graph(MGJ, MGK).
contract(Graph, A, B, With_combine) ->
    yog@transform:contract(Graph, A, B, With_combine).

-file("src/yog.gleam", 528).
-spec to_directed(yog@model:graph(MGP, MGQ)) -> yog@model:graph(MGP, MGQ).
to_directed(Graph) ->
    yog@transform:to_directed(Graph).

-file("src/yog.gleam", 532).
-spec to_undirected(yog@model:graph(MGV, MGW), fun((MGW, MGW) -> MGW)) -> yog@model:graph(MGV, MGW).
to_undirected(Graph, Resolve) ->
    yog@transform:to_undirected(Graph, Resolve).