Packages
livebook
0.9.0
0.19.8
0.19.7
0.19.6
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.19.0
0.18.6
0.18.5
0.18.4
0.18.3
0.18.2
0.18.1
0.18.0
0.17.3
0.17.2
0.17.1
0.17.0
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.14.0
0.14.0-rc.1
0.14.0-rc.0
0.13.3
0.13.2
0.13.1
0.13.0
0.12.1
0.12.0
0.11.4
0.11.3
0.11.2
0.11.1
0.11.0
0.10.0
0.9.3
0.9.2
0.9.1
0.9.0
0.8.2
0.8.1
0.8.0
0.7.2
0.7.1
0.7.0
0.6.3
0.6.2
0.6.1
0.6.0
0.5.2
0.5.1
0.5.0
0.4.1
0.4.0
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.2
0.1.1
0.1.0
Automate code & data workflows with interactive notebooks
Security advisory:
This version has known vulnerabilities.
View advisories
Current section
Files
Jump to
Current section
Files
lib/livebook/utils/graph.ex
defmodule Livebook.Utils.Graph do
@moduledoc false
@typedoc """
A bottom-up graph representation encoded as a map
of child-to-parent entries.
"""
@type t() :: %{node_id => node_id | nil}
@type t(node_id) :: %{node_id => node_id | nil}
@type node_id :: term()
@doc """
Finds a path between nodes `from_id` and `to_id`.
If the path exists, a top-down list of nodes is
returned including the extreme nodes. Otherwise,
an empty list is returned.
"""
@spec find_path(t(), node_id(), node_id()) :: list(node_id())
def find_path(graph, from_id, to_id) do
find_path(graph, from_id, to_id, [])
end
defp find_path(_graph, to_id, to_id, path), do: [to_id | path]
defp find_path(_graph, nil, _to_id, _path), do: []
defp find_path(graph, from_id, to_id, path),
do: find_path(graph, graph[from_id], to_id, [from_id | path])
@doc """
Finds graph leave nodes, that is, nodes with
no children.
"""
@spec leaves(t()) :: list(node_id())
def leaves(graph) do
children = MapSet.new(graph, fn {key, _} -> key end)
parents = MapSet.new(graph, fn {_, value} -> value end)
MapSet.difference(children, parents) |> MapSet.to_list()
end
@doc """
Reduces each top-down path in the graph.
Returns a list of accumulators, one for each leaf in the graph,
in no specific order.
"""
@spec reduce_paths(t(), acc, (node_id(), acc -> acc)) :: acc when acc: term()
def reduce_paths(graph, acc, fun) do
leaves = Livebook.Utils.Graph.leaves(graph)
cache = do_reduce(graph, leaves, acc, fun, %{})
Enum.map(leaves, &cache[&1])
end
defp do_reduce(_graph, [], _initial_acc, _fun, cache), do: cache
defp do_reduce(graph, [cell_id | cell_ids], initial_acc, fun, cache) do
if parent_id = graph[cell_id] do
case cache do
%{^parent_id => acc} ->
acc = fun.(cell_id, acc)
cache = put_in(cache[cell_id], acc)
do_reduce(graph, cell_ids, initial_acc, fun, cache)
_ ->
do_reduce(graph, [parent_id, cell_id | cell_ids], initial_acc, fun, cache)
end
else
acc = fun.(cell_id, initial_acc)
cache = put_in(cache[cell_id], acc)
do_reduce(graph, cell_ids, initial_acc, fun, cache)
end
end
end