次の非常に単純な有向グラフ ツリーがあります (コードは 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}]
これは、ルート頂点を見つける最も効率的な方法ですか、つまり、エッジのない頂点を見つけることですか?