net.sourceforge.olduvai.treejuxtaposer
Class TreePairs

java.lang.Object
  net.sourceforge.olduvai.treejuxtaposer.TreePairs

public class TreePairs
extends java.lang.Object

TreePairs store all the pairwise data structures needed for structural comparison and visulization.

Version:

2.2

Author:

Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou

See Also:

TreeJuxtaposer, Tree2Tree, Tree, GridCell

Field Summary

private java.util.HashMap	pairs The hash map that stores all the Tree2Tree objects.
private java.util.ArrayList	trees List of "raw" trees, these are used in the hashtable.

Constructor Summary

TreePairs()
Constructor for tree pairs.

Method Summary

void	addTree(Tree newTree, int edgeweightLevels, boolean pruneNewLeaves) Add a new tree.
TreeNode	getBestCorrNode(Tree source, TreeNode n, Tree other, int el) 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.
float	getBestCorrNodeScore(Tree source, TreeNode n, Tree other, int edgeweightLevel) Retrieves the matching score for the node in Tree "other" whose set of descendant leaves best matches that of TreeNode n in Tree "source".
java.util.ArrayList	getBestNodeList(Tree source, TreeNode n, Tree other, int edgeweightLevel) Get the list of nodes for the given node that will be highlighted if the node is selected.
Tree2Tree	getPair(Tree t1, Tree t2) Get the Tree2Tree table for t1 and t2 differences.
void	removeTree(Tree deletedTree) Remove a tree from the list of trees.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

trees

private java.util.ArrayList trees

List of "raw" trees, these are used in the hashtable.

pairs

private java.util.HashMap pairs

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.

Constructor Detail

TreePairs

public TreePairs()

Constructor for tree pairs. Makes the list (for raw trees) and hashtable (for T2T tree comparison pairs).

Method Detail

addTree

public void addTree(Tree newTree,
                    int edgeweightLevels,
                    boolean pruneNewLeaves)

Add a new tree. Create the data structure between the new tree and all the previously added trees.

Parameters:

newTree - New tree that has been added to the application.

edgeweightLevels - The number of edge weight levels to process.

pruneNewLeaves - Unimplemented flag for removing unique leaves from processing tree comparisons, for difference marking that does not ascend when two leaf sets do not match.

getPair

public Tree2Tree getPair(Tree t1,
                         Tree t2)

Get the Tree2Tree table for t1 and t2 differences. First gets the hashmap for t1 (from pairs) then gets the T2T in that hashmap for t2 (the differences of t2 based on t1).

Parameters:

t1 - First tree object. Index in trees for hashmap.

t2 - Second tree object. Index in the recovered hashmap for t1 for the Tree2Tree object.

Returns:

Tree2Tree that corresponds to the differences in t1, with respect to t2.

removeTree

public void removeTree(Tree deletedTree)

Remove a tree from the list of trees. Does not remove the relevant tree pairs.

Parameters:

deletedTree - Tree to delete from the set of trees.

getBestCorrNode

public TreeNode getBestCorrNode(Tree source,
                                TreeNode n,
                                Tree other,
                                int el)

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.

Parameters:

source - Tree that contains the node of interest.

n - The node that we are looking up the best matching node for.

other - Target tree to look up the node in.

el - Number of edge weight levels to use.

Returns:

// TODO: here

See Also:

Tree, TreeNode, Tree2Tree.NodeScorePair

getBestNodeList

public java.util.ArrayList getBestNodeList(Tree source,
                                           TreeNode n,
                                           Tree other,
                                           int edgeweightLevel)

Get the list of nodes for the given node that will be highlighted if the node is selected. BCN are not always unique, some nodes have equally good matches for best nodes.

Parameters:

source - Source tree that contains the given tree node

n - The node to look up the list of best nodes for, found in the source tree

other - The target tree that will be referenced for the best nodes that match the given node.

edgeweightLevel - The edge weight level to use for looking up matches.

Returns:

The list of nodes in other (target tree) that match the input node the best.

getBestCorrNodeScore

public float getBestCorrNodeScore(Tree source,
                                  TreeNode n,
                                  Tree other,
                                  int edgeweightLevel)

Retrieves 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.

Parameters:

source - Source tree, in which the tree node of interest is found.

n - Node of interest, the score with respect to the second tree is returned.

other - The target tree, or the tree that the given node's score will be found.

edgeweightLevel - The edge weight level for the lookup.

Returns:

The score, as stored by index of the node, in the tree to tree object, from the pair table for the two input trees.

See Also:

Tree, TreeNode, Tree2Tree.NodeScorePair