hyphy-common 2.2.7+dfsg-1 / usr / share / hyphy / TemplateBatchFiles / TreeTools.ibf

/*************************************************************************************/

function PostOrderAVL2StringDL (theAVL, doLengths)
{
	return PostOrderAVL2StringAnnotate (theAVL, doLengths, "");
}

/*************************************************************************************/

function PostOrderAVL2StringAnnotate (theAVL, doLengths,label)
{
	return PostOrderAVL2StringAnnotateAux (theAVL, doLengths, label, "[]");
}

/*************************************************************************************/

function PostOrderAVL2StringAnnotateAux (theAVL, doLengths, label, chars)
{
	_ost = "";
	_ost * 256;
	
	lastLevel = 0;
	treeSize  = Abs(theAVL);
	treeInfo  = theAVL[0];
	rootIndex = treeInfo["Root"];
	
	for (nodeIndex = 1; nodeIndex < treeSize; nodeIndex = nodeIndex + 1)
	{
        nodeInfo = theAVL[nodeIndex];
        myDepth = nodeInfo["Depth"];
        if (lastDepth < myDepth)
        {
            if (lastDepth)
            {
                _ost * ",";
            }
            for (pidx = lastDepth; pidx < myDepth; pidx = pidx + 1)
            {
                _ost * "(";
            }
        }
        else
        {
            if (lastDepth > myDepth)
            {
                for (pidx = myDepth; pidx < lastDepth; pidx = pidx + 1)
                {
                    _ost * ")";
                }				
            }
            else
            {
                _ost * ",";
            }
        }
        
        _ost * nodeInfo["Name"];
        
        if (Abs (label))
        {
            if (Abs(nodeInfo[label]))
            {
                _ost * (chars[0] + nodeInfo[label] + chars[1]);
            }
        }

        if (doLengths)
        {
            if (nodeIndex < treeSize - 1)
            {
                _ost * ":";
                _ost * (""+nodeInfo ["Length"]); 
            }
        }
        lastDepth = myDepth;
	}
	
	_ost * 0;
	return _ost;
}


/*************************************************************************************/

function PostOrderAVL2String (theAVL)
{
	return PostOrderAVL2StringDL(theAVL, 0);
}

/*************************************************************************************/

function PostOrderAVL2StringDistances (theAVL, distAVL)
{
	_ost = "";
	_ost * 256;
	
	lastLevel = 0;
	treeSize  = Abs(theAVL);
	treeInfo  = theAVL[0];
	rootIndex = treeInfo["Root"];
	
	for (nodeIndex = 1; nodeIndex < treeSize; nodeIndex+=1)
	{
        nodeInfo = theAVL[nodeIndex];
        myDepth = nodeInfo["Depth"];
        myName 	= nodeInfo["Name"];
        
        if (lastDepth < myDepth)
        {
            if (lastDepth)
            {
                _ost * ",";
            }
            for (pidx = lastDepth; pidx < myDepth; pidx = pidx + 1)
            {
                _ost * "(";
            }
        }
        else
        {
            if (lastDepth > myDepth)
            {
                for (pidx = myDepth; pidx < lastDepth; pidx = pidx + 1)
                {
                    _ost * ")";
                }				
            }
            else
            {
                _ost * ",";
            }
        }
        if (nodeIndex != rootIndex) {
            _ost * myName;
        }
        if (nodeIndex < treeSize - 1)
        {
            _ost * ":";
            _ost * (""+distAVL [myName]); 
        }
        lastDepth = myDepth;
	}
	
	_ost * 0;
	return _ost;
}

/*************************************************************************************/

