Найти корень дерева в орграфе Erlang / Elixir

У меня есть следующее супер простое дерево орграфов (код 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}]

Является ли это наиболее эффективным способом нахождения корневой вершины, т. е. путем нахождения вершины без входящих ребер?


elixir digraphs erlang
person Thomas Browne    schedule 24.09.2018    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Есть функция под названием :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

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

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

person Alex de Sousa    schedule 24.09.2018