erlang - 在 Erlang / Elixir digraph 中查找树的根

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可以解决这个问题。

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

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

在效率方面，这个内置函数和你的代码一样，所以我猜你的问题的答案是否定的，没有更有效的方法。

我希望这有帮助 ：）