function KillInternalZeroBranchLengths (treeAVL)
{
	treeSize   = Abs(treeAVL);
	if (treeSize == 3)
	{
		return "(" + (treeAVL[0])["Name"] + "," + (treeAVL[1])["Name"] + ")";
	}
	newTreeAVL = {};
	oldIndexMap= {treeSize,1};
	index2	   = {treeSize,1};
	newDAVL	   = {};
	newTreeAVL [0] = treeAVL[0];
	allDeleted = 0;
	for (nodeIndex = 1; nodeIndex < treeSize; nodeIndex = nodeIndex + 1)
	{
		newDAVL [(treeAVL[nodeIndex])["Name"]] = (treeAVL[nodeIndex])["Length"];
		
		if (Abs((treeAVL[nodeIndex])["Children"]) && Abs((treeAVL[nodeIndex])["Length"]) <= 1e-10 && (treeAVL[nodeIndex])["Parent"]) 
			/* zero internal branch */
		{
			oldIndexMap[nodeIndex] = -(treeAVL[nodeIndex])["Parent"];
			allDeleted			 = allDeleted + 1;
		}
		else
		{
			newTreeAVL [nodeIndex-allDeleted] = treeAVL[nodeIndex];
			oldIndexMap[nodeIndex]   			= nodeIndex-allDeleted;
			index2 [nodeIndex-allDeleted]		= nodeIndex;
		}
	}
	
	if (allDeleted)
	{
		markedIndices = {};
		for (nodeIndex = treeSize-1; nodeIndex>0; nodeIndex = nodeIndex - 1)
		{
			if (oldIndexMap [nodeIndex]<0)
			{
				markedIndices[nodeIndex] = 1;
				oldIndexMap[nodeIndex] = oldIndexMap[-oldIndexMap[nodeIndex]]; 
			}
		}
		treeSize = Abs (newTreeAVL);
		for (nodeIndex = 1; nodeIndex<treeSize; nodeIndex = nodeIndex + 1)
		{
			meParent = (newTreeAVL[nodeIndex])["Parent"];
			_cc		 = Abs((newTreeAVL[nodeIndex])["Children"]);
			if (_cc > 0)
			{
				newChildrenMap = {};
				for (_cci = 0; _cci < _cc; _cci = _cci+1)
				/* map children to new indices */
				{				
					_cn = ((newTreeAVL[nodeIndex])["Children"])[_cci];
					if (markedIndices[_cn] == 0)
					{
						newChildrenMap[Abs(newChildrenMap)] = oldIndexMap[_cn];
					}
				}
				((newTreeAVL[nodeIndex])["Children"]) = newChildrenMap;
			}
					
			if (meParent > 0)
			{
				meParentOI = meParent;
				meParent = oldIndexMap[meParent];
				(newTreeAVL[nodeIndex])["Parent"] = meParent;
				if (markedIndices[meParentOI])
				{
					/*
					fprintf (stdout, "Insert ", (newTreeAVL[nodeIndex])["Name"], " as a child of ", (newTreeAVL[meParent])["Name"], " index ", index2[nodeIndex], "(", oldIndexMap[index2[nodeIndex]], ",", nodeIndex,")\n");
					*/
					((newTreeAVL[meParent])["Children"])[Abs((newTreeAVL[meParent])["Children"])] = index2[nodeIndex];
				}
			}

		}
		
		
		for (nodeIndex = treeSize-1; nodeIndex>0; nodeIndex = nodeIndex - 1)
		{
			_cc		 = Abs((newTreeAVL[nodeIndex])["Children"]);
			if (_cc > 0)
			{
				_cd = (newTreeAVL[nodeIndex])["Depth"] + 1;
				for (_cci = 0; _cci < _cc; _cci = _cci+1)
				{				
					_cn =  ((newTreeAVL[nodeIndex])["Children"])[_cci];
					/*fprintf (stdout, (newTreeAVL[_cn])["Name"], ":", (newTreeAVL[_cn])["Depth"], "=>", _cd, "\n");*/
					(newTreeAVL[_cn])["Depth"] = _cd;
				}
			}
		}

		(newTreeAVL[0])["Root"] = treeSize-1;
	}
	
	return PostOrderAVL2StringDistances (newTreeAVL, newDAVL);
}


/*************************************************************************************/

function TreeAVL2String (treeAVL)
{
	rootNode = treeAVL[0];
	rootNode = rootNode["Root"];
	return subtreeAVLStr (rootNode,0,0);
}


/*************************************************************************************/

function subtreeAVLStr (nodeIndex,k,treeString)
{
	nodeInfo = treeAVL[nodeIndex];
	k = Abs(nodeInfo["Children"])-1;
	if (k>=0)
	{
		while (k>=0)
		{
			nodeInfo = treeAVL[nodeIndex];
			cNodes = nodeInfo["Children"];
			cNodes = cNodes[k];
			if (k < Abs(nodeInfo["Children"])-1)
			{
				ExecuteCommands("treeString=subtreeAVLStr (cNodes,k,treeString)+\",\"+treeString;");
			}
			else
			{
				ExecuteCommands("treeString=subtreeAVLStr (cNodes,k,treeString)+\")\";");
			}
			k=k-1;
		}
		return "("+treeString;
	}
	else
	{
		callLevel = callLevel - 1;
		return nodeInfo["Name"];
	}
}

