An Exploratory Assignment on Minimum Spanning Trees

Introduction

Let the weight of a tree be the sum of the squares of its edges lengths. Given a set of points P in the unit square let W(P) be the weight of the minimum spanning tree (MST) of P, where an edge length is the Euclidean distance between its endpoints. If P consist of the four corners of the square, then W(P)= 3. Gilbert and Pollack proved that W(P) is O(1) and this was extended to an arbitrary number of dimensions by Bern and Eppstein. While more recent divide-and-conquer approaches have show that W(P) ≤ 4, no point set is known with W(P) > 3, and hence it has been widely conjectured that W(P) ≤ 3. Later it was proved that W(P) < 3.41 [1].

The objective of this empirical experiment is to check if W(P) < 3.41 holds. In order to the previous theorem, we uniformaly at random generate points in the unite square P and compute the weight of the MST of these points. We do this with an increasing number of points in order to explore the solution space.

The results of this experiment can be found in the report.

Installation

This project is build using GHC(compiler) and cabal(build tool).

The easiest way to install both is using ghcup

# Install ghcup
curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh

# Install GHC using ghcup
ghcup install ghc 8.8.4

# Install cabal using ghcup
ghcup install cabal

Finally, we need to compile the project. This may takes some minutes and requires internet connection. This project does not depend on any .so so it should be possible to compile it in any architecture that supports ghc.

# It may takes some minutes
$ cabal build
...
Preprocessing executable 'mst-experiment' for mst-experiment-0.1.0.0..
Building executable 'mst-experiment' for mst-experiment-0.1.0.0..

Alternative Installation

This project is also prepared to be build with Stack.

Install Stack following the instructions from here and then run the following command:

$ stack build
...
Installing executable mst-experiment in /home/arnau/projects/haskell/mst-experiment/.stack-work/install/x86_64-linux-tinfo6/8e847b3b360c55e4f2b05724757e725ca7f55e7cb74ffe5cc2e613d4fe029b37/8.8.4/bin
Registering library for mst-experiment-0.1.0.0..

Usage

Let's start by showing the available options:

$ cabal run mst-experiment -- --help
Usage: mst-experiment COMMAND

Available options:
  -h,--help                Show this help text

Available commands:
  run                      Run the experiment and plot the result.
  single                   Single run on the given graph size.
  estimate                 Estimate k(n) for the experiment.

The executable has three options

• run: runs the experiment and plots the result to the given file (this may takes several minutes).
• single: computes the weight of the MST on the given number of vertices
• estimate (ignore): internal option that is needed to optimize the runs.

For example, to run the experiment

cabal run mst-experiment -- run --file "output"

Another example, to run the experiment with a complete undirected graph of 2048 vertices

cabal run mst-experiment -- single --size 2048 --repetitions 5