treepairs.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.Tree;
import AccordionTreeDrawer.TreeNode;

import java.util.*;

/**
 * TreePairs store all the pairwise data structures needed for
 * structural comparison and visulization.
 *
 * @author Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou
 * @version 
 * @see TreeJuxtaposer.TreeJuxtaposer
 * @see TreeJuxtaposer.Tree2Tree
 * @see     AccordionDrawer.Tree
 * @see     AccordionDrawer.GridCell
 *
 **/

public class TreePairs {

    ArrayList trees; 

    /**
     * the hash map that stores all the Tree2Tree objects.   the
     * pairs are indexed first by the key of one tree in the pair 
     * and then by the key of the other tree in the pair. a better 
     * solution would be to use the key pair to index each pair. but
     *  since the number of trees is small and is likely in the
     * range  fewer than 10, it does not really matter how we
     * implement it.
     */
    HashMap pairs; 

    TreePairs() {
	trees = new ArrayList();
	pairs = new HashMap();
    }

    /**
     * Add a new tree 
     *
     * Create the data structure between the tree and all the
     * previously added trees.
     **/
     
    void addTree(Tree newTree, int eL) {

	if(trees.size()>=1) {
	    // we need to add all the pairs between newTree and all
	    // the previously added trees.
	    HashMap h = new HashMap();
	    
	    pairs.put(newTree, h); 
	    
	    // construct the data structure between the newly added
	    // tree and every previously added tree
	    for(int i=0; i<trees.size(); i++) {
		Tree t = (Tree)trees.get(i);
		Tree2Tree t2t = new Tree2Tree(t,newTree,eL);
		h.put(t, t2t);
		HashMap ht = (HashMap)pairs.get(t);
		if(ht==null) {
		    // this happens when there was only one tree in
		    // the list 
		    ht = new HashMap();
		    ht.put(newTree, t2t);
		    pairs.put(t, ht);
		} else
		    ht.put(newTree, t2t);
	    }
	}
	trees.add(newTree);
    }
	
	Tree2Tree getPair(Tree t1, Tree t2)
	{
		HashMap h = (HashMap) pairs.get(t1);
		if (h == null)
			return null;
		return (Tree2Tree) h.get(t2);
	}

	/**
	* remove a tree and the  relevant tree pairs  
	* @see Tree2Tree.close
	* @see TreeJuxtaposer.deleteTree
	*/
	void removeTree(Tree deletedTree)
	{
		trees.remove(deletedTree);
		HashMap h = (HashMap) pairs.get(deletedTree);
		//			WeakHashMap h = (WeakHashMap)pairs.get(deletedTree);
		for (int i = 0; i < trees.size(); i++) {
			Tree2Tree t2t = (Tree2Tree) h.get(trees.get(i));
			t2t.close();
		}
		pairs.remove(deletedTree);

		for (int i = 0; i < trees.size(); i++) {
			HashMap hm = (HashMap) pairs.get(trees.get(i));
			//				  WeakHashMap hm = (WeakHashMap)pairs.get(trees.get(i));
			Tree2Tree t2t = (Tree2Tree) hm.get(deletedTree);
			t2t.close();
			hm.remove(deletedTree);
		}

	}

    /**
     * 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)
	{
		if (source == other)
			return n;
		if (null == n)
			return null;
		Tree2Tree t2t = getPair(source, other);
		if (t2t == null)
			return null;
		return t2t.getBestCorrNode(source, n, other, el);
	}

	ArrayList getBestNodeList(Tree source, TreeNode n, Tree other, int el)
	{
		if (null == n)
			return null;
		Tree2Tree t2t = getPair(source, other);
		if (t2t == null)
			return null;
		ArrayList returnValue = t2t.getCorrRange(source, n, other, el);
		return returnValue;
	}

    /**
     * Computes the matching score for the node in Tree "other" whose
     * set of descendant leaves best matches that of TreeNode n in
     * Tree "source" 
     * 
     * The matching score between nodes n and n' is computed as
     * follows:
     *
     * | 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
     */

    float getBestCorrNodeScore(Tree source, TreeNode n, Tree other, int el) {
	
	if (source == other) return 1.0f;
	Tree2Tree t2t = getPair(source, other);
	if(t2t==null) return 0.0f;
	return t2t.getBestCorrNodeScore(source, n, other, el);
    }

//    /**
//     * Computes the dissimilarity distance between source and other
//     * 
//     * The distance is computed by summing up getBestCorrNode scores
//     * between each tree node in source and the best matching node in
//     * other 
//     *
//     * <Pre>
//     * mode 0: alpha is the cut off
//     * 1: (1-s)^\alpha
//     * 2: 1-s^{1/\alpha}
//     * </Pre>
//     *
//     */ 
//	// never called
//    float computeDistance(Tree source, Tree other, float a, int m) throws Exception {
//	Tree2Tree t2t = getPair(source, other);
//	if(t2t==null) return 0.0f;
//	return t2t.computeDistance(a, m);
//    }

//    /**
//     * Given a node range in one tree, determine whether there's an overlap
//     * with the node range in the other tree. 
//     *
//     * @return Number of overlapping nodes, possibly 0
//     */
//
//    /** 
//     * 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
//     **/
//    // never called
//    public int isRangeInRange(Tree treeA, int AMin, int AMax, 
//			      Tree treeB, int BMin, int BMax) throws Exception {
//	Tree2Tree t2t = getPair(treeA, treeB);
//	if(t2t==null) return -2;
//	return t2t.isRangeInRange(treeA, AMin, AMax, treeB, BMin, BMax);
//    }

}