/*************************************************************************************/

function InsertANode (theAVL&,insertAt,newNodeName)
{
	nodeInfo = theAVL[insertAt];
	if (Abs(nodeInfo))
	{
		nparent = nodeInfo["Parent"];
		if (nparent > 0)
		{
			lastIndex = Abs(theAVL);
			myDepth = nodeInfo["Depth"];
			newParentNode = {};
			newParentNode ["Name"] = "Node"+lastIndex;
			newParentNode ["Parent"] = nparent;
			newParentNode ["Depth"] = myDepth;
			
			newChildNode = {};
			newChildNode ["Name"] = newNodeName;
			newChildNode ["Parent"] = lastIndex;
			newChildNode ["Depth"] = myDepth + 1;
			
			pChildren = {};
			pChildren [0] = insertAt;
			pChildren [1] = lastIndex+1;
			newParentNode ["Children"] = pChildren;
			
			theAVL[lastIndex] = newParentNode;
			theAVL[lastIndex+1] = newChildNode;

			/* update the parent*/

			nodeInfo ["Parent"] = lastIndex;
			theAVL[insertAt] = nodeInfo;
			
			/* update the list of children at the parent node*/
			
			parentInfo = theAVL[nparent];
			parentChildren = parentInfo["Children"];
			
			for (nic = Abs(parentChildren)-1; nic >= 0; nic = nic-1)
			{
				if (parentChildren[nic] == insertAt)
				{
					break;
				}
			}

			parentChildren[nic] = lastIndex;
			parentInfo["Children"] = parentChildren;
			theAVL[nparent] = parentInfo;
			
			/* now update the depths at new NodeName and all of its children */
			
			nodeCache    = {};
			nodeCache[0] = insertAt;
			cacheIndex   = 0;
			
			while (cacheIndex <= Abs(nodeCache))
			{
				nparent 			= nodeCache[cacheIndex];
				nodeInfo 			= theAVL[nparent];
				nodeInfo["Depth"] 	= nodeInfo["Depth"] + 1;
				theAVL[nparent] 	= nodeInfo;
				nodeChildren 		= nodeInfo["Children"];
				for (nic = Abs(nodeChildren)-1; nic >=0; nic = nic-1)
				{
					nodeCache [Abs(nodeCache)] = nodeChildren[nic];
				}
				cacheIndex = cacheIndex + 1;
			}
			
			nodeCache = 0;
		}
	}
	return 0;
}

/*************************************************************************************/

function	ModifyDepth (nIndex, modAmount)
{
	nodeInfo = theAVL[nIndex];
	nodeInfo ["Depth"] = nodeInfo ["Depth"] + modAmount;
	theAVL[nIndex] = nodeInfo;

}

/*************************************************************************************/

function	echoAVL (anAVL)
{
	for (k=1; k<Abs(anAVL); k=k+1)
	{
		nodeInfo 			= anAVL[k];
		myChildren			= nodeInfo["Children"];
		if (Abs(myChildren))
		{
			fprintf (stdout, "Index ", k, ":", nodeInfo["Name"], " : parent = ", nodeInfo["Parent"], " children:");
			for (k2 = 0; k2 < Abs(myChildren); k2=k2+1)
			{
				fprintf (stdout,"\t", myChildren[k2]);
			}
			fprintf (stdout, " depth: ", nodeInfo["Depth"], "\n");
		
		}
		else
		{
			fprintf (stdout, "Index ", k, ":", nodeInfo["Name"], " : parent = ", nodeInfo["Parent"], " children: none, depth: ", nodeInfo["Depth"], "\n");
		}
	}
	return 0;
}

/*************************************************************************************/

function	selectATreeBranch (treeID, title)
{
	ExecuteCommands ("internalNodes = BranchCount(`treeID`);");
	ExecuteCommands ("leafNodes     = TipCount(`treeID`);");

	choiceMatrix  = {internalNodes+leafNodes,2};
	
	for (bc=0; bc<internalNodes; bc=bc+1)
	{
		ExecuteCommands ("choiceMatrix[bc][0] = BranchName(`treeID`,bc);choiceMatrix[bc][1] = \"Internal Branch Rooting \" + `treeID`[bc];");
	}
	
	for (bc=0; bc<leafNodes; bc=bc+1)
	{
		ExecuteCommands ("choiceMatrix[bc+internalNodes][0] = TipName(`treeID`,bc);");
		choiceMatrix[bc+internalNodes][1] = "Terminal branch endin in " + choiceMatrix[bc+internalNodes][0];
	}
	
	mxTreeSpec = {5,1};
	mxTreeSpec [0] = treeID;
	mxTreeSpec [1] = "8240";
	mxTreeSpec [2] = "10,40,-10,-175,1";
	mxTreeSpec [3] = "";
	mxTreeSpec [4] = "";
	OpenWindow (TREEWINDOW, mxTreeSpec);
	
	ChoiceList  (bOption,title,1,NO_SKIP,choiceMatrix);
	
	if (bOption < 0)
	{
		return "";
	}
	return choiceMatrix[bOption][0];
}

