Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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?


  • Prev by Date: Can Mathematica be used as expert system (rule-based computations like CLIPS?)
  • Next by Date: circular plot question
  • Previous by thread: Re: Determining if a directed graph is a rooted tree
  • Next by thread: conditionals during nonlinear regression