TreeJuxtaposer
Class Tree2Tree

java.lang.Object
  |
  +--TreeJuxtaposer.Tree2Tree

class Tree2Tree

extends java.lang.Object

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.

Version:

Author:

Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou

See Also:

AccordionDrawer.Tree, RangeTree

Nested Class Summary

(package private) class	Tree2Tree.NodeScorePair
(package private) class	Tree2Tree.TmpD Attachment to a node that is needed as temporary data structure when computing best corresponding nodes

Field Summary

(package private) java.util.Hashtable	A2B
(package private) java.util.Hashtable	B2A
(package private) java.util.Vector	bestA2B The hashmaps that store the best matchings.
(package private) java.util.Vector	bestB2A The hashmaps that store the best matchings.
(package private) float	epsilon
(package private) RangeTree	rangeAB
(package private) RangeTree	rangeBA
(package private) Tree	treeA
(package private) Tree	treeB

Constructor Summary

(package private)

Tree2Tree(Tree t1, Tree t2, int eL)

Method Summary

private void	addNodeToForest(TreeNode node, java.util.ArrayList array, java.util.Hashtable hash)
void	close() clean method, called when a tree is deleted
(package private) Tree2Tree.NodeScorePair	computeBestMatch(TreeNode an, Tree t, float alpha, java.lang.Object[] tmpData)
(package private) Tree2Tree.NodeScorePair	computeBestMatch(TreeNode an, Tree t, java.lang.Object[] tmpData) compute the best corresponding node for each node node B is the best corresponding node of node A if it maximizes | L(A) U L(B)| ---------------- | L(A) n L(B)| where L(A),L(B) represent the set of leaves underneath the node A and node B respectively.
(package private) void	computeBestMatch(Tree t1, Tree t2, java.util.Vector v12, int eL) For each node om Tree t1, computes the best matching node in Tree t2 and stores it in HashMap h12
(package private) float	computeDistance(float alpha, int mode) Computes the dissimilarity distance between treeA and treeB The distance is computed by summing up getBestCorrNode scores between each tree node in treeA and the best matching node in treeB.
private void	computeForest(java.util.Hashtable X2Y, Tree treeX, Tree treeY, AccordionTreeDrawer atdY, int cutoff)
(package private) 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.
(package private) float	getBestCorrNodeScore(Tree source, TreeNode n, Tree other, int el)
(package private) java.util.ArrayList	getCorrRange(Tree source, TreeNode n, Tree other, int el)
(package private) int	isRangeInRange(Tree source, int AMin, int AMax, Tree other, int BMin, int BMax) Given a node range in one tree, say whether there's an overlap with the node range in the other tree.
private java.util.ArrayList	reduceNodeListToCutoff(java.util.ArrayList node, int cutoff)
private void	removeNodeFromForest(TreeNode node, java.util.ArrayList array, java.util.Hashtable hash)
void	subtree2Forest(AccordionTreeDrawer atdA, AccordionTreeDrawer atdB, int eL)

Methods inherited from class java.lang.Object

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

Field Detail

treeA

Tree treeA

treeB

Tree treeB

A2B

java.util.Hashtable A2B

B2A

java.util.Hashtable B2A

bestA2B

java.util.Vector bestA2B

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

bestB2A

java.util.Vector bestB2A

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

epsilon

float epsilon

rangeAB

RangeTree rangeAB

rangeBA

RangeTree rangeBA

Constructor Detail

Tree2Tree

Tree2Tree(Tree t1,
          Tree t2,
          int eL)

Method Detail

close

public void close()

clean method, called when a tree is deleted

See Also:

TreePairs.removeTree

addNodeToForest

private void addNodeToForest(TreeNode node,
                             java.util.ArrayList array,
                             java.util.Hashtable hash)

removeNodeFromForest

private void removeNodeFromForest(TreeNode node,
                                  java.util.ArrayList array,
                                  java.util.Hashtable hash)

reduceNodeListToCutoff

private java.util.ArrayList reduceNodeListToCutoff(java.util.ArrayList node,
                                                   int cutoff)

computeForest

private void computeForest(java.util.Hashtable X2Y,
                           Tree treeX,
                           Tree treeY,
                           AccordionTreeDrawer atdY,
                           int cutoff)

subtree2Forest

public void subtree2Forest(AccordionTreeDrawer atdA,
                           AccordionTreeDrawer atdB,
                           int eL)

getBestCorrNode

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.

See Also:

AccordionDrawer.Tree, AccordionDrawer.TreeNode, TreeJuxtaposer.NodeScorePair

getBestCorrNodeScore

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

getCorrRange

java.util.ArrayList getCorrRange(Tree source,
                                 TreeNode n,
                                 Tree other,
                                 int el)

isRangeInRange

int isRangeInRange(Tree source,
                   int AMin,
                   int AMax,
                   Tree other,
                   int BMin,
                   int BMax)
             throws java.lang.Exception

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

java.lang.Exception

See Also:

AccordionDrawer.Tree, AccordionDrawer.TreeNode

computeBestMatch

void computeBestMatch(Tree t1,
                      Tree t2,
                      java.util.Vector v12,
                      int eL)

For each node om Tree t1, computes the best matching node in Tree t2 and stores it in HashMap h12

See Also:

AccordionDrawer.Tree, TreeJuxtaposer.computeBestMatch, TreeJuxtaposer.NodeScorePair

computeDistance

float computeDistance(float alpha,
                      int mode)

Computes the dissimilarity distance between treeA and treeB The distance is computed by summing up getBestCorrNode scores between each tree node in treeA and the best matching node in treeB.

 mode 0: alpha is the cut off
 1: (1-s)^\alpha
 2: 1-s^{1/\alpha}
 

computeBestMatch

Tree2Tree.NodeScorePair computeBestMatch(TreeNode an,
                                         Tree t,
                                         java.lang.Object[] tmpData)

compute the best corresponding node for each node node B is the best corresponding node of node A if it maximizes | L(A) U L(B)| ---------------- | L(A) n L(B)| where L(A),L(B) represent the set of leaves underneath the node A and node B respectively. For the description of the algorithm, see Li Zhang. On Matching Nodes in Two Trees.

computeBestMatch

Tree2Tree.NodeScorePair computeBestMatch(TreeNode an,
                                         Tree t,
                                         float alpha,
                                         java.lang.Object[] tmpData)