Algorithmic aspects of vertex elimination on graphs

This repo contains the optional project for the Advanced Algorithms part of the Computer Science and Engineering Master's Degree course Advanced Algorithms and Parallel Programming (095946 - A.Y. 2020/21) of Politecnico di Milano. The goal of the project is to create, test and benchmark a C++ implementation of the algorithms described in Algorithmic aspects of vertex elimination on graphs by Rose, Lueker & Tarjan.

I've implemented the algorithms as a generic header-only C++ template library (following the C++17 standard) to be used alongside the powerful Boost Graph Library, supporting all the different Graph implementations provided by it.

A brief report in the form of a slideshow used for presentation of the project is available here.

Implemented algorithms

The authors of this paper propose three algorithms for efficient computation of vertex elimination orderings on simple, connected, undirected (SCU for brevity) graphs:

• FILL (src/fill.h): an O(V+E) algorithm to compute the chordal completion of any SCU graph.
• LEX M (src/lex_m.h): an O(VE) algorithm to compute a minimal vertex elimination order of any SCU graph.
• LEX P (src/lex_p.h): an O(V+E) algorithm to compute a perfect vertex elimination order for a chordal graph. This algorithm is also known as lexicographic breadth-first search.

Errors in the paper

I've discovered the following errors in the algorithms described in the paper:

1. The LEX M algorithm presents some logical/typographical errors in the "search" loop:

   • All the ks that appear inside the loop should be js.
   • The loop should run in the opposite direction with j from 1 to k: the graph needs to be explored starting from lower labeled vertices.
   • if l(z) < k should be if l(z) > j: the label of vertex z should only be increased if we can reach it through a chain of lower-labeled vertices.

2. The BFS labeling algorithm (outside the scope of this project) also presents one logical error: in the "explore" loop, new vertices should only be added to the queue if not already present. Adding vertices twice will lead to wrong labeling.

Building

This is a header-only template library and thus does not need any building. The only dependency when using this library is Boost Graph (development headers and dynamic library, packaged on any major Linux distro), also needed for testing and benchmarking.

When using this library, compile with at least -std=c++17 and link with -lboost_graph.

Testing

Building unit tests (in addition to Boost Graph) also requires the Boost Test developement headers and dynamic library.

make tests     # build only
make run_tests # build and run

To also compile and run tests with coverage support to produce coverage info (needs gcov):

make clean # if already compiled
make run_tests COVERAGE=1

Benchmarking

Building benchmarks (in addition to Boost Graph) also requires the Google Benchmark development headers and static library. This is expected to be cloned in build/benchmark and correctly built using cmake. The Makefile in this repository will automatically try to clone and build this as needed.

make benchmarks          # build only
make run_benchmarks      # build and run
make run_time_benchmarks # build and run only time benchmarks
make run_mem_benchmarks  # build and run only memory benchmarks

Plotting benchmark results requires Python 3 (>= 3.6) with numpy, matplotlib and scikit-learn.

python3 -m pip install -r test/bench/requirements.txt
make plot_benchmarks

---

Copyright © 2021 Marco Bonelli. Licensed under the Apache License 2.0.