Current section
Files
Jump to
Current section
Files
src/yog@model.erl
-module(yog@model).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/model.gleam").
-export([new/1, add_node/3, kind/1, order/1, node_count/1, edge_count/1, has_node/2, has_edge/3, successors/2, predecessors/2, remove_node/2, neighbors/2, successor_ids/2, predecessor_ids/2, neighbor_ids/2, out_degree/2, in_degree/2, degree/2, all_nodes/1, nodes/1, node/2, edge_data/3, all_edges/1, add_edge/4, add_edge_ensure/5, from_edges/2, from_unweighted_edges/2, from_adjacency_list/2, add_edge_with/5, add_edges/2, remove_edge/3, add_edge_with_combine/5, add_simple_edges/2, add_unweighted_edges/2]).
-export_type([graph_type/0, graph/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(
" Core graph data structures and basic operations for the yog library.\n"
"\n"
" This module defines the fundamental `Graph` type and provides all basic operations\n"
" for creating and manipulating graphs. The graph uses an adjacency list representation\n"
" with dual indexing (both outgoing and incoming edges) for efficient traversal in both\n"
" directions.\n"
"\n"
" ## Graph Types\n"
"\n"
" - **Directed Graph**: Edges have a direction (one-way relationships)\n"
" - **Undirected Graph**: Edges are bidirectional (mutual relationships)\n"
"\n"
" ## Type Parameters\n"
"\n"
" - `node_data`: The type of data stored at each node (e.g., `String`, `City`, `Task`)\n"
" - `edge_data`: The type of data stored on edges, typically weights (e.g., `Int`, `Float`)\n"
"\n"
" ## Quick Start\n"
"\n"
" ```gleam\n"
" import yog/model\n"
"\n"
" let assert Ok(graph) =\n"
" model.new(model.Undirected)\n"
" |> model.add_node(1, \"Alice\")\n"
" |> model.add_node(2, \"Bob\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10) // weight = 10\n"
" ```\n"
"\n"
" ## Design Notes\n"
"\n"
" The dual-map representation enables O(1) edge existence checks and O(1) transpose\n"
" operations, at the cost of increased memory usage and slightly more complex edge\n"
" updates.\n"
).
-type graph_type() :: directed | undirected.
-type graph(EGX, EGY) :: {graph,
graph_type(),
gleam@dict:dict(integer(), EGX),
gleam@dict:dict(integer(), gleam@dict:dict(integer(), EGY)),
gleam@dict:dict(integer(), gleam@dict:dict(integer(), EGY))}.
-file("src/yog/model.gleam", 81).
?DOC(
" Creates a new empty graph of the specified type.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let graph = model.new(Directed)\n"
" ```\n"
).
-spec new(graph_type()) -> graph(any(), any()).
new(Graph_type) ->
{graph, Graph_type, maps:new(), maps:new(), maps:new()}.
-file("src/yog/model.gleam", 100).
?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"
" |> model.add_node(1, \"Node A\")\n"
" |> model.add_node(2, \"Node B\")\n"
" ```\n"
).
-spec add_node(graph(EHD, EHE), integer(), EHD) -> graph(EHD, EHE).
add_node(Graph, Id, Data) ->
New_nodes = gleam@dict:insert(erlang:element(3, Graph), Id, Data),
{graph,
erlang:element(2, Graph),
New_nodes,
erlang:element(4, Graph),
erlang:element(5, Graph)}.
-file("src/yog/model.gleam", 484).
?DOC(" Gets the type of the graph (Directed or Undirected).\n").
-spec kind(graph(any(), any())) -> graph_type().
kind(Graph) ->
erlang:element(2, Graph).
-file("src/yog/model.gleam", 501).
?DOC(
" Returns the number of nodes in the graph (graph order).\n"
"\n"
" **Time Complexity:** O(1)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.order\n"
" // => 2\n"
" ```\n"
).
-spec order(graph(any(), any())) -> integer().
order(Graph) ->
maps:size(erlang:element(3, Graph)).
-file("src/yog/model.gleam", 519).
?DOC(
" Returns the number of nodes in the graph.\n"
" Equivalent to `order(graph)`.\n"
"\n"
" **Time Complexity:** O(1)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.node_count\n"
" // => 2\n"
" ```\n"
).
-spec node_count(graph(any(), any())) -> integer().
node_count(Graph) ->
order(Graph).
-file("src/yog/model.gleam", 542).
?DOC(
" Returns the number of edges in the graph.\n"
"\n"
" For undirected graphs, each edge is counted once (the pair {u, v}).\n"
" For directed graphs, each directed edge (u -> v) is counted once.\n"
"\n"
" **Time Complexity:** O(V)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
"\n"
" model.edge_count(graph)\n"
" // => 1\n"
" ```\n"
).
-spec edge_count(graph(any(), any())) -> integer().
edge_count(Graph) ->
_pipe = gleam@dict:fold(
erlang:element(4, Graph),
0,
fun(Acc, _, Targets) -> Acc + maps:size(Targets) end
),
(fun(Count) -> case erlang:element(2, Graph) of
directed ->
Count;
undirected ->
Count div 2
end end)(_pipe).
-file("src/yog/model.gleam", 557).
?DOC(
" Checks if the graph contains a node with the given ID.\n"
"\n"
" **Time Complexity:** O(1)\n"
).
-spec has_node(graph(any(), any()), integer()) -> boolean().
has_node(Graph, Id) ->
gleam@dict:has_key(erlang:element(3, Graph), Id).
-file("src/yog/model.gleam", 564).
?DOC(
" Checks if the graph contains an edge between `src` and `dst`.\n"
"\n"
" **Time Complexity:** O(1)\n"
).
-spec has_edge(graph(any(), any()), integer(), integer()) -> boolean().
has_edge(Graph, Src, Dst) ->
_pipe = gleam_stdlib:map_get(erlang:element(4, Graph), Src),
_pipe@1 = gleam@result:map(
_pipe,
fun(_capture) -> gleam@dict:has_key(_capture, Dst) end
),
gleam@result:unwrap(_pipe@1, false).
-file("src/yog/model.gleam", 588).
?DOC(
" Gets nodes you can travel TO (Successors).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
"\n"
" model.successors(graph, 1)\n"
" // => [#(2, 10)]\n"
" ```\n"
).
-spec successors(graph(any(), ELH), integer()) -> list({integer(), ELH}).
successors(Graph, Id) ->
_pipe = erlang:element(4, Graph),
_pipe@1 = gleam_stdlib:map_get(_pipe, Id),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:to_list/1),
gleam@result:unwrap(_pipe@2, []).
-file("src/yog/model.gleam", 609).
?DOC(
" Gets nodes you came FROM (Predecessors).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
"\n"
" model.predecessors(graph, 2)\n"
" // => [#(1, 10)]\n"
" ```\n"
).
-spec predecessors(graph(any(), ELM), integer()) -> list({integer(), ELM}).
predecessors(Graph, Id) ->
_pipe = erlang:element(5, Graph),
_pipe@1 = gleam_stdlib:map_get(_pipe, Id),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:to_list/1),
gleam@result:unwrap(_pipe@2, []).
-file("src/yog/model.gleam", 170).
?DOC(
" Removes a node and all its connected edges (incoming and outgoing).\n"
"\n"
" **Time Complexity:** O(deg(v)) - proportional to the number of edges\n"
" connected to the node, not the whole graph.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_edges([#(1, 2, 10), #(2, 3, 20)])\n"
"\n"
" let graph = model.remove_node(graph, 2)\n"
" // Node 2 is removed, along with edges 1->2 and 2->3\n"
" ```\n"
).
-spec remove_node(graph(EHV, EHW), integer()) -> graph(EHV, EHW).
remove_node(Graph, Id) ->
Targets = successors(Graph, Id),
Sources = predecessors(Graph, Id),
New_nodes = gleam@dict:delete(erlang:element(3, Graph), Id),
New_out = gleam@dict:delete(erlang:element(4, Graph), Id),
New_in_cleaned = begin
gleam@list:fold(
Targets,
erlang:element(5, Graph),
fun(Acc_in, _use1) ->
{Target_id, _} = _use1,
yog@internal@util:dict_update_inner(
Acc_in,
Target_id,
Id,
fun gleam@dict:delete/2
)
end
)
end,
New_in = gleam@dict:delete(New_in_cleaned, Id),
New_out_cleaned = begin
gleam@list:fold(
Sources,
New_out,
fun(Acc_out, _use1@1) ->
{Source_id, _} = _use1@1,
yog@internal@util:dict_update_inner(
Acc_out,
Source_id,
Id,
fun gleam@dict:delete/2
)
end
)
end,
{graph, erlang:element(2, Graph), New_nodes, New_out_cleaned, New_in}.
-file("src/yog/model.gleam", 633).
?DOC(
" Gets everyone connected to the node, regardless of direction.\n"
" Useful for algorithms like finding \"connected connectivity.\"\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
" |> model.add_edge(from: 3, to: 1, with: 5)\n"
"\n"
" model.neighbors(graph, 1)\n"
" // => [#(2, 10), #(3, 5)]\n"
" ```\n"
).
-spec neighbors(graph(any(), ELR), integer()) -> list({integer(), ELR}).
neighbors(Graph, Id) ->
case erlang:element(2, Graph) of
undirected ->
successors(Graph, Id);
directed ->
Outgoing = successors(Graph, Id),
Incoming = predecessors(Graph, Id),
Out_ids = gleam@set:from_list(
gleam@list:map(Outgoing, fun gleam@pair:first/1)
),
gleam@list:fold(
Incoming,
Outgoing,
fun(Acc, _use1) ->
{In_id, _} = Incoming@1 = _use1,
case gleam@set:contains(Out_ids, In_id) of
true ->
Acc;
false ->
[Incoming@1 | Acc]
end
end
)
end.
-file("src/yog/model.gleam", 665).
?DOC(
" Returns all successor node IDs (without weights).\n"
" Convenient for traversal algorithms that only need the IDs.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
"\n"
" model.successor_ids(graph, 1)\n"
" // => [2]\n"
" ```\n"
).
-spec successor_ids(graph(any(), any()), integer()) -> list(integer()).
successor_ids(Graph, Id) ->
_pipe = Graph,
_pipe@1 = successors(_pipe, Id),
gleam@list:map(_pipe@1, fun(Edge) -> erlang:element(1, Edge) end).
-file("src/yog/model.gleam", 672).
?DOC(" Returns all predecessor node IDs (without weights).\n").
-spec predecessor_ids(graph(any(), any()), integer()) -> list(integer()).
predecessor_ids(Graph, Id) ->
_pipe = Graph,
_pipe@1 = predecessors(_pipe, Id),
gleam@list:map(_pipe@1, fun(Edge) -> erlang:element(1, Edge) end).
-file("src/yog/model.gleam", 679).
?DOC(" Returns all neighbor node IDs (without weights).\n").
-spec neighbor_ids(graph(any(), any()), integer()) -> list(integer()).
neighbor_ids(Graph, Id) ->
_pipe = Graph,
_pipe@1 = neighbors(_pipe, Id),
gleam@list:map(_pipe@1, fun(Edge) -> erlang:element(1, Edge) end).
-file("src/yog/model.gleam", 690).
?DOC(
" Returns the out-degree of a node.\n"
"\n"
" For undirected graphs, this returns the total degree.\n"
"\n"
" **Time Complexity:** O(1)\n"
).
-spec out_degree(graph(any(), any()), integer()) -> integer().
out_degree(Graph, Id) ->
_pipe = erlang:element(4, Graph),
_pipe@1 = gleam_stdlib:map_get(_pipe, Id),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:size/1),
gleam@result:unwrap(_pipe@2, 0).
-file("src/yog/model.gleam", 702).
?DOC(
" Returns the in-degree of a node.\n"
"\n"
" For undirected graphs, this returns the total degree.\n"
"\n"
" **Time Complexity:** O(1)\n"
).
-spec in_degree(graph(any(), any()), integer()) -> integer().
in_degree(Graph, Id) ->
_pipe = erlang:element(5, Graph),
_pipe@1 = gleam_stdlib:map_get(_pipe, Id),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:size/1),
gleam@result:unwrap(_pipe@2, 0).
-file("src/yog/model.gleam", 715).
?DOC(
" Returns the total degree of a node.\n"
"\n"
" For directed graphs, this is the sum of in-degree and out-degree.\n"
" For undirected graphs, self-loops count as 2.\n"
"\n"
" **Time Complexity:** O(1)\n"
).
-spec degree(graph(any(), any()), integer()) -> integer().
degree(Graph, Id) ->
case erlang:element(2, Graph) of
undirected ->
case gleam_stdlib:map_get(erlang:element(4, Graph), Id) of
{ok, Targets} ->
Base = maps:size(Targets),
case gleam@dict:has_key(Targets, Id) of
true ->
Base + 1;
false ->
Base
end;
{error, _} ->
0
end;
directed ->
in_degree(Graph, Id) + out_degree(Graph, Id)
end.
-file("src/yog/model.gleam", 749).
?DOC(
" Returns all node IDs in the graph.\n"
" This includes all nodes, even isolated nodes with no edges.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.all_nodes\n"
" // => [1, 2]\n"
" ```\n"
).
-spec all_nodes(graph(any(), any())) -> list(integer()).
all_nodes(Graph) ->
maps:keys(erlang:element(3, Graph)).
-file("src/yog/model.gleam", 754).
?DOC(" Returns all nodes data in the graph as a Dict.\n").
-spec nodes(graph(ENB, any())) -> gleam@dict:dict(integer(), ENB).
nodes(Graph) ->
erlang:element(3, Graph).
-file("src/yog/model.gleam", 759).
?DOC(" Gets the data associated with a node.\n").
-spec node(graph(ENH, any()), integer()) -> {ok, ENH} | {error, nil}.
node(Graph, Id) ->
gleam_stdlib:map_get(erlang:element(3, Graph), Id).
-file("src/yog/model.gleam", 764).
?DOC(" Gets the weight/data of an edge between two nodes.\n").
-spec edge_data(graph(any(), ENO), integer(), integer()) -> {ok, ENO} |
{error, nil}.
edge_data(Graph, Src, Dst) ->
_pipe = erlang:element(4, Graph),
_pipe@1 = gleam_stdlib:map_get(_pipe, Src),
gleam@result:'try'(
_pipe@1,
fun(_capture) -> gleam_stdlib:map_get(_capture, Dst) end
).
-file("src/yog/model.gleam", 778).
?DOC(
" Returns all edges in the graph as triplets `#(from, to, weight)`.\n"
"\n"
" For directed graphs, returns all edges.\n"
" For undirected graphs, returns each edge only once where `from <= to`.\n"
).
-spec all_edges(graph(any(), ENU)) -> list({integer(), integer(), ENU}).
all_edges(Graph) ->
case erlang:element(2, Graph) of
directed ->
gleam@dict:fold(
erlang:element(4, Graph),
[],
fun(Acc, From, Dests) ->
gleam@dict:fold(
Dests,
Acc,
fun(Acc@1, To, Weight) ->
[{From, To, Weight} | Acc@1]
end
)
end
);
undirected ->
gleam@dict:fold(
erlang:element(4, Graph),
[],
fun(Acc@2, From@1, Dests@1) ->
gleam@dict:fold(
Dests@1,
Acc@2,
fun(Acc@3, To@1, Weight@1) -> case From@1 =< To@1 of
true ->
[{From@1, To@1, Weight@1} | Acc@3];
false ->
Acc@3
end end
)
end
)
end.
-file("src/yog/model.gleam", 816).
?DOC(" Adds a node only if it doesn't already exist.\n").
-spec ensure_node(graph(EOE, EOF), integer(), EOE) -> graph(EOE, EOF).
ensure_node(Graph, Id, Data) ->
case gleam@dict:has_key(erlang:element(3, Graph), Id) of
true ->
Graph;
false ->
add_node(Graph, Id, Data)
end.
-file("src/yog/model.gleam", 825).
?DOC(
" Adds a node only if it doesn't already exist, using a function\n"
" to create the node data from the node ID.\n"
).
-spec ensure_node_with(graph(EOK, EOL), integer(), fun((integer()) -> EOK)) -> graph(EOK, EOL).
ensure_node_with(Graph, Id, Make) ->
case gleam@dict:has_key(erlang:element(3, Graph), Id) of
true ->
Graph;
false ->
add_node(Graph, Id, Make(Id))
end.
-file("src/yog/model.gleam", 836).
-spec do_add_directed_edge(graph(EOQ, EOR), integer(), integer(), EOR) -> graph(EOQ, EOR).
do_add_directed_edge(Graph, Src, Dst, Weight) ->
Out_update_fn = fun(Maybe_inner_map) -> case Maybe_inner_map of
{some, M} ->
gleam@dict:insert(M, Dst, Weight);
none ->
maps:from_list([{Dst, Weight}])
end end,
In_update_fn = fun(Maybe_inner_map@1) -> case Maybe_inner_map@1 of
{some, M@1} ->
gleam@dict:insert(M@1, Src, Weight);
none ->
maps:from_list([{Src, Weight}])
end end,
New_out = gleam@dict:upsert(erlang:element(4, Graph), Src, Out_update_fn),
New_in = gleam@dict:upsert(erlang:element(5, Graph), Dst, In_update_fn),
{graph, erlang:element(2, Graph), erlang:element(3, Graph), New_out, New_in}.
-file("src/yog/model.gleam", 801).
?DOC(" Adds an edge without checking if nodes exist (internal use).\n").
-spec add_edge_unchecked(graph(ENY, ENZ), integer(), integer(), ENZ) -> graph(ENY, ENZ).
add_edge_unchecked(Graph, Src, Dst, Weight) ->
Graph@1 = do_add_directed_edge(Graph, Src, Dst, Weight),
case erlang:element(2, Graph@1) of
directed ->
Graph@1;
undirected ->
do_add_directed_edge(Graph@1, Dst, Src, Weight)
end.
-file("src/yog/model.gleam", 219).
?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 in `graph.nodes`.\n"
" Use `add_edge_ensure` to auto-create missing nodes with a default value,\n"
" or `add_node` to explicitly add nodes before adding edges.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" graph\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
" // => Ok(graph)\n"
" ```\n"
"\n"
" ```gleam\n"
" graph\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
" // => Error(\"Node 1 does not exist\")\n"
" ```\n"
).
-spec add_edge(graph(EIB, EIC), integer(), integer(), EIC) -> {ok,
graph(EIB, EIC)} |
{error, binary()}.
add_edge(Graph, Src, Dst, Weight) ->
case {gleam@dict:has_key(erlang:element(3, Graph), Src),
gleam@dict:has_key(erlang:element(3, Graph), Dst)} of
{true, true} ->
{ok, add_edge_unchecked(Graph, Src, Dst, Weight)};
{false, false} ->
{error,
<<<<<<<<"Nodes "/utf8, (erlang:integer_to_binary(Src))/binary>>/binary,
" and "/utf8>>/binary,
(erlang:integer_to_binary(Dst))/binary>>/binary,
" do not exist"/utf8>>};
{false, _} ->
{error,
<<<<"Node "/utf8, (erlang:integer_to_binary(Src))/binary>>/binary,
" does not exist"/utf8>>};
{_, false} ->
{error,
<<<<"Node "/utf8, (erlang:integer_to_binary(Dst))/binary>>/binary,
" does not exist"/utf8>>}
end.
-file("src/yog/model.gleam", 264).
?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 before the edge is added. Nodes\n"
" that already exist are left unchanged.\n"
"\n"
" Always succeeds and returns a `Graph` (never fails).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Nodes 1 and 2 are created automatically with data \"unknown\"\n"
" model.new(model.Directed)\n"
" |> model.add_edge_ensure(from: 1, to: 2, with: 10, default: \"unknown\")\n"
" ```\n"
"\n"
" ```gleam\n"
" // Existing nodes keep their data; only missing ones get the default\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"Alice\")\n"
" |> model.add_edge_ensure(from: 1, to: 2, with: 5, default: \"anon\")\n"
" // Node 1 is still \"Alice\", node 2 is \"anon\"\n"
" ```\n"
).
-spec add_edge_ensure(graph(EIJ, EIK), integer(), integer(), EIK, EIJ) -> graph(EIJ, EIK).
add_edge_ensure(Graph, Src, Dst, Weight, Default) ->
_pipe = Graph,
_pipe@1 = ensure_node(_pipe, Src, Default),
_pipe@2 = ensure_node(_pipe@1, Dst, Default),
add_edge_unchecked(_pipe@2, Src, Dst, Weight).
-file("src/yog/model.gleam", 112).
?DOC(
" Creates a graph from a list of edges #(src, dst, weight).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let graph = model.from_edges(Directed, [#(1, 2, 10), #(2, 3, 5)])\n"
" ```\n"
).
-spec from_edges(graph_type(), list({integer(), integer(), EHJ})) -> graph(nil, EHJ).
from_edges(Graph_type, Edges) ->
gleam@list:fold(
Edges,
new(Graph_type),
fun(G, _use1) ->
{Src, Dst, Weight} = _use1,
add_edge_ensure(G, Src, Dst, Weight, nil)
end
).
-file("src/yog/model.gleam", 127).
?DOC(
" Creates a graph from a list of unweighted edges #(src, dst).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let graph = model.from_unweighted_edges(Directed, [#(1, 2), #(2, 3)])\n"
" ```\n"
).
-spec from_unweighted_edges(graph_type(), list({integer(), integer()})) -> graph(nil, nil).
from_unweighted_edges(Graph_type, Edges) ->
gleam@list:fold(
Edges,
new(Graph_type),
fun(G, _use1) ->
{Src, Dst} = _use1,
add_edge_ensure(G, Src, Dst, nil, nil)
end
).
-file("src/yog/model.gleam", 142).
?DOC(
" Creates a graph from an adjacency list #(src, List(#(dst, weight))).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let graph = model.from_adjacency_list(Directed, [#(1, [#(2, 10), #(3, 5)])])\n"
" ```\n"
).
-spec from_adjacency_list(
graph_type(),
list({integer(), list({integer(), EHQ})})
) -> graph(nil, EHQ).
from_adjacency_list(Graph_type, Adj_list) ->
gleam@list:fold(
Adj_list,
new(Graph_type),
fun(G0, _use1) ->
{Src, Edges} = _use1,
G1 = add_node(G0, Src, nil),
gleam@list:fold(
Edges,
G1,
fun(Graph, _use1@1) ->
{Dst, Weight} = _use1@1,
add_edge_ensure(Graph, Src, Dst, Weight, nil)
end
)
end
).
-file("src/yog/model.gleam", 300).
?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"
" Nodes that already exist are left unchanged.\n"
"\n"
" Always succeeds and returns a `Graph` (never fails).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Nodes 1 and 2 are created automatically with value that's the same as NodeId\n"
" model.new(model.Directed)\n"
" |> model.add_edge_with(from: 1, to: 2, with: 10, by: fn(x) { x })\n"
" ```\n"
"\n"
" ```gleam\n"
" // Existing nodes keep their data; only missing ones get the default\n"
" model.new(model.Directed)\n"
" |> model.add_node(1, \"1\")\n"
" |> model.add_edge_with(from: 1, to: 2, with: 5, by: fn(n) { int.to_string(n) <> \":new\" })\n"
" // Node 1 is still \"1\", node 2 is \"2:new\"\n"
" ```\n"
).
-spec add_edge_with(
graph(EIP, EIQ),
integer(),
integer(),
EIQ,
fun((integer()) -> EIP)
) -> graph(EIP, EIQ).
add_edge_with(Graph, Src, Dst, Weight, By) ->
_pipe = Graph,
_pipe@1 = ensure_node_with(_pipe, Src, By),
_pipe@2 = ensure_node_with(_pipe@1, Dst, By),
add_edge_unchecked(_pipe@2, Src, Dst, Weight).
-file("src/yog/model.gleam", 335).
?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"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_edges([\n"
" #(1, 2, 10),\n"
" #(2, 3, 5),\n"
" #(1, 3, 15),\n"
" ])\n"
" ```\n"
).
-spec add_edges(graph(EIV, EIW), list({integer(), integer(), EIW})) -> {ok,
graph(EIV, EIW)} |
{error, binary()}.
add_edges(Graph, Edges) ->
gleam@list:try_fold(
Edges,
Graph,
fun(G, _use1) ->
{Src, Dst, Weight} = _use1,
add_edge(G, Src, Dst, Weight)
end
).
-file("src/yog/model.gleam", 862).
-spec do_remove_directed_edge(graph(EOW, EOX), integer(), integer()) -> graph(EOW, EOX).
do_remove_directed_edge(Graph, Src, Dst) ->
New_out = case gleam_stdlib:map_get(erlang:element(4, Graph), Src) of
{ok, Targets} ->
gleam@dict:insert(
erlang:element(4, Graph),
Src,
gleam@dict:delete(Targets, Dst)
);
{error, _} ->
erlang:element(4, Graph)
end,
New_in = case gleam_stdlib:map_get(erlang:element(5, Graph), Dst) of
{ok, Sources} ->
gleam@dict:insert(
erlang:element(5, Graph),
Dst,
gleam@dict:delete(Sources, Src)
);
{error, _} ->
erlang:element(5, Graph)
end,
{graph, erlang:element(2, Graph), erlang:element(3, Graph), New_out, New_in}.
-file("src/yog/model.gleam", 466).
?DOC(
" Removes a directed edge from `src` to `dst`.\n"
"\n"
" For **directed graphs**, this removes the single directed edge from `src` to `dst`.\n"
" For **undirected graphs**, this removes the edges in both directions\n"
" (from `src` to `dst` and from `dst` to `src`).\n"
"\n"
" **Time Complexity:** O(1)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Directed graph - removes single directed edge\n"
" let assert Ok(graph) =\n"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
" let graph = model.remove_edge(graph, 1, 2)\n"
" // Edge 1->2 is removed\n"
" ```\n"
).
-spec remove_edge(graph(EKC, EKD), integer(), integer()) -> graph(EKC, EKD).
remove_edge(Graph, Src, Dst) ->
Graph@1 = do_remove_directed_edge(Graph, Src, Dst),
case erlang:element(2, Graph@1) of
directed ->
Graph@1;
undirected ->
do_remove_directed_edge(Graph@1, Dst, Src)
end.
-file("src/yog/model.gleam", 878).
-spec do_add_directed_combine(
graph(EPC, EPD),
integer(),
integer(),
EPD,
fun((EPD, EPD) -> EPD)
) -> graph(EPC, EPD).
do_add_directed_combine(Graph, Src, Dst, Weight, With_combine) ->
Update_fn = fun(Maybe_inner_map) -> case Maybe_inner_map of
{some, M} ->
New_weight = case gleam_stdlib:map_get(M, Dst) of
{ok, Existing} ->
With_combine(Existing, Weight);
{error, _} ->
Weight
end,
gleam@dict:insert(M, Dst, New_weight);
none ->
maps:from_list([{Dst, Weight}])
end end,
New_out = gleam@dict:upsert(erlang:element(4, Graph), Src, Update_fn),
New_in = gleam@dict:upsert(
erlang:element(5, Graph),
Dst,
fun(Maybe_m) -> case Maybe_m of
{some, M@1} ->
New_weight@1 = case gleam_stdlib:map_get(M@1, Src) of
{ok, Existing@1} ->
With_combine(Existing@1, Weight);
{error, _} ->
Weight
end,
gleam@dict:insert(M@1, Src, New_weight@1);
none ->
maps:from_list([{Src, Weight}])
end end
),
{graph, erlang:element(2, Graph), erlang:element(3, Graph), New_out, New_in}.
-file("src/yog/model.gleam", 416).
?DOC(
" Adds an edge, but if an edge already exists between `src` and `dst`,\n"
" it combines the new weight with the existing one using `with_combine`.\n"
"\n"
" The combine function receives `(existing_weight, new_weight)` and should\n"
" return the combined weight.\n"
"\n"
" Returns `Error` if either endpoint node doesn't exist in `graph.nodes`.\n"
"\n"
" **Time Complexity:** O(1)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let assert Ok(graph) =\n"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_edge(from: 1, to: 2, with: 10)\n"
" let assert Ok(graph) = model.add_edge_with_combine(graph, from: 1, to: 2, with: 5, using: int.add)\n"
" // Edge 1->2 now has weight 15 (10 + 5)\n"
" ```\n"
).
-spec add_edge_with_combine(
graph(EJU, EJV),
integer(),
integer(),
EJV,
fun((EJV, EJV) -> EJV)
) -> {ok, graph(EJU, EJV)} | {error, binary()}.
add_edge_with_combine(Graph, Src, Dst, Weight, With_combine) ->
case {gleam@dict:has_key(erlang:element(3, Graph), Src),
gleam@dict:has_key(erlang:element(3, Graph), Dst)} of
{true, true} ->
Graph@1 = do_add_directed_combine(
Graph,
Src,
Dst,
Weight,
With_combine
),
Result = case erlang:element(2, Graph@1) of
directed ->
Graph@1;
undirected ->
do_add_directed_combine(
Graph@1,
Dst,
Src,
Weight,
With_combine
)
end,
{ok, Result};
{false, false} ->
{error,
<<<<<<<<"Nodes "/utf8, (erlang:integer_to_binary(Src))/binary>>/binary,
" and "/utf8>>/binary,
(erlang:integer_to_binary(Dst))/binary>>/binary,
" do not exist"/utf8>>};
{false, _} ->
{error,
<<<<"Node "/utf8, (erlang:integer_to_binary(Src))/binary>>/binary,
" does not exist"/utf8>>};
{_, false} ->
{error,
<<<<"Node "/utf8, (erlang:integer_to_binary(Dst))/binary>>/binary,
" does not exist"/utf8>>}
end.
-file("src/yog/model.gleam", 916).
-spec do_add_edges_with(graph(EPI, EPJ), list({integer(), integer()}), EPJ) -> {ok,
graph(EPI, EPJ)} |
{error, binary()}.
do_add_edges_with(Graph, Edges, Weight) ->
gleam@list:try_fold(
Edges,
Graph,
fun(G, _use1) ->
{Src, Dst} = _use1,
add_edge(G, Src, Dst, Weight)
end
).
-file("src/yog/model.gleam", 362).
?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"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_simple_edges([\n"
" #(1, 2),\n"
" #(2, 3),\n"
" #(1, 3),\n"
" ])\n"
" ```\n"
).
-spec add_simple_edges(graph(EJE, integer()), list({integer(), integer()})) -> {ok,
graph(EJE, integer())} |
{error, binary()}.
add_simple_edges(Graph, Edges) ->
do_add_edges_with(Graph, Edges, 1).
-file("src/yog/model.gleam", 388).
?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"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_unweighted_edges([\n"
" #(1, 2),\n"
" #(2, 3),\n"
" #(1, 3),\n"
" ])\n"
" ```\n"
).
-spec add_unweighted_edges(graph(EJM, nil), list({integer(), integer()})) -> {ok,
graph(EJM, nil)} |
{error, binary()}.
add_unweighted_edges(Graph, Edges) ->
do_add_edges_with(Graph, Edges, nil).