tree2tree.java

生物物种进化历程的演示

/*
   Copyright (c) 2002 Compaq Computer Corporation
   
   SOFTWARE RELEASE
   
   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:
   
   - Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.
   
   - Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in the
     documentation and/or other materials provided with the distribution.
   
   - Neither the names of Compaq Research, Compaq Computer Corporation
     nor the names of its contributors may be used to endorse or promote
     products derived from this Software without specific prior written
     permission.
   
   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
   IN NO EVENT SHALL COMPAQ COMPUTER CORPORATION BE LIABLE FOR ANY CLAIM,
   DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
   OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
   THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

package TreeJuxtaposer;

import AccordionTreeDrawer.*;
//import AccordionTreeDrawer.AccordionTreeDrawer;
//import AccordionTreeDrawer.Tree;
//import AccordionTreeDrawer.TreeNode;

import java.util.*;


/**
 * Tree2Tree does the precomputation for each pair of trees. The two
 * precomputation tasks are computing the best corresponding node for
 * each node and building the range query data structures.
 *
 * @author  Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou
 * @version 
 * @see     AccordionDrawer.Tree
 * @see     TreeJuxtaposer.RangeTree
 */

class Tree2Tree {

	// the trees being compared
    Tree treeA, treeB;

	// for X2Y: an entry for each node in X if the subtree under X is a forest in Y
	Hashtable A2B, B2A;

    /**
     * The hashmaps that store the best matchings. A2B (B2A) stores
     * the best match of treeB (treeA) node to treeA (treeB).
     */

    // the vector that stores the best corresponding nodes for
    // different levels. each element of the vector is a hashmap that
    // is indexed by nodes
    Vector bestA2B, bestB2A;

    // to deal with edge weights and leaves
    float epsilon = 0.1f;

    //    HashMap bestA2B, bestB2A;
//    RangeTree rangeAB, rangeBA;
    
    // do all the necessary preprocessing
    Tree2Tree(Tree t1, Tree t2, int eL) {
	treeA = t1;
	treeB = t2;
	long start, current;
	bestA2B = new Vector(eL);
	bestB2A = new Vector(eL);

	start = System.currentTimeMillis();
	// initialization the data structures for answering the
	// queries of getBestCorrNode and isRangeInRange.
	computeBestMatch(treeA, treeB, bestA2B, eL);
	current = System.currentTimeMillis();
	System.out.println("best match 1 total preprocessed: "+(current-start)/1000.0f+" sec");
	start = current;
	computeBestMatch(treeB, treeA, bestB2A, eL);
	current = System.currentTimeMillis();
	System.out.println("best match 2 total preprocessed: "+(current-start)/1000.0f+" sec");
	start = current;
	
	// initialize the data structure for rectangular range searching
//	rangeAB = new RangeTree(treeA, treeB, this);
//	rangeBA = new RangeTree(treeB, treeA, this);
//	current = System.currentTimeMillis();
//	System.out.println("range tree preprocessed: "+(current-start)/1000.0f+" sec");

    }

	/**
	 * clean method, called when a tree is deleted
	 * @see TreePairs.removeTree
	 *
	 */
		public void close(){
		   A2B.clear();
		   B2A.clear();	
		   bestA2B.clear();
		   bestB2A.clear();
//		   this = null;
		}

	private void addNodeToForest(TreeNode node, ArrayList array, Hashtable hash)
	{
		Integer nodeInteger = new Integer(node.key);
		if (hash.get(nodeInteger) == null)
		{
			array.add(nodeInteger);
			hash.put(nodeInteger, node);
		}
	}
	private void removeNodeFromForest(TreeNode node, ArrayList array, Hashtable hash)
	{
		Integer nodeInteger = new Integer(node.key);
		if (hash.get(nodeInteger) == null)
		{
			array.remove(nodeInteger);
			hash.remove(nodeInteger);
		}
	}

