[erlang-questions] graphs and trees
Thu Dec 20 13:32:23 CET 2007
On Thu, 2007-12-20 at 09:34 +0000, French, Mike wrote:
> A graph is a tree if it's connected and nEdges = nVertices - 1
> For a simple test, but not necessarily most efficient, use
> digraph:no_edges/1 and digraph:no_vertices/1 then see if
> digraph_utils:components/1 returns a single element list:
> ( digraph:no_edges(G) == digraph:no_vertices(G)-1 ) and
> ( length(digraph_utils:components(G)) == 1 )
> Of course this does not guarantee that the edges are
> directed from the root outward to the leaves of the tree.
so a connected directed acyclic graph where nEdges - nVertices = 1 is
a tree, and vice versa(?)
in hindsight it's obvious even to me that every vertex, except the
root, has exactly one incoming edge.
More information about the erlang-questions