在 Erlang/Elixir 有向图中找到树的根

Question

我有以下超级简单的有向图树（代码是 Elixir）：

digraph = :digraph.new()
coords = [{0.0, 0.0}, {1.0, 0.0}, {1.0, 1.0}]
[v0, v1, v2] = (for c <- coords, do:   :digraph.add_vertex(digraph, c))
:digraph.add_edge(digraph, v0, v1)
:digraph.add_edge(digraph, v1, v2)

我们可以看到它是一棵树：

iex(82)> :digraph_utils.is_tree(digraph)
true

但是如何有效地找到树的顶点根呢？目前我正在这样做：

iex(83)> Enum.filter(:digraph.vertices(digraph), fn x -> :digraph.in_degree(digraph, x) == 0 end)
[{0.0, 0.0}]

这是找到根顶点最有效的方法，即找到没有内边的顶点吗？

Answer 1

有一个名为 :digraph_utils.arborescence_root/1 的函数可以解决问题。

对于您的示例，它将 return 以下内容：

iex(7)> :digraph_utils.arborescence_root(digraph)
{:yes, {0.0, 0.0}}

注意，如果我们添加另一条边从第一个顶点到最后一个顶点形成一个循环，那么它将失去它的根：

iex(8)> :digraph.add_edge(digraph, v2, v0)
iex(9)> :digraph_utils.arborescence_root(digraph)
:no

在效率方面，this built-in function does the same as your code，所以我猜你的问题的答案是不，没有更有效的方法。

希望对您有所帮助:)

在 Erlang/Elixir 有向图中找到树的根

Find root of tree in Erlang / Elixir digraph

erlang

elixir

digraphs