[erlang-questions] graphs and trees

[Torben Hoffmann]

On Dec 20, 2007 9:51 AM, mats cronqvist <mats.cronqvist@REDACTED> 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 :>
>
>  mats
>

Sorry for the late addition to the discussion (vacation clean-up of
mailbox), but the Wikipedia article about Trees defines exactly the
conditions for when a graph is indeed a tree:
http://en.wikipedia.org/wiki/Tree_(graph_theory)

Which approach that is the fastest depends on how the digraph module
represents grahps - I have not had the courage to peek inside...

Cheers,
Torben
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080101/23af771c/attachment.htm>