[erlang-questions] graphs and trees

mats cronqvist mats.cronqvist@REDACTED
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.

  thanks mike!


More information about the erlang-questions mailing list