/*************************************************************************************/

function	computeTreeSplits (treeID,mirror,leafMap)
{
	ExecuteCommands ("_treeAVL		= `treeID`^0;");
	ExecuteCommands ("_leafNodes     = TipCount(`treeID`);");
	_tipMap			= {};
	_splitMap		= {};
	_splitTemplate = {_leafNodes,1};
	_hasLeafMap	   = Abs (leafMap);
	
	for (_k = 1; _k < Abs(_treeAVL); _k = _k+1)
	{
		if (Abs((_treeAVL[_k])["Children"]) == 0)
		{
			if (_hasLeafMap)
			{
				_tipMap [_k] = leafMap [(_treeAVL[_k])["Name"]];
			}
			else
			{
				_tipMap [_k] = Abs(_tipMap);
			}
		}
		(_treeAVL[_k])["Split"]		   = _splitTemplate;
	}
	
	
	for (_k = 1; _k < Abs(_treeAVL); _k = _k+1)
	{
		_pc = (_treeAVL[_k])["Parent"];
		if (_pc)
		{
			_cc = Abs((_treeAVL[_k])["Children"]);
			if (_cc)
			{
				_mySplit                 = ((_treeAVL[_k])["Split"])["_MATRIX_ELEMENT_VALUE_>0"];
				(_treeAVL[_pc])["Split"] = (_treeAVL[_pc])["Split"] + _mySplit;
			}
			else
			{
				((_treeAVL[_k])["Split"])[_tipMap[_k]] = 1;
				_mySplit = (_treeAVL[_k])["Split"];
				((_treeAVL[_pc])["Split"])[_tipMap[_k]] = 1;
			}
			_splitMap[_mySplit]		  = (_treeAVL[_k])["Name"];
		}
	}
	
	
	_uniqueSplits = Rows(_splitMap);
	_splitStrings = {};
	for (_k = 0; _k < Abs(_splitMap); _k = _k+1)
	{
		_stringKey = ""; _stringKey * 128;
		_stringKey2 = ""; _stringKey2 * 128;
		ExecuteCommands ("_thisKey   = " + _uniqueSplits[_k]);
		for (_k2 = 0; _k2 < _leafNodes; _k2 = _k2 + 1)
		{
			if (_thisKey[_k2])
			{
				_stringKey * "*";
				_stringKey2 * "-";
			}
			else
			{
				_stringKey * "-";
				_stringKey2 * "*";
			}
		}
		_stringKey * 0;_stringKey2 * 0;
		_splitStrings [_stringKey] = _splitMap[_uniqueSplits[_k]];
		if (mirror)
		{
			_splitStrings [_stringKey2] = _splitStrings [_stringKey];
		}
	}
	DeleteObject (_splitMap);
	return _splitStrings;
}

/*************************************************************************************/

/* 
   return the most recent common ancestor for a group 
   of nodes in an AVL; returns the index of the MRCA
*/

function	_findMRCA (treeAVL, nodeIDList)
{
	_nodeCount	 = Rows(nodeIDList)*Columns(nodeIDList);
	
	if (_nodeCount)
	{
		nodeIDList    = nodeIDList % 0;
		_highestNode  = (treeAVL[nodeIDList[0]])["Depth"];
		_currentDepth = _highestNode;
		_lastNode	  = nodeIDList[_nodeCount-1];
		for (_nodeIterator = nodeIDList[0]+1; _nodeIterator <= _lastNode; 
											  _nodeIterator  = _nodeIterator + 1)
		{
			_currentDepth = (treeAVL[_nodeIterator])["Depth"];
			if (_currentDepth < _highestNode)
			{
				_highestNode   = _currentDepth;
			}
		}
				
		for (; _nodeIterator <= Abs(treeAVL); _nodeIterator = _nodeIterator+1)
		{
			if ((treeAVL[_nodeIterator])["Depth"] < _highestNode)
			{
				return _nodeIterator;
			}
		} 
		
	}
	
	return Abs(treeAVL)-1;
}

