biserkov/twotree-longest-path

The code from my master thesis. 100.0% Clojure.

O(n) algorithm for computing longest paths in 2-trees

Overview

In 2013 Markov, Vassilev and Manev published a novel linear time algorithm for computing longest paths in 2-trees.

This repository contains 3 implementations of said algorithm in Clojure:

The first one is a direct implementation of the mathematical operations described in the paper. Due to the need to construct subgraphs to implement splitting, the time complexity is O(n√n).

The second one was suggested by Minko Markov and preprocesses the 2-tree, thus avoiding the need to construct subgraphs. The time complexity is O(n). Due to its recursive nature, this implementation will fail with a Stack Overflow Error if used on deep 2-trees with millions of vertices.

The third implementation is an iterative one. It uses the EdgeLabels map as a sort of explicit call stack. The time complexity is O(n).

Only the third one should be used for any practical purposes.

Data representation

The vertices of the graph are represented as positive integers.

On an abstract lever, the graph is represented as an adjacency list.

On a concrete level, it's a int-map in which a vertex acts as key and the corresponding values is an int-set of the its neighbours.

twotree-longest-path's Issues

Boxed math

Longest_path.path

Compute the actual path, not just it's length.

Longest_path.weighted-length

Example Code or Test Input?

Hi! This looks cool. Can you push an example file, or show a simple example in code? Haven't tried to run yet, just getting an idea of how to use it.

Specifically, I want to calculate the critical path (longest weighted) path between two nodes in a graph (which might be cyclic so cycles are equivalent to an inferred node, but let's say it acyclic)

Sign releases

GraalVM

Longest_path.weighted-path