package org.biohackathon.SPARQLBuilder.OWL; import java.io.Serializable; import java.util.HashMap; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; public class SimpleTree { // children key, parent value private final Map nodeParent = new HashMap(); //all nodes list private final LinkedHashSet nodeList = new LinkedHashSet(); public void add (N parent, N node) { nodeList.add(node); nodeList.add(parent); nodeParent.put(node, parent); } //for unstrict tree:multi-root public List getRoots () { return getChildren(null); } // for strict tree: one root public N getRoot () { List list = getRoots(); return list.get(0); } public N getParent (N node) { return nodeParent.get(node); } public List getChildren (N node) { List children = new LinkedList(); for (N n : nodeList) { N parent = nodeParent.get(n); if (node == null && parent == null) { children.add(n); } else if (node != null && parent != null && parent.equals(node)) { children.add(n); } } return children; } public String toString () { StringBuilder builder = new StringBuilder(); dumpNodeStructure(builder, null, "- "); return builder.toString(); } private void dumpNodeStructure (StringBuilder builder, N node, String prefix) { if (node != null) { builder.append(prefix); builder.append(node.toString()); builder.append('\n'); prefix = " " + prefix; } for (N child : getChildren(node)) { dumpNodeStructure(builder, child, prefix); } } private N findMinAncestorIntenal(N node1,N node2){ N root = getRoot(); for ( N parent1 = node1;parent1!=root;parent1=getParent(parent1)) { for ( N parent2=node2;parent2!=root;parent2=getParent(parent2)) { if(parent1==parent2) return parent1; } } return root; } public N findMinAncestor(N... node){ int length = node.length; if (length<=1) return node[0]; N ancestor=node[0]; for(int i=0;i tree = new SimpleTree(); tree.add("D", "E"); tree.add("D", "F"); tree.add("E", "A"); tree.add("E", "B"); tree.add("E", "L"); tree.add("F", "C"); tree.add("H", "D"); tree.add("H", "K"); System.out.println(tree.nodeParent.toString()); List list= tree.getRoots(); System.out.println(list.toString()); String ance=tree.findMinAncestor("A","B","F","E"); System.out.println(ance); } }