Найти корень дерева в эрланге / эликсире орграфа

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

С точки зрения эффективности, эта встроенная функция работает так же, как ваш код поэтому я думаю, что ответ на ваш вопрос нет, не существует более эффективного способа сделать это .

Надеюсь, это поможет:)