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?