GraphUtil { public static <V, E> V findCommonAncestor(Tree<V, E> tree, V u, V v) { while (tree.getDepth(u) > tree.getDepth(v)) { u = tree.getParent(u); } while (tree.getDepth(v) > tree.getDepth(u)) { v = tree.getParent(v); } while (!u.equals(v)) { v = tree.getParent(v); u = tree.getParent(u); } return v; }  static void addVertices(Graph<V, E> graph, Collection<V> vertices); static void copyGraph(Graph<V, E> source, Graph<V, E> target); static void copyTree(Tree<V, E> source, Tree<V, E> target); static boolean isDescendant(Tree<V, E> t, V v, V w); static boolean isWeaklyConnected(Hypergraph<V, E> graph); static boolean areVerticesWeaklyConnected(Hypergraph<V, E> studyGraph, V first, V second); static boolean isSimpleCycle(UndirectedGraph<V, E> graph); static V findCommonAncestor(Tree<V, E> tree, V u, V v); static List<V> findPath(Tree<V, E> tree, V u, V v);  }
@Test public void testFindCommonAncestor() { Tree<String, Integer> tree = new DelegateTree<String, Integer>(); tree.addVertex("A"); tree.addEdge(1, "A", "B"); tree.addEdge(2, "B", "C"); tree.addEdge(3, "B", "D"); tree.addEdge(4, "A", "E"); assertEquals("D", GraphUtil.findCommonAncestor(tree, "D", "D")); assertEquals("B", GraphUtil.findCommonAncestor(tree, "C", "D")); assertEquals("B", GraphUtil.findCommonAncestor(tree, "B", "D")); assertEquals("A", GraphUtil.findCommonAncestor(tree, "E", "D")); }