[78] | 1 | package org.biohackathon.SPARQLBuilder.OWL;
|
---|
| 2 |
|
---|
| 3 | import java.io.Serializable;
|
---|
| 4 | import java.util.HashMap;
|
---|
| 5 | import java.util.LinkedHashSet;
|
---|
| 6 | import java.util.LinkedList;
|
---|
| 7 | import java.util.List;
|
---|
| 8 | import java.util.Map;
|
---|
| 9 |
|
---|
| 10 | public class SimpleTree <N extends Serializable > {
|
---|
| 11 |
|
---|
| 12 | // children key, parent value
|
---|
| 13 | private final Map<N, N> nodeParent = new HashMap<N, N>();
|
---|
| 14 |
|
---|
| 15 |
|
---|
| 16 | //all nodes list
|
---|
| 17 | private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();
|
---|
| 18 |
|
---|
| 19 | public void add (N parent, N node) {
|
---|
| 20 |
|
---|
| 21 | nodeList.add(node);
|
---|
| 22 | nodeList.add(parent);
|
---|
| 23 | nodeParent.put(node, parent);
|
---|
| 24 |
|
---|
| 25 |
|
---|
| 26 | }
|
---|
| 27 |
|
---|
| 28 | //for unstrict tree:multi-root
|
---|
| 29 | public List<N> getRoots () {
|
---|
| 30 | return getChildren(null);
|
---|
| 31 | }
|
---|
| 32 |
|
---|
| 33 | // for strict tree: one root
|
---|
| 34 | public N getRoot () {
|
---|
| 35 |
|
---|
| 36 | List<N> list = getRoots();
|
---|
| 37 | return list.get(0);
|
---|
| 38 |
|
---|
| 39 | }
|
---|
| 40 |
|
---|
| 41 |
|
---|
| 42 |
|
---|
| 43 | public N getParent (N node) {
|
---|
| 44 | return nodeParent.get(node);
|
---|
| 45 | }
|
---|
| 46 |
|
---|
| 47 | public List<N> getChildren (N node) {
|
---|
| 48 | List<N> children = new LinkedList<N>();
|
---|
| 49 | for (N n : nodeList) {
|
---|
| 50 | N parent = nodeParent.get(n);
|
---|
| 51 | if (node == null && parent == null) {
|
---|
| 52 | children.add(n);
|
---|
| 53 | } else if (node != null && parent != null && parent.equals(node)) {
|
---|
| 54 | children.add(n);
|
---|
| 55 | }
|
---|
| 56 | }
|
---|
| 57 | return children;
|
---|
| 58 | }
|
---|
| 59 |
|
---|
| 60 |
|
---|
| 61 | public String toString () {
|
---|
| 62 | StringBuilder builder = new StringBuilder();
|
---|
| 63 | dumpNodeStructure(builder, null, "- ");
|
---|
| 64 | return builder.toString();
|
---|
| 65 | }
|
---|
| 66 |
|
---|
| 67 | private void dumpNodeStructure (StringBuilder builder, N node, String prefix) {
|
---|
| 68 | if (node != null) {
|
---|
| 69 | builder.append(prefix);
|
---|
| 70 | builder.append(node.toString());
|
---|
| 71 | builder.append('\n');
|
---|
| 72 | prefix = " " + prefix;
|
---|
| 73 | }
|
---|
| 74 | for (N child : getChildren(node)) {
|
---|
| 75 | dumpNodeStructure(builder, child, prefix);
|
---|
| 76 | }
|
---|
| 77 | }
|
---|
| 78 |
|
---|
| 79 | private N findMinAncestorIntenal(N node1,N node2){
|
---|
| 80 |
|
---|
| 81 | N root = getRoot();
|
---|
| 82 |
|
---|
| 83 |
|
---|
| 84 | for ( N parent1 = node1;parent1!=root;parent1=getParent(parent1))
|
---|
| 85 | {
|
---|
| 86 |
|
---|
| 87 | for ( N parent2=node2;parent2!=root;parent2=getParent(parent2))
|
---|
| 88 | {
|
---|
| 89 |
|
---|
| 90 | if(parent1==parent2) return parent1;
|
---|
| 91 |
|
---|
| 92 | }
|
---|
| 93 |
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | return root;
|
---|
| 97 |
|
---|
| 98 |
|
---|
| 99 | }
|
---|
| 100 | public N findMinAncestor(N... node){
|
---|
| 101 | int length = node.length;
|
---|
| 102 | if (length<=1) return node[0];
|
---|
| 103 |
|
---|
| 104 | N ancestor=node[0];
|
---|
| 105 |
|
---|
| 106 | for(int i=0;i<length-1;i++)
|
---|
| 107 | {
|
---|
| 108 | ancestor=findMinAncestorIntenal(ancestor,node[i+1]);
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 | return ancestor;
|
---|
| 112 | }
|
---|
| 113 |
|
---|
| 114 |
|
---|
| 115 | /* H
|
---|
| 116 | * / \
|
---|
| 117 | * D K
|
---|
| 118 | * / \
|
---|
| 119 | * E F
|
---|
| 120 | * / \ \
|
---|
| 121 | * A B C
|
---|
| 122 | *
|
---|
| 123 | */
|
---|
| 124 |
|
---|
| 125 | public static void main (String[] args) {
|
---|
| 126 |
|
---|
| 127 | SimpleTree<String> tree = new SimpleTree<String>();
|
---|
| 128 |
|
---|
| 129 | tree.add("D", "E");
|
---|
| 130 | tree.add("D", "F");
|
---|
| 131 | tree.add("E", "A");
|
---|
| 132 | tree.add("E", "B");
|
---|
| 133 | tree.add("E", "L");
|
---|
| 134 | tree.add("F", "C");
|
---|
| 135 | tree.add("H", "D");
|
---|
| 136 | tree.add("H", "K");
|
---|
| 137 |
|
---|
| 138 | System.out.println(tree.nodeParent.toString());
|
---|
| 139 |
|
---|
| 140 | List<String> list= tree.getRoots();
|
---|
| 141 | System.out.println(list.toString());
|
---|
| 142 |
|
---|
| 143 | String ance=tree.findMinAncestor("A","B","F","E");
|
---|
| 144 | System.out.println(ance);
|
---|
| 145 |
|
---|
| 146 |
|
---|
| 147 | }
|
---|
| 148 |
|
---|
| 149 | }
|
---|