[erlang-questions] graphs and trees

French, Mike <>
Thu Dec 20 12:45:47 CET 2007


No, because is_acyclic(G) considers the direction of edges,
and a pair of nodes can be connected by multiple paths that do not form a
cycle.
What you have found is a Directed Acyclic Graph (DAG).

Mike

-----Original Message-----
From: 
[mailto:]On Behalf Of Richard
Carlsson
Sent: 20 December 2007 11:33
To: mats cronqvist
Cc: 
Subject: Re: [erlang-questions] graphs and trees


mats cronqvist wrote:
>   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 :>

If you get a single component from digraph_utils:components(Graph)
and digraph_utils:is_acyclic(Graph) returns true, you have a tree.

     /Richard


_______________________________________________
erlang-questions mailing list

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



More information about the erlang-questions mailing list