[erlang-questions] graphs and trees

[French, Mike]

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.

Mike

-----Original Message-----
From: erlang-questions-bounces@REDACTED
[mailto:erlang-questions-bounces@REDACTED]On Behalf Of mats cronqvist
Sent: 20 December 2007 08:51
To: erlang-questions@REDACTED
Subject: [erlang-questions] graphs and trees


  so i've made a directad acyclic graph by calling various functions in
the digraph module. i theory, the resulting graph should be a tree. is
there some snazzy graph theory trick to show that the graph is indeed a
tree?
  disclaimer; i am by training a physicist, and as such uncomfortable
with all data structures more complicated than the fixed-size array. so
no big words please :>

  mats


_______________________________________________
erlang-questions mailing list
erlang-questions@REDACTED
http://www.erlang.org/mailman/listinfo/erlang-questions

Thales UK Ltd (Wells) DISCLAIMER: The information contained in this e-mail
is confidential. It may also be legally privileged. It is intended only for
the stated addressee(s) and access to it by any other person is
unauthorised. If you are not an addressee, you must not disclose, copy,
circulate or in any other way use or rely on the information contained in
this e-mail. Such unauthorised use may be unlawful. We may monitor all
e-mail communications through our networks. If you have received this e-mail
in error, please inform us immediately on +44 (0) 1749 672081 and delete it
and all copies from your system. We accept no responsibility for changes to
any e-mail which occur after it has been sent.  Attachments to this e-mail
may contain software viruses which could damage your system.  We therefore
recommend you virus-check all attachments before opening. A business of
Thales UK Ltd. Registered Office: 2 Dashwood Lang Road, The Bourne Business
Park, Addlestone, Weybridge, Surrey KT15 2NX Registered in England No.
868273