	/*
	 * return an ArrayList of a reduced number of elements from ArrayList
	 * based on the number of leaves; bigger subtrees are kept, ties broken
	 * by taking any subtree with maximum number of leaves not already in forest
	 */
	private ArrayList reduceNodeListToCutoff(ArrayList node, int cutoff)
	{
		//System.out.println("reducing nodelist to cutoff");
		int subtreeSize[] = new int[node.size()];
		for (int i = 0; i < node.size(); i++)
		{
			subtreeSize[i] = ((TreeNode)node.get(i)).numberLeaves;
		}
		Arrays.sort(subtreeSize); // sort array in ascending order
		int subtreeSizeCutoff = subtreeSize[node.size() - cutoff] + 1; // find (cutoff + 1) subtree size
		ArrayList returnList = new ArrayList();
		for (int i = 0; i < node.size(); i++)
		{
			TreeNode currentNode = (TreeNode)node.get(i);
			if (currentNode.numberLeaves >= subtreeSizeCutoff)
				returnList.add(currentNode);
		}
		subtreeSizeCutoff--;
		for (int i = 0; i < node.size() && returnList.size() < cutoff; i++)
		{
			TreeNode currentNode = (TreeNode)node.get(i);
			if (currentNode.numberLeaves == subtreeSizeCutoff)
				returnList.add(currentNode);
		}
		return returnList;
	}
	
	private void computeForest(Hashtable X2Y, Tree treeX, Tree treeY,
		AccordionTreeDrawer atdY, int cutoff)
	{
		//posorder = children first, then parents
		for (TreeNode nX = treeX.posorderStartNode; nX != null; nX = nX.posorderNext)
		{
			ArrayList currListX = null;
			TreeNode nY = getBestCorrNode(treeX, nX, treeY, 0);
			if (nY == null) // no BCN for nX, give up
				continue;
			Hashtable nXHash = null;

			if (!nX.isLeaf()) // add children of nY to currListY
			//  (iff child is BCN of a descendent of nX)
			{
				currListX = new ArrayList();
				nXHash = new Hashtable();
				addNodeToForest(nY, currListX, nXHash);
				// add nY reference (sort later)
				for (int i = 0; i < nX.numberChildren(); i++) {
					TreeNode nXChild = nX.getChild(i);
					TreeNode nYChild = getBestCorrNode(treeX, nXChild, treeY, 0);
					ArrayList nXChildList = (ArrayList)X2Y.get(nXChild);
					if (nXChildList != null) {
						for (int j = 0; j < nXChildList.size(); j++) // go through forest of nXChild
						{
							TreeNode nYj = (TreeNode)nXChildList.get(j);
							if (nY.getMin() > nYj.getMin() || nY.getMax() < nYj.getMax())
							// nY is not an ancestor of nYj; nYj could be an ancestor of nY
								addNodeToForest(nYj, currListX, nXHash);
							if (nYj.getMin() <= nY.getMin() && nYj.getMax() >= nY.getMax())
							// nYj is an ancestor of nY, remove nY
								removeNodeFromForest(nY, currListX, nXHash);
						}
					}
					// add child
					if (nYChild != null && !nY.isAncestorOf(nYChild))
						addNodeToForest(nYChild, currListX, nXHash);
						
					// reduce (to cutoff) large forests under children of current node
					if (nXChildList != null && nXChildList.size() > cutoff)
					{
						ArrayList newNXChildList = reduceNodeListToCutoff(nXChildList, cutoff);
						X2Y.remove(nXChild);
						X2Y.put(nXChild, newNXChildList);
					}
				}
			}
			ArrayList finalArrayX = new ArrayList(); // final forest calculation
			
			// sort nBChildList by key
			if (currListX != null) {
				Object tempObjects[] = currListX.toArray();
				Integer tempArray[] = new Integer[tempObjects.length];
				for (int i = 0; i < tempObjects.length; i++)
				  tempArray[i] = (Integer)tempObjects[i];
				Arrays.sort(tempArray);
				for (int i = 0; i < tempArray.length; i++)
				{
					TreeNode node = (TreeNode)nXHash.get(tempArray[i]);
					if (node != null)
					{
						finalArrayX.add(node);
						nXHash.remove(tempArray[i]);
					}
				}
			}
			
			// add finalArrayX to X2Y referenced by nX if finalArrayX has more than one element
			if (finalArrayX != null && finalArrayX.size() > 1)
				X2Y.put(nX, finalArrayX);
		} // end of current nX
	}


