Tree Edit Distance - Left-Most-Descendant Method

917阅读　0评论2011-12-20　maunix
分类：Java

  1. /**
  2.  * mht Dec 19, 2011
  3.  * reference Tim Henderson and Steve Johnson's test_tree.py
  4.  * Tree.java is rewrite it into Java code.
  5.  */

  7. package org.mht.ted;

  9. import java.util.*;

  11. public class Tree {
  12.     private Node _root = null;
  13. //    private int _id = -1;
  14.     private LinkedList<Node> _nodes = null;
  15.     private LinkedList<Integer> _lmds = null;    
  16.     private Node[] _keyRoots = null;
  17.     
  18.     public Tree(Node root) {
  19.         _root = root;
  20.         _nodes = new LinkedList<Node>();
  21.         _lmds = new LinkedList<Integer>();    
  22.         LinkedList<Pair> stack = new LinkedList<Pair>();
  23.         LinkedList<Pair> pstack = new LinkedList<Pair>();
  24.         stack.add(new Pair(root, new LinkedList<Integer>()));
  25.         int porder = 0;
  26.         while (stack.size() > 0) {
  27.             
  28.             Pair p = (Pair)stack.removeLast();
  29.             Node n = p.getNode();
  30.             LinkedList<Integer> anc = p.getAncIDs();
  31.             setid(n, porder);
  32.             if (n.isLeaf()) {
  33.                 //stack.add(new Pair(n, anc));
  34.                 pstack.add(new Pair(n, anc));
  35.                 //return;
  36.             }
  37.             else {
  38.                 
  39.                 for (Node c: n.getChildren()) {
  40.                     LinkedList<Integer> a = new LinkedList(anc);
  41.                     a.addFirst(n.getid());
  42.                     stack.addLast(new Pair(c, a));
  43.                     }
  44.                 pstack.addLast(new Pair(n, anc));
  45.                 porder += 1;
  46.                 }
  47.         }
  48.         
  49.         //System.out.println("Here?");
  50.         
  51.         int i = 0;
  52.         
  53.         HashMap lmds = new HashMap();
  54.         while (pstack.size() > 0) {
  55.             
  56.             Pair p = (Pair)pstack.removeLast();
  57.             Node n = p.getNode();
  58.      LinkedList<Integer> anc = p.getAncIDs();
  59.             _nodes.add(n);
  60.             System.out.println(n.getValue());
  61.             int lmd;
  62.             if (n.isLeaf()) {
  63.                 lmd = i;
  64.                 for (int a : anc)
  65.                     if (!(lmds.containsKey(a)))
  66.                         lmds.put(a, i);
  67.                     else
  68.                         break;                    
  69.             }
  70.             else
  71.                 lmd = (Integer)lmds.get(n.getid());
  72.             //System.out.print(lmd);
  73.             _lmds.addLast(lmd);
  74.             i += 1;
  75.             }
  76.         }
  77.             
  78.     public void setid(Node n, int id) {
  79.         n.setid(id);
  80.     }
  81.     
  82.     public Node getRoot() {
  83.         return _root;
  84.     }
  85.     
  86.     public LinkedList<Node> getNodes() {
  87.         return _nodes;
  88.     }
  89.     
  90.     public int getNodeCount() {
  91.         int sum = 1;
  92.         Node[] nodes = this.getRoot().getChildren();
  93.         for (Node d : nodes) {
  94.             sum += d.getNumOfDescendants();
  95.         }
  96.         return sum;
  97.     }
  98.     public LinkedList<Integer> getLmds() {
  99.         return _lmds;
  100.     }
  101.     
  102.     public static void main(String[] args) {
  103.         Node f = new Node("root", "f");
  104.         Node d = new Node("left", "d");
  105.         Node e = new Node("right", "e");
  106.         Node a = new Node("lleft", "a");
  107.         Node c = new Node("lright", "c");
  108.         Node b = new Node("ldescendant", "b");
  109.         
  110.         c.addChild(b);
  111.         d.addChild(a);
  112.         d.addChild(c);
  113.         f.addChild(d);
  114.         f.addChild(e);
  115.         Tree T = new Tree(f);
  116.         LinkedList<Node> nodes = T.getNodes();
  117.         
  118.         for (Node n: nodes) {
  119.             System.out.print(n.getValue());
  120.         }
  121.         System.out.println();
  122.         LinkedList<Integer> lmds = T.getLmds();
  123.         for (int i: lmds)
  124.             System.out.print(i);
  125.     }
  126.     
  127.     /**
  128.      * A pair is a tuple(root, children) where root is the current
  129.      * node and children is list of the node's child nodes from left to right.
  130.      * @author mht
  131.      *
  132.      */
  133.     class Pair {
  134.         private Node _node = null;
  135.         private LinkedList<Integer> _ancIDs = null;
  136.         
  137.         public Pair(Node root, LinkedList<Integer> ancIDs) {
  138.             _node = root;
  139.             _ancIDs = ancIDs;
  140.         }
  141.         public Node getNode() {
  142.             return _node;
  143.         }
  144.         public LinkedList<Integer> getAncIDs() {
  145.             return _ancIDs;
  146.         }
  147.     }
  148.     
  149. }
上一篇：exam3.3.6
下一篇：Tree Edit Distance - Node Class