Current section
Files
Jump to
Current section
Files
src/yog@dag@algorithm.erl
-module(yog@dag@algorithm).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/dag/algorithm.gleam").
-export([topological_sort/1, longest_path/1, transitive_closure/2, transitive_reduction/2, shortest_path/3, count_reachability/2, lowest_common_ancestors/3]).
-export_type([direction/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.
?MODULEDOC(
" # ⚠️ Experimental Module\n"
"\n"
" This module is experimental and provides minimal, working functionality.\n"
" The implementation is functional but may not be fully optimized for performance.\n"
"\n"
" **Expected changes:**\n"
" - Additional features and algorithms will be added\n"
" - Performance enhancements and optimizations\n"
" - API may be subject to change in future versions\n"
"\n"
" Use with caution in production environments.\n"
).
-type direction() :: ancestors | descendants.
-file("src/yog/dag/algorithm.gleam", 45).
?DOC(
" Returns a topological ordering of all nodes in the DAG.\n"
"\n"
" Unlike `traversal.topological_sort()` which returns `Result` (since general\n"
" graphs may contain cycles), this version is **total** - it always returns\n"
" a valid ordering because the `Dag` type guarantees acyclicity.\n"
"\n"
" In a topological ordering, every node appears before all nodes it has edges to.\n"
" This is useful for scheduling tasks with dependencies, build systems, etc.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Given edges: 1->2, 1->3, 2->4, 3->4\n"
" // Valid topological sorts include: [1, 2, 3, 4] or [1, 3, 2, 4]\n"
" let sorted = dag.algorithms.topological_sort(my_dag)\n"
" // sorted == [1, 2, 3, 4] // or another valid ordering\n"
" ```\n"
).
-spec topological_sort(yog@dag@model:dag(any(), any())) -> list(integer()).
topological_sort(Dag) ->
Graph = yog@dag@model:to_graph(Dag),
Sorted@1 = case yog@traversal:topological_sort(Graph) of
{ok, Sorted} -> Sorted;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/dag/algorithm"/utf8>>,
function => <<"topological_sort"/utf8>>,
line => 48,
value => _assert_fail,
start => 1774,
'end' => 1831,
pattern_start => 1785,
pattern_end => 1795})
end,
Sorted@1.
-file("src/yog/dag/algorithm.gleam", 134).
-spec reconstruct_path(
integer(),
gleam@dict:dict(integer(), integer()),
list(integer())
) -> list(integer()).
reconstruct_path(Current, Predecessors, Path) ->
New_path = [Current | Path],
case gleam_stdlib:map_get(Predecessors, Current) of
{ok, Prev} ->
reconstruct_path(Prev, Predecessors, New_path);
{error, _} ->
New_path
end.
-file("src/yog/dag/algorithm.gleam", 73).
?DOC(
" Finds the longest path (critical path) in a weighted DAG.\n"
"\n"
" The longest path is the path with maximum total edge weight from any source\n"
" node to any sink node. This is the dual of shortest path and is useful for:\n"
" - Project scheduling (finding the critical path)\n"
" - Dependency chains with durations\n"
" - Determining minimum time to complete all tasks\n"
"\n"
" **Time Complexity:** O(V + E) - linear via dynamic programming on the\n"
" topologically sorted DAG.\n"
"\n"
" **Note:** For unweighted graphs, this finds the path with most edges.\n"
" Weights must be non-negative for meaningful results.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Find the critical path in a project schedule\n"
" let critical_path = dag.algorithms.longest_path(project_dag)\n"
" // critical_path == [start, task_a, task_b, end]\n"
" ```\n"
).
-spec longest_path(yog@dag@model:dag(any(), integer())) -> list(integer()).
longest_path(Dag) ->
Graph = yog@dag@model:to_graph(Dag),
Sorted_nodes = topological_sort(Dag),
{Distances, Predecessors} = gleam@list:fold(
Sorted_nodes,
{maps:new(), maps:new()},
fun(Acc, Node) ->
{Dist_acc, Pred_acc} = Acc,
Node_dist = case gleam_stdlib:map_get(Dist_acc, Node) of
{ok, D} ->
D;
{error, _} ->
0
end,
case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
{ok, Edges} ->
gleam@dict:fold(
Edges,
{Dist_acc, Pred_acc},
fun(Inner_acc, Target, Weight) ->
{D_acc, P_acc} = Inner_acc,
Current_target_dist = gleam_stdlib:map_get(
D_acc,
Target
),
New_dist = Node_dist + Weight,
Should_update = case Current_target_dist of
{ok, D@1} ->
New_dist > D@1;
{error, _} ->
true
end,
case Should_update of
true ->
{gleam@dict:insert(D_acc, Target, New_dist),
gleam@dict:insert(P_acc, Target, Node)};
false ->
Inner_acc
end
end
);
{error, _} ->
Acc
end
end
),
Max_node_opt = gleam@dict:fold(
Distances,
none,
fun(Acc@1, Node@1, Dist) -> case Acc@1 of
none ->
{some, {Node@1, Dist}};
{some, {_, Max_d}} when Dist > Max_d ->
{some, {Node@1, Dist}};
_ ->
Acc@1
end end
),
case Max_node_opt of
none ->
[];
{some, {End_node, _}} ->
reconstruct_path(End_node, Predecessors, [])
end.
-file("src/yog/dag/algorithm.gleam", 169).
?DOC(
" Computes the transitive closure of a DAG.\n"
"\n"
" The transitive closure adds edges between all pairs of nodes where a path\n"
" exists in the original graph. If `u` can reach `v` through any path, the\n"
" closure will have a direct edge `u -> v`.\n"
"\n"
" The `merge_fn` is used to combine edge weights when multiple paths exist\n"
" between the same pair of nodes.\n"
"\n"
" **Use cases:**\n"
" - Reachability queries (is A reachable from B?)\n"
" - Precomputing path relationships\n"
" - Dependency analysis (what indirectly depends on what?)\n"
"\n"
" **Time Complexity:** O(V × E) in the worst case\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Original edges: A->B (weight 2), B->C (weight 3)\n"
" // Closure adds: A->C (weight 5 = 2+3)\n"
" let closure = dag.algorithms.transitive_closure(dag, int.add)\n"
" ```\n"
).
-spec transitive_closure(yog@dag@model:dag(NAJ, NAK), fun((NAK, NAK) -> NAK)) -> yog@dag@model:dag(NAJ, NAK).
transitive_closure(Dag, Merge_fn) ->
Graph = yog@dag@model:to_graph(Dag),
Sorted_nodes = begin
_pipe = topological_sort(Dag),
lists:reverse(_pipe)
end,
Reachability_map = gleam@list:fold(
Sorted_nodes,
maps:new(),
fun(Acc, Node) ->
case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
{ok, Edges} ->
Reachable_from_node = gleam@dict:fold(
Edges,
Edges,
fun(Reachable_acc, Child, W_node_child) ->
case gleam_stdlib:map_get(Acc, Child) of
{ok, Child_reachable} ->
gleam@dict:fold(
Child_reachable,
Reachable_acc,
fun(Inner_acc, Target, W_child_target) ->
Combined_weight = Merge_fn(
W_node_child,
W_child_target
),
case gleam_stdlib:map_get(
Inner_acc,
Target
) of
{ok, Existing_weight} ->
gleam@dict:insert(
Inner_acc,
Target,
Merge_fn(
Existing_weight,
Combined_weight
)
);
{error, _} ->
gleam@dict:insert(
Inner_acc,
Target,
Combined_weight
)
end
end
);
{error, _} ->
Reachable_acc
end
end
),
gleam@dict:insert(Acc, Node, Reachable_from_node);
{error, _} ->
gleam@dict:insert(Acc, Node, maps:new())
end
end
),
New_graph = gleam@dict:fold(
Reachability_map,
Graph,
fun(G_acc, Source_node, Targets) ->
gleam@dict:fold(
Targets,
G_acc,
fun(G_inner, Target_node, Weight) ->
G@1 = case yog@model:add_edge(
G_inner,
Source_node,
Target_node,
Weight
) of
{ok, G} -> G;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/dag/algorithm"/utf8>>,
function => <<"transitive_closure"/utf8>>,
line => 229,
value => _assert_fail,
start => 8079,
'end' => 8242,
pattern_start => 8090,
pattern_end => 8095})
end,
G@1
end
)
end
),
New_dag@1 = case yog@dag@model:from_graph(New_graph) of
{ok, New_dag} -> New_dag;
_assert_fail@1 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/dag/algorithm"/utf8>>,
function => <<"transitive_closure"/utf8>>,
line => 240,
value => _assert_fail@1,
start => 8272,
'end' => 8364,
pattern_start => 8283,
pattern_end => 8294})
end,
New_dag@1.
-file("src/yog/dag/algorithm.gleam", 267).
?DOC(
" Computes the transitive reduction of a DAG.\n"
"\n"
" The transitive reduction removes all edges that are redundant - i.e., edges\n"
" `u -> v` where there exists an indirect path from `u` to `v` through other\n"
" nodes. The result has the minimum number of edges while preserving all\n"
" reachability relationships.\n"
"\n"
" This is the inverse of transitive closure. It's useful for:\n"
" - Simplifying dependency graphs\n"
" - Removing implied dependencies\n"
" - Creating minimal representations\n"
"\n"
" **Time Complexity:** O(V × E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Original: A->B, B->C, A->C (A->C is implied by A->B->C)\n"
" // Reduction removes: A->C\n"
" // Result: A->B, B->C\n"
" let minimal = dag.algorithms.transitive_reduction(dag, int.add)\n"
" ```\n"
).
-spec transitive_reduction(yog@dag@model:dag(NAP, NAQ), fun((NAQ, NAQ) -> NAQ)) -> yog@dag@model:dag(NAP, NAQ).
transitive_reduction(Dag, Merge_fn) ->
Graph = yog@dag@model:to_graph(Dag),
Reach_dag = transitive_closure(Dag, Merge_fn),
Reach_graph = yog@dag@model:to_graph(Reach_dag),
Reduced_graph = gleam@dict:fold(
erlang:element(4, Graph),
Graph,
fun(G_acc, U, Targets) ->
gleam@dict:fold(
Targets,
G_acc,
fun(G_inner, V, _) ->
Is_redundant = gleam@dict:fold(
Targets,
false,
fun(Found_redundant, W, _) ->
case {Found_redundant, W =:= V} of
{true, _} ->
true;
{false, true} ->
false;
{false, false} ->
case gleam_stdlib:map_get(
erlang:element(4, Reach_graph),
W
) of
{ok, W_targets} ->
gleam@dict:has_key(W_targets, V);
{error, _} ->
false
end
end
end
),
case Is_redundant of
true ->
yog@model:remove_edge(G_inner, U, V);
false ->
G_inner
end
end
)
end
),
New_dag@1 = case yog@dag@model:from_graph(Reduced_graph) of
{ok, New_dag} -> New_dag;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/dag/algorithm"/utf8>>,
function => <<"transitive_reduction"/utf8>>,
line => 303,
value => _assert_fail,
start => 10338,
'end' => 10434,
pattern_start => 10349,
pattern_end => 10360})
end,
New_dag@1.
-file("src/yog/dag/algorithm.gleam", 404).
-spec reconstruct_path_backward(
integer(),
integer(),
gleam@dict:dict(integer(), integer()),
list(integer())
) -> list(integer()).
reconstruct_path_backward(Current, Start, Predecessors, Path) ->
New_path = [Current | Path],
case Current =:= Start of
true ->
New_path;
false ->
case gleam_stdlib:map_get(Predecessors, Current) of
{ok, Prev} ->
reconstruct_path_backward(
Prev,
Start,
Predecessors,
New_path
);
{error, _} ->
New_path
end
end.
-file("src/yog/dag/algorithm.gleam", 342).
?DOC(
" Finds the shortest path between two specific nodes in a weighted DAG.\n"
"\n"
" Uses dynamic programming on the topologically sorted DAG to find the minimum\n"
" weight path from `from` to `to`. Unlike Dijkstra's algorithm which works on\n"
" general graphs in O((V+E) log V), this leverages the DAG property for linear\n"
" time complexity.\n"
"\n"
" Returns `None` if no path exists from `from` to `to`.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Find shortest path in a weighted DAG\n"
" case dag.algorithms.shortest_path(my_dag, from: start_node, to: end_node) {\n"
" Some(path) -> {\n"
" // path.nodes contains the node sequence\n"
" // path.total_weight is the path length\n"
" }\n"
" None -> // No path exists\n"
" }\n"
" ```\n"
).
-spec shortest_path(yog@dag@model:dag(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path(Dag, Start, Goal) ->
Graph = yog@dag@model:to_graph(Dag),
Sorted_nodes = topological_sort(Dag),
{Distances, Predecessors} = gleam@list:fold(
Sorted_nodes,
{maps:new(), maps:new()},
fun(Acc, Node) ->
{Dist_acc, Pred_acc} = Acc,
Dist_acc@1 = case Node =:= Start of
true ->
gleam@dict:insert(Dist_acc, Node, 0);
false ->
Dist_acc
end,
Node_dist = case gleam_stdlib:map_get(Dist_acc@1, Node) of
{ok, D} ->
D;
{error, _} ->
0
end,
case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
{ok, Edges} ->
gleam@dict:fold(
Edges,
{Dist_acc@1, Pred_acc},
fun(Inner_acc, Target, Weight) ->
{D_acc, P_acc} = Inner_acc,
Current_target_dist = gleam_stdlib:map_get(
D_acc,
Target
),
New_dist = Node_dist + Weight,
Should_update = case Current_target_dist of
{ok, D@1} ->
New_dist < D@1;
{error, _} ->
true
end,
case Should_update of
true ->
{gleam@dict:insert(D_acc, Target, New_dist),
gleam@dict:insert(P_acc, Target, Node)};
false ->
Inner_acc
end
end
);
{error, _} ->
Acc
end
end
),
case gleam_stdlib:map_get(Distances, Goal) of
{error, _} ->
none;
{ok, Total_dist} ->
Path = reconstruct_path_backward(Goal, Start, Predecessors, []),
{some, {path, Path, Total_dist}}
end.
-file("src/yog/dag/algorithm.gleam", 445).
?DOC(
" Counts the number of ancestors or descendants for every node.\n"
"\n"
" For each node, returns how many other nodes are reachable from it\n"
" (`Descendants`) or can reach it (`Ancestors`).\n"
"\n"
" Uses dynamic programming on the topologically sorted DAG for efficiency.\n"
" Properly handles diamond patterns where a node is reachable through multiple\n"
" paths - each node is only counted once.\n"
"\n"
" **Time Complexity:** O(V × E) in the worst case (sparse graphs),\n"
" optimized with set operations for common cases.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Given: A->B, A->C, B->D, C->D (diamond pattern)\n"
" // D has 3 ancestors (A, B, C)\n"
" // A has 3 descendants (B, C, D) - D counted once despite 2 paths\n"
" let descendant_counts = dag.algorithms.count_reachability(dag, Descendants)\n"
" // dict.get(descendant_counts, a) == Ok(3)\n"
" ```\n"
).
-spec count_reachability(yog@dag@model:dag(any(), any()), direction()) -> gleam@dict:dict(integer(), integer()).
count_reachability(Dag, Direction) ->
Graph = yog@dag@model:to_graph(Dag),
Nodes_to_process = case Direction of
descendants ->
_pipe = topological_sort(Dag),
lists:reverse(_pipe);
ancestors ->
topological_sort(Dag)
end,
Get_related = fun(Node) -> case Direction of
descendants ->
case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
{ok, Targets} ->
maps:keys(Targets);
{error, _} ->
[]
end;
ancestors ->
case gleam_stdlib:map_get(erlang:element(5, Graph), Node) of
{ok, Sources} ->
maps:keys(Sources);
{error, _} ->
[]
end
end end,
Reachability_sets = gleam@list:fold(
Nodes_to_process,
maps:new(),
fun(Acc, Node@1) ->
Related = Get_related(Node@1),
Related_set = gleam@set:from_list(Related),
All_reachable = gleam@list:fold(
Related,
Related_set,
fun(Set_acc, Child) -> case gleam_stdlib:map_get(Acc, Child) of
{ok, Child_set} ->
gleam@set:union(Set_acc, Child_set);
{error, _} ->
Set_acc
end end
),
gleam@dict:insert(Acc, Node@1, All_reachable)
end
),
gleam@dict:map_values(
Reachability_sets,
fun(_, Reachable) -> gleam@set:size(Reachable) end
).
-file("src/yog/dag/algorithm.gleam", 568).
-spec do_has_path(
yog@model:graph(any(), any()),
list(integer()),
integer(),
gleam@set:set(integer())
) -> boolean().
do_has_path(Graph, Stack, Target, Visited) ->
case Stack of
[] ->
false;
[Current | Rest] ->
case Current =:= Target of
true ->
true;
false ->
case gleam@set:contains(Visited, Current) of
true ->
do_has_path(Graph, Rest, Target, Visited);
false ->
New_visited = gleam@set:insert(Visited, Current),
Children = case gleam_stdlib:map_get(
erlang:element(4, Graph),
Current
) of
{ok, Edges} ->
maps:keys(Edges);
{error, _} ->
[]
end,
New_stack = gleam@list:fold(
Children,
Rest,
fun(Acc, Child) -> [Child | Acc] end
),
do_has_path(Graph, New_stack, Target, New_visited)
end
end
end.
-file("src/yog/dag/algorithm.gleam", 560).
?DOC(
" Checks if a path exists from `start` to `target` in the DAG.\n"
"\n"
" Performs a simple DFS traversal. Since the graph is a DAG, no cycle\n"
" detection is needed.\n"
"\n"
" **Time Complexity:** O(V + E) in the worst case\n"
).
-spec has_path(yog@dag@model:dag(any(), any()), integer(), integer()) -> boolean().
has_path(Dag, Start, Target) ->
Graph = yog@dag@model:to_graph(Dag),
do_has_path(Graph, [Start], Target, gleam@set:new()).
-file("src/yog/dag/algorithm.gleam", 546).
-spec get_ancestors_set(yog@dag@model:dag(any(), any()), integer()) -> list(integer()).
get_ancestors_set(Dag, Node) ->
Graph = yog@dag@model:to_graph(Dag),
All_nodes = maps:keys(erlang:element(3, Graph)),
gleam@list:filter(All_nodes, fun(N) -> has_path(Dag, N, Node) end).
-file("src/yog/dag/algorithm.gleam", 517).
?DOC(
" Finds the lowest common ancestors (LCAs) of two nodes.\n"
"\n"
" A common ancestor of nodes A and B is any node that has paths to both A and B.\n"
" The \"lowest\" common ancestors are those that are not ancestors of any other\n"
" common ancestor - they are the \"closest\" shared dependencies.\n"
"\n"
" This is useful for:\n"
" - Finding merge bases in version control\n"
" - Identifying shared dependencies\n"
" - Computing dominators in control flow graphs\n"
"\n"
" **Time Complexity:** O(V × (V + E))\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Given: X->A, X->B, Y->A, Z->B\n"
" // LCAs of A and B are [X] - the most specific shared ancestor\n"
" let lcas = dag.algorithms.lowest_common_ancestors(dag, a, b)\n"
" // lcas == [x]\n"
" ```\n"
).
-spec lowest_common_ancestors(
yog@dag@model:dag(any(), any()),
integer(),
integer()
) -> list(integer()).
lowest_common_ancestors(Dag, Node_a, Node_b) ->
Ancestors_counts_a = get_ancestors_set(Dag, Node_a),
Ancestors_counts_b = get_ancestors_set(Dag, Node_b),
Common_ancestors = gleam@list:filter(
Ancestors_counts_a,
fun(A) -> gleam@list:contains(Ancestors_counts_b, A) end
),
gleam@list:filter(
Common_ancestors,
fun(Candidate) ->
Is_ancestor_of_another = gleam@list:any(
Common_ancestors,
fun(Other) -> case Candidate =:= Other of
true ->
false;
false ->
has_path(Dag, Candidate, Other)
end end
),
not Is_ancestor_of_another
end
).