Packages
livebook
0.17.1
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
Current section
Files
Jump to
Current section
Files
lib/livebook/utils/graph.ex
defmodule Livebook.Utils.Graph do
@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