Greetings,

     To my chagrin, I discovered that there was a bug in my Prufer code from yesterday (fortunatley, not in the VBScript itself). I was mostly interested in testing if my script works and didn't test the resulting code in Derive much. I tested it against 2 trees and it worked, so I declared success. The problem was that in some cases it overwrites the 2 used to indicate a node's removal. In retrospect, I should have just maintained a list of non-removed nodes and not tried to burden the adjacency matrix with two tasks. In any event, the (hopefully) debugged pseudo code and resulting Derive code is:

 

//This program takes a tree,T, on 1,2,..., n
//represented by its adjacncey matrix
//and returns a list of length n-2 of numbers in
//1,2,...,n

 

Prufer(T)

 

locals:
 n,L,i,j,k,s, found

 

begin
n:= Dim(T)
L:=[]
//main loop:

 

for i = 1 to n-2
  //locate the first leaf
  found := false
  j:=0
  while not(found)
    j:+1
    s:=0
    k:=1
    while s < 2 and k <=n
      s:+ T sub j sub k
      k:+1
    wend
    if(s=1,found:=true)
  wend
  // record the node adjacent to j
  // first find it
  k:=1
  while T sub j sub k /= 1 //haven't hit it yet
    k:+1
  wend
  L:=adjoin(k,L)
  //now remove the leaf j
  //we will mark the first position of its
  //row by 2 to indicate its removal
  //and then remove it from any other row
  T sub j sub 1 := 2
  for k = 1 to n
    if(T sub k sub j = 1,T sub k sub j := 0)
  next k
Next i

 

//the list has been built up in reverse
//order, so:

 

return reverse(L)

 

end

 

*********************************************
Derive Code: (remove before running script again!)
*********************************************

 

Prufer(T,n,L,i,j,k,s, found):=Prog(n:= Dim(T),L:=[],i:=1,Loop(If(i>n-2,Exit),found := false,j:=0,Loop(If(Not(not(found)),Exit),j:+1,s:=0,k:=1,Loop(If(Not(s < 2 and k <=n),Exit),s:+ T sub j sub k,k:+1),if(s=1,found:=true)),k:=1,Loop(If(Not(T sub j sub k /= 1 ),Exit),k:+1),L:=adjoin(k,L),T sub j sub 1 := 2,k:=1,Loop(If(k>n,Exit),if(T sub k sub j = 1,T sub k sub j := 0),k:+1),i:+1),return reverse(L))

 

For example, if T is [[0,0,1,0,0,0],[0,0,1,0,0,0],[1,1,0,1,0,0],[0,0,1,0,1,1],[0,0,0,1,0,0],[0,0,0,1,0,0]], corresponding to the tree

 

                1----3-----4-----5

                       |       |

                       2       6

 

then n=6 and the call Prufer(T) returns [3,3,4,4], as expected.

 

-John Coleman