/*************************************************************************************/
/* 
  	use parsimony to reconstruct ancestral states based on leaf AVL labels 
  	return the number of substitutions
*/

function _parsimonyAncestralMapping (treeAVL&, label)
{
	uniqueLabels = {};
	idToLabel	 = {};
	for (_nodeIterator = 1; _nodeIterator < Abs (treeAVL); _nodeIterator = _nodeIterator + 1)
	{
		isLeaf = Abs((treeAVL[_nodeIterator])["Children"]) == 0;
		if (isLeaf)
		{
			isLeaf = (treeAVL[_nodeIterator])[label];
			if (uniqueLabels[isLeaf] == 0)
			{
				uniqueLabels [isLeaf]     = 1+Abs(uniqueLabels);
				idToLabel[Abs(idToLabel)] = isLeaf;
			}
		}
	}

	assignmentMatrices = {};
	kindCount		   = Abs (uniqueLabels);
	
	for (_nodeIterator = 1; _nodeIterator < Abs (treeAVL); _nodeIterator = _nodeIterator + 1)
	{
		aMx = {2,kindCount};
		s2  = uniqueLabels[(treeAVL[_nodeIterator])[label]]-1;
		for (k=0; k<kindCount; k=k+1)
		{
			aMx[0][k] = s2;
			aMx[1][k] = 1-(k==s2);	
		}
		assignmentMatrices [(treeAVL[_nodeIterator])["Name"]] = aMx;
	}

	for (_nodeIterator = 1; _nodeIterator < Abs (treeAVL); _nodeIterator = _nodeIterator + 1)
	{
		nodeInfo 		= treeAVL[_nodeIterator];
		nodeChildren	= nodeInfo ["Children"];
		cCount			= Abs(nodeChildren);
		
		if (cCount)
		{
			localMatrices = {};
			
			nodeName = nodeInfo["Name"];
			
			for (s1 = 0; s1<cCount; s1=s1+1)
			{
				localMatrices[s1] = assignmentMatrices[(treeAVL	 [nodeChildren[s1]])  ["Name"]];
			}
			
			twoWay = {kindCount,1};
			
			for (s2 = 0; s2 < kindCount; s2 = s2+1)
			{
				lc = 0;
				for (s3 = 0; s3<cCount; s3=s3+1)
				{
					lc  = lc + (localMatrices[s3])[1][s2];
				}
				twoWay[s2] = lc;
			}
						
			if (nodeInfo["Parent"])
			{
				aMx = {2,kindCount};
				
				for (s2 = 0; s2 < kindCount; s2 = s2+1)
				{
					minV = 1e100;
					minI = 0;
					
					for (s3 = 0; s3 < kindCount; s3 = s3+1)
					{
						aCost = (s3!=s2) + twoWay[s3];
						if (minV > aCost)
						{
							minV  = aCost;
							minI  = s3;
						}	
					}
					
					aMx[0][s2] = minI;
					aMx[1][s2] = minV;
				}
				
				assignmentMatrices [nodeName] = aMx;
			}
			else
			{
				totalCost = 1e100;
				rootState = 0;
				
				for (s2 = 0; s2 < kindCount; s2 = s2+1)
				{
					if (twoWay[s2] < totalCost)
					{
						totalCost = twoWay[s2];
						rootState = s2;
					}	
				}
				(treeAVL[_nodeIterator])[label] = idToLabel[rootState];
			}
		}
	}
	
	for (_nodeIterator = Abs (treeAVL)-1; _nodeIterator >=1 ; _nodeIterator = _nodeIterator - 1)
	{
		nodeInfo 		= treeAVL[_nodeIterator];
		nodeChildren	= nodeInfo ["Children"];
		
		if (Abs(nodeChildren))
		{			
			nodeName   = nodeInfo["Name"];
			nodeParent = nodeInfo["Parent"];
			if (nodeParent)
			{
				aMx							    = assignmentMatrices [nodeName];
				(treeAVL[_nodeIterator])[label] = idToLabel[aMx[0][uniqueLabels[(treeAVL[nodeParent])[label]]-1]];
			}
		}
	}	

	assignmentMatrices = 0;
	return totalCost;
}



/*************************************************************************************/
/* 
  	Center of Tree (COT) calculation 
*/