	/*
	 * preprocessing: calculate and store forests that correspond to subtrees
	 * A2B/B2A: hash tables that map nodes (roots of subtrees) from A/B to forests of nodes (subtrees) in B/A
	 * all work is done in computeForest
	 */
	public void subtree2Forest(AccordionTreeDrawer atdA, AccordionTreeDrawer atdB, int eL)
	{
		final int cutoff = 100; // allow at most "cutoff" items in a node's forest array
		float start = System.currentTimeMillis();
		A2B = new Hashtable();
		computeForest(A2B, treeA, treeB, atdB, cutoff);
		B2A = new Hashtable();
		computeForest(B2A, treeB, treeA, atdA, cutoff);
		float time = (System.currentTimeMillis() - start) / 1000;
		System.out.println("Time to preprocess forest pair: " + time);
	}

    /**
     * Computes the node in Tree "other" whose set of descendant
     * leaves best matches that of TreeNode n in Tree "source"
     * 
     * The best match is the node n' maximizing the following score
     * | S(n) Intersection S(n') | / | S(n) Union S(n') | 
     * 
     * where S(n) is the set of leaves that are descendants of node n.
     * 
     * @author   Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou
     * 
     * @see      AccordionDrawer.Tree
     * @see      AccordionDrawer.TreeNode
     * @see      TreeJuxtaposer.NodeScorePair
     */

    TreeNode getBestCorrNode(Tree source, TreeNode n, Tree other, int el) {
        HashMap h = null;
	if((source == treeA)&&(other == treeB))
	{
	    h = (HashMap)bestA2B.elementAt(el);
	}
	else if((source == treeB)&&(other == treeA))
	{
	    h = (HashMap)bestB2A.elementAt(el);
	}
	if (h == null) return null;
	
    NodeScorePair p = ((NodeScorePair)(h.get(n)));
    if (p != null)
        return p.node;
    return null;
    }

    float getBestCorrNodeScore(Tree source, TreeNode n, Tree other, int el) {

	if((source == treeA)&&(other == treeB))
	    return ((NodeScorePair)(((HashMap)(bestA2B.elementAt(el))).get(n))).score;
	else if((source == treeB)&&(other == treeA))
	    return ((NodeScorePair)(((HashMap)(bestB2A.elementAt(el))).get(n))).score;
	else return -1.0f;
    }

	// return an ArrayList of RangeInTree objects that correspond to n from source
	ArrayList getCorrRange(Tree source, TreeNode n, Tree other, int el)
	{
		int min = n.getMin();
		if ((source == treeA)&&(other == treeB))
			return (ArrayList)A2B.get(n);
		else if ((source == treeB) && (other == treeA))
			return (ArrayList)B2A.get(n);
		return null;
	}


//    /** 
//     * Given a node range in one tree, say whether there's an overlap
//     * with the node range in the other tree. 
//     * Returns number of overlapping nodes, possibly 0
//     * 
//     * @author   Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou
//     * 
//     * @see      AccordionDrawer.Tree
//     * @see      AccordionDrawer.TreeNode
//     */
//
//    int isRangeInRange(Tree source, int AMin, int AMax, 
//		       Tree other, int BMin, int BMax) throws Exception{
//	if((source == treeA)&&(other == treeB)) 
//	    return rangeAB.query2D(AMin, AMax, BMin, BMax);
//	else if((source == treeB)&&(other == treeA)) 
//	    return rangeBA.query2D(AMin, AMax, BMin, BMax);
//	else
//	    return -1;
//    }

    class NodeScorePair {

	TreeNode node = null;
	float score = 0.0f;
	NodeScorePair(TreeNode n, float s) { node = n; score = s; }
    };

    /** 
     * Attachment to a node that is needed as temporary data structure
     * when computing best corresponding nodes
     **/
    class TmpD {
	int tmpScore = 0;
	float uSum = 0;
	float lSum = 0;
	TreeNode tmpParent = null;
	TreeNode tmpPosorderNext = null;
	TmpD() {;}
    };

    /**
     *
     * For each node om Tree t1, computes the best matching node in
     * Tree t2 and stores it in HashMap h12
     * 
     * @see      AccordionDrawer.Tree
     * @see      TreeJuxtaposer.computeBestMatch
     * @see      TreeJuxtaposer.NodeScorePair
     */

    
    void computeBestMatch(Tree t1, Tree t2, Vector v12, int eL) {
	
	TmpD[] tmpData = new TmpD[t2.nodes.size()];