Packages
livebook
0.4.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
@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 grpah 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
end