[erlang-questions] graphs and trees

[mats cronqvist]

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!

  mats