Lowest Common Ancestor

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

// Let's construct a simple rooted tree. A is the root.

MutableDirectedUnweightedGraph<String> graph = MutableDirectedUnweightedGraph.create();
graph.insertVertex("A");
graph.insertVertex("B");
graph.insertVertex("C");
graph.insertVertex("D");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("C", "D");

// Run it!

LowestCommonAncestorQuerySession<String> session = GoodLowestCommonAncestorAlgorithm.getInstrance().calc(RootedTree.wrap(graph, "A"));

String result1 = session.query("B", "C"); // must be "A"

String result2 = session.query("A", "D"); // must be "A"

See Also

Implementation

Copyright 2014 psjava team. View on GitHub