We need jgrapht. Since this is a Maven project, I have already added pom.xml to fetch dependencies.
We have a dot file which contains a graph and we need to find all the closest ancestor of two given nodes as command line argument. Since we intend to find all the LCAs of two given nodes, expected graph is a DAG. So you can alter fileName in LeastCommonAncestor class and choose your own dot file. Remember to add only DAG.
LeastCommonAncestor contains a method allLcas
which uses DOTImporter
class to parse the dot file as graph and then uses
findLcas
from NaiveLcaFinder
. We need to make sure the input dot file contains a DAG.
My current dot file which renders following graph:
I am yet to write test cases, but gives me following output for Tyrion Cersei