-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_ensure/5, add_edge_with/5, add_unweighted_edge/3, add_simple_edge/3, add_edges/2, add_simple_edges/2, add_unweighted_edges/2, 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 assert Ok(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_edges([#(1, 2, 5), #(2, 3, 3), #(1, 3, 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/property`** - 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/property`** - 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", 167). ?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", 187). ?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", 207). ?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", 221). ?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(IIG, IIH), integer(), IIG) -> yog@model:graph(IIG, IIH). add_node(Graph, Id, Data) -> yog@model:add_node(Graph, Id, Data). -file("src/yog.gleam", 250). ?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" " Returns `Error` if either endpoint node doesn't exist.\n" " Use `add_edge_ensure` to auto-create missing nodes, or add nodes first with `add_node`.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " graph\n" " |> yog.add_node(1, \"A\")\n" " |> yog.add_node(2, \"B\")\n" " |> yog.add_edge(from: 1, to: 2, with: 10)\n" " // => Ok(graph)\n" " ```\n" "\n" " ## With result.try for chaining\n" "\n" " ```gleam\n" " use graph <- result.try(yog.add_edge(graph, from: 1, to: 2, with: 10))\n" " use graph <- result.try(yog.add_edge(graph, from: 2, to: 3, with: 5))\n" " Ok(graph)\n" " ```\n" ). -spec add_edge(yog@model:graph(IIM, IIN), integer(), integer(), IIN) -> {ok, yog@model:graph(IIM, IIN)} | {error, binary()}. add_edge(Graph, Src, Dst, Weight) -> yog@model:add_edge(Graph, Src, Dst, Weight). -file("src/yog.gleam", 274). ?DOC( " Ensures both endpoint nodes exist, then adds an edge.\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" " Always succeeds and returns a `Graph` (never fails).\n" " Use this when you want to build graphs quickly without pre-creating nodes.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " yog.directed()\n" " |> yog.add_edge_ensure(from: 1, to: 2, with: 10, default: \"anon\")\n" " // Nodes 1 and 2 are auto-created with data \"anon\"\n" " ```\n" ). -spec add_edge_ensure(yog@model:graph(IIU, IIV), integer(), integer(), IIV, IIU) -> yog@model:graph(IIU, IIV). add_edge_ensure(Graph, Src, Dst, Weight, Default) -> yog@model:add_edge_ensure(Graph, Src, Dst, Weight, Default). -file("src/yog.gleam", 301). ?DOC( " Ensures both endpoint nodes exist using a callback, then adds an edge.\n" "\n" " If `src` or `dst` is not already in the graph, it is created by\n" " calling the `by` function with the node ID to generate the node data.\n" " Existing nodes are left unchanged.\n" "\n" " Always succeeds and returns a `Graph` (never fails).\n" "\n" " ## Example\n" "\n" " ```gleam\n" " yog.directed()\n" " |> yog.add_edge_with(from: 1, to: 2, with: 10, by: fn(id) {\n" " \"Node\" <> int.to_string(id)\n" " })\n" " // Nodes 1 and 2 are auto-created with \"Node1\" and \"Node2\"\n" " ```\n" ). -spec add_edge_with( yog@model:graph(IJA, IJB), integer(), integer(), IJB, fun((integer()) -> IJA) ) -> yog@model:graph(IJA, IJB). add_edge_with(Graph, Src, Dst, Weight, By) -> yog@model:add_edge_with(Graph, Src, Dst, Weight, By). -file("src/yog.gleam", 326). ?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" " Returns `Error` if either endpoint node doesn't exist.\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(IJG, nil), integer(), integer()) -> {ok, yog@model:graph(IJG, nil)} | {error, binary()}. add_unweighted_edge(Graph, Src, Dst) -> yog@model:add_edge(Graph, Src, Dst, nil). -file("src/yog.gleam", 349). ?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" " Returns `Error` if either endpoint node doesn't exist.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " graph\n" " |> yog.add_node(1, \"A\")\n" " |> yog.add_node(2, \"B\")\n" " |> yog.add_simple_edge(from: 1, to: 2)\n" " ```\n" ). -spec add_simple_edge(yog@model:graph(IJN, integer()), integer(), integer()) -> {ok, yog@model:graph(IJN, integer())} | {error, binary()}. add_simple_edge(Graph, Src, Dst) -> yog@model:add_edge(Graph, Src, Dst, 1). -file("src/yog.gleam", 379). ?DOC( " Adds multiple edges to the graph in a single operation.\n" "\n" " Fails fast on the first edge that references non-existent nodes.\n" " Returns `Error` if any endpoint node doesn't exist.\n" "\n" " This is more ergonomic than chaining multiple `add_edge` calls\n" " as it only requires unwrapping a single `Result`.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " let assert Ok(graph) =\n" " yog.directed()\n" " |> yog.add_node(1, \"A\")\n" " |> yog.add_node(2, \"B\")\n" " |> yog.add_node(3, \"C\")\n" " |> yog.add_edges([\n" " #(1, 2, 10),\n" " #(2, 3, 5),\n" " #(1, 3, 15),\n" " ])\n" " ```\n" ). -spec add_edges(yog@model:graph(IJU, IJV), list({integer(), integer(), IJV})) -> {ok, yog@model:graph(IJU, IJV)} | {error, binary()}. add_edges(Graph, Edges) -> yog@model:add_edges(Graph, Edges). -file("src/yog.gleam", 405). ?DOC( " Adds multiple simple edges (weight = 1) to the graph.\n" "\n" " Fails fast on the first edge that references non-existent nodes.\n" " Convenient for unweighted graphs where all edges have weight 1.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " let assert Ok(graph) =\n" " yog.directed()\n" " |> yog.add_node(1, \"A\")\n" " |> yog.add_node(2, \"B\")\n" " |> yog.add_node(3, \"C\")\n" " |> yog.add_simple_edges([\n" " #(1, 2),\n" " #(2, 3),\n" " #(1, 3),\n" " ])\n" " ```\n" ). -spec add_simple_edges( yog@model:graph(IKD, integer()), list({integer(), integer()}) ) -> {ok, yog@model:graph(IKD, integer())} | {error, binary()}. add_simple_edges(Graph, Edges) -> yog@model:add_simple_edges(Graph, Edges). -file("src/yog.gleam", 431). ?DOC( " Adds multiple unweighted edges (weight = Nil) to the graph.\n" "\n" " Fails fast on the first edge that references non-existent nodes.\n" " Convenient for graphs where edges carry no weight information.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " let assert Ok(graph) =\n" " yog.directed()\n" " |> yog.add_node(1, \"A\")\n" " |> yog.add_node(2, \"B\")\n" " |> yog.add_node(3, \"C\")\n" " |> yog.add_unweighted_edges([\n" " #(1, 2),\n" " #(2, 3),\n" " #(1, 3),\n" " ])\n" " ```\n" ). -spec add_unweighted_edges( yog@model:graph(IKL, nil), list({integer(), integer()}) ) -> {ok, yog@model:graph(IKL, nil)} | {error, binary()}. add_unweighted_edges(Graph, Edges) -> yog@model:add_unweighted_edges(Graph, Edges). -file("src/yog.gleam", 440). ?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(), IKU), integer()) -> list({integer(), IKU}). successors(Graph, Id) -> yog@model:successors(Graph, Id). -file("src/yog.gleam", 446). ?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(), IKZ), integer()) -> list({integer(), IKZ}). predecessors(Graph, Id) -> yog@model:predecessors(Graph, Id). -file("src/yog.gleam", 453). ?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(), ILE), integer()) -> list({integer(), ILE}). neighbors(Graph, Id) -> yog@model:neighbors(Graph, Id). -file("src/yog.gleam", 458). ?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", 469). ?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(), ILN})) -> yog@model:graph(nil, ILN). from_edges(Graph_type, Edges) -> gleam@list:fold( Edges, new(Graph_type), fun(G, Edge) -> {Src, Dst, Weight} = Edge, _pipe = G, add_edge_ensure(_pipe, Src, Dst, Weight, nil) end ). -file("src/yog.gleam", 487). ?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, add_edge_ensure(_pipe, Src, Dst, nil, nil) end ). -file("src/yog.gleam", 505). ?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(), ILU})}) ) -> yog@model:graph(nil, ILU). from_adjacency_list(Graph_type, Adj_list) -> gleam@list:fold( Adj_list, new(Graph_type), fun(G, Entry) -> {Src, Edges} = Entry, G@1 = add_node(G, Src, nil), gleam@list:fold( Edges, G@1, fun(Acc, Edge) -> {Dst, Weight} = Edge, _pipe = Acc, add_edge_ensure(_pipe, Src, Dst, Weight, nil) end ) end ). -file("src/yog.gleam", 524). ?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", 542). ?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", 559). ?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", 564). -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", 572). -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", 581). -spec fold_walk( yog@model:graph(any(), any()), integer(), yog@traversal:order(), INA, fun((INA, integer(), yog@traversal:walk_metadata(integer())) -> {yog@traversal:walk_control(), INA}) ) -> INA. fold_walk(Graph, Start, Order, Acc, Folder) -> yog@traversal:fold_walk(Graph, Start, Order, Acc, Folder). -file("src/yog.gleam", 598). -spec transpose(yog@model:graph(INC, IND)) -> yog@model:graph(INC, IND). transpose(Graph) -> yog@transform:transpose(Graph). -file("src/yog.gleam", 602). -spec map_nodes(yog@model:graph(INI, INJ), fun((INI) -> INM)) -> yog@model:graph(INM, INJ). map_nodes(Graph, Fun) -> yog@transform:map_nodes(Graph, Fun). -file("src/yog.gleam", 606). -spec map_edges(yog@model:graph(INP, INQ), fun((INQ) -> INT)) -> yog@model:graph(INP, INT). map_edges(Graph, Fun) -> yog@transform:map_edges(Graph, Fun). -file("src/yog.gleam", 610). -spec filter_nodes(yog@model:graph(INW, INX), fun((INW) -> boolean())) -> yog@model:graph(INW, INX). filter_nodes(Graph, Predicate) -> yog@transform:filter_nodes(Graph, Predicate). -file("src/yog.gleam", 617). -spec filter_edges( yog@model:graph(IOC, IOD), fun((integer(), integer(), IOD) -> boolean()) ) -> yog@model:graph(IOC, IOD). filter_edges(Graph, Predicate) -> yog@transform:filter_edges(Graph, Predicate). -file("src/yog.gleam", 624). -spec complement(yog@model:graph(IOI, IOJ), IOJ) -> yog@model:graph(IOI, IOJ). complement(Graph, Default_weight) -> yog@transform:complement(Graph, Default_weight). -file("src/yog.gleam", 631). -spec merge(yog@model:graph(IOO, IOP), yog@model:graph(IOO, IOP)) -> yog@model:graph(IOO, IOP). merge(Base, Other) -> yog@transform:merge(Base, Other). -file("src/yog.gleam", 635). -spec subgraph(yog@model:graph(IOW, IOX), list(integer())) -> yog@model:graph(IOW, IOX). subgraph(Graph, Ids) -> yog@transform:subgraph(Graph, Ids). -file("src/yog.gleam", 639). -spec contract( yog@model:graph(IPD, IPE), integer(), integer(), fun((IPE, IPE) -> IPE) ) -> yog@model:graph(IPD, IPE). contract(Graph, A, B, With_combine) -> yog@transform:contract(Graph, A, B, With_combine). -file("src/yog.gleam", 653). -spec to_directed(yog@model:graph(IPJ, IPK)) -> yog@model:graph(IPJ, IPK). to_directed(Graph) -> yog@transform:to_directed(Graph). -file("src/yog.gleam", 657). -spec to_undirected(yog@model:graph(IPP, IPQ), fun((IPQ, IPQ) -> IPQ)) -> yog@model:graph(IPP, IPQ). to_undirected(Graph, Resolve) -> yog@transform:to_undirected(Graph, Resolve).