Try our source code for free

Download the source code for the reachability/lowest common ancestor (LCA) framework.

Please note: The software is a research prototype and despite our best intentions, it may contains errors/bugs.

About the code

Our framework reads unordered html lists as graph inputs where each line item corresponds to an edge.

We include examples of class hierarchies of commonly used software packages such as Eclipse and Tomcat represented in this format as a reference. Additionally, the code also generates powerset lattices and random DAGs as test cases and invokes the pre-processing and testing (on all vertex pairs) automatically.

The code reports pre-processing time (denoted by ppc_*) and lookup times (denoted by qt_*) for using our pre-processing algorithm (denoted by *_cc for cluster-based timings) over a range of lattices when compared to a plain vanilla approach to transitive closure that uses matrix multiplication (denoted by *_fc for a full closure timings).

While the code is primarily intended to measure speed-ups, it can also be used to get results of lowest common ancestor or least upper bound and reachability queries while adaptively pre-processing the input DAG/lattice to obtain the best pre-processing times over the entire structure spectrum of DAGs/lattices.

We compute the average lookup times by computing the results of these queries. So, the code for looking up the LCA for a vertex pair in already included.

What do you think?

Please send us your feedback and let us know how you have used the code. We look forward to hearing what you think of it and how you have used the simulation.