Re: Determining if a directed graph is a rooted tree
- To: mathgroup at smc.vnet.net
- Subject: [mg28418] Re: Determining if a directed graph is a rooted tree
- From: Matthias Hertel <wir95cgu at studserv.uni-leipzig.de>
- Date: Mon, 16 Apr 2001 23:54:21 -0400 (EDT)
- References: <200104140528.BAA07447@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Tony,
In a tree, all nodes but the root have exactly one incident edge. (The
root has no incident edge.) This is a necessary condition for
tree-ness, but not sufficient. It's also met by a graph that contains
a tree and a few disconnected cycles. So we need to check if all nodes
are reachable from the supposed root node.
I use adjacency matrices as the representation: adj[[i, j]]==1 iff
there is an edge from node i to node j; otherwise it's 0.
The translation to Mathematica is quite straightforward:
children[n_?NumberQ, adj_?MatrixQ] := First /@ Position[adj[[n]], 1]
children[n : {_?NumberQ ..}, adj_?MatrixQ] :=
Join @@ (children[#, adj] & /@ n)
descendants[{}, _] := {}
descendants[n : {_?NumberQ ..}, adj_?MatrixQ] :=
Join[n, descendants[children[n, adj], adj]]
istree[adj_?MatrixQ] :=
Module[{n = Length[adj], in = Plus @@@ Transpose[adj]},
Count[in, 0] == 1 && Count[in, 1] == n - 1 &&
Length[descendants[First /@ Position[in, 0], adj]] == n]]]
Let's try it:
{ A->C, B->C } is not a tree, while { C->A, C->B } is:
In[12]:= g = {{0, 0, 1}, {0, 0, 1}, {0, 0, 0}};
In[13]:= istree[g]
Out[2]:= False
In[14]:= istree[Transpose[g]]
Out[14]= True
{ A->B, B->A, C } is one of the graphs that defeat the simple check
(counting incident edges):
In[22]:= g = {{0, 1, 0}, {1, 0, 0}, {0, 0, 0}};
In[23]:= Plus @@@ g
Out[23]= {1, 1, 0} (* looks good, but... *)
In[24]:= descendants[{3}, g]
Out[24]= {3} (* ...this does not. Therefore: *)
In[25]:= istree[g]
Out[25]= False
If you're going to use the descendants function somewhere else, take
care. If the part of the graph that it works on contains cycles, it
won't voluntarily stop recursing (that's why it's called last in the
istree function).
Regards,
Matthias
"Tony Duran" <radura0 at pop.uky.edu> writes:
> Dear MathGroup,
>
> I'm trying to find an algorithm that will determine if a directed graph is a
> rooted tree. Does anybody have any ideas?