function ComputeCOT (_treeID, _filePath)
/* IN 	: the identifier of an existing tree variable (String)
		  _filePath : if not an empty string, write a PostScript image with this tree
		  			  to the given path
		  			  
   OUT	: an associative array with four entries
   		  "Branch" 		- the branch where the COT resides
   		  				  branch ENDS at the node whose value is returned 
   		  				  
   		  "Split"  		- how far up the branch the COT is, measured in the same units as branch lengths
   		  				  from the END of the branch (i.e node) 
   		  				  
   		  "COTTree"		- tree rerooted at the COT
   		  
   		  "Distances"	- mean squared distance from the COT to all leaves		  
*/ 
{
	_power = 2;
					 /* '2' is the power of the distance function to 
						   minimize - i.e. least squares in this case */
	ExecuteCommands (
	"_cot = Min ("+_treeID+",_power);");
	
	_returnList = {};
	_returnList ["Branch"] = _cot["COT_NODE"];
	_returnList ["Split"]  = _cot["COT_SPLIT"];
	_meanD = 0;
	_keys  = Rows(_cot["COT_TO_NODE"]); 
		/* _cot["COT_TO_NODE"] is an associative array
		   mapping tree nodes to the total distance from COT (linear distance)
		*/ 

	for (_k = 0; _k < Columns(_keys); _k=_k+1)
	{
		_meanD = _meanD + (_cot["COT_TO_NODE"])[_keys[_k]]^_power;
	}

	_returnList     ["Distances"]  = _meanD/Columns(_keys);
	/* reroot the tree at the COT branch */
	ExecuteCommands ("_rerootedTree = RerootTree ("+_treeID+", \""+_returnList ["Branch"]+"\");");
	/* hackish lines below split the root branch into appropriate bits */
	
	ACCEPT_ROOTED_TREES = 1;
	UseModel (USE_NO_MODEL);
	Tree _temp = _rerootedTree;
	_tempA = _temp^0; /* this converts the tree into a post-order list of nodes as an associative array; 
						print it to see the structure */					       
	_rootID	   = (_tempA[0])["Root"];
	_dist	   = {};
	for (_k = 1; _k < Abs (_tempA); _k = _k + 1)
	{
		if ((_tempA[_k])["Parent"] == _rootID)
		{
			if (_k == _rootID - 1)
			{
				_dist [(_tempA[_k])["Name"]] = _cot["COT_SPLIT"];
			}
			else
			{
				_dist [(_tempA[_k])["Name"]] = _cot["COT_BRANCH_LENGTH"]-_cot["COT_SPLIT"];			
			}
		}
		else
		{
			_dist [(_tempA[_k])["Name"]] = (_tempA[_k])["Length"];
		}
	}
	
	_returnList["COTTree"] = PostOrderAVL2StringDistances (_tempA,_dist);
	
	/* make a postscript file if needed */
	if (Abs(_filePath))
	{
		TREE_OUTPUT_OPTIONS = {};
		nodeSpec = {};
		nodeSpec ["TREE_OUTPUT_BRANCH_SPLIT"]		= _cot["COT_SPLIT"]/_cot["COT_BRANCH_LENGTH"];	
		TREE_OUTPUT_OPTIONS [_cot["COT_NODE"]] 		= nodeSpec;
		ExecuteCommands 							("psString = PSTreeString ("+_treeID+",\"STRING_SUPPLIED_LENGTHS\",{{-1,-1}});");
		fprintf 									(_filePath, CLEAR_FILE, psString);
	}

	return _returnList;
	
}


/*************************************************************************************/
/* 
    Computes the distance from each node to the root of the tree.
    By default, uses the "Length" key, but this can be redefined by passing an argument  
*/

function PathDistanceToRoot (_treeAVL, _distanceKey)
/* IN 	: the identifier of a post-order tree AVL (dictionary)
		  _distanceKey : if not an empty string, use this key to retrieve branch lengths
          		  			  
   OUT	: an associative array keyed on branch names with paths stored as values
                
*/ 
{
    _distances = {};
    
    if (Abs (_distanceKey) == 0)
    {
        _distanceKey = "Length";
    }
    
    for (_k = Abs (_treeAVL)-2; _k > 0; _k = _k-1)
    {
        _nodeName   = (_treeAVL[_k])["Name"];
        _distances[_nodeName] = _distances[(_treeAVL[(_treeAVL[_k])["Parent"]])["Name"]] + (_treeAVL[_k])[_distanceKey];
    }
    
    return _distances;
}