Algora

What's this?

Algora is a modular algorithms library written in C++.

The design principle was to have data structures and algorithms that are

Algora currently consists of three ‘‘pillars’’:

Algora|Core: The core library. Provides data structures for directed graphs, support for sub- and supergraphs, property maps to attribute a graph’s vertices and arcs, as well as some basic graph algorithms and routines to read and write graphs.
Algora|Dyn: A library especially for dynamic graph algorithms. Contains support for dynamic weighted and unweighted graphs, i.e., graphs that undergo a series of updates (e.g. vertex/arc insertions/deletions or weight changes). In addition, it currently features implementations of various fully dynamic reachability algorithms.
Algora|LO: A library containing algorithms for the Linear Ordering Problem and the Feedback Arc Set Problem. Contains data structures and a collection of both heuristic and exact algorithms to find a linear ordering of the graph’s vertices with as few as possible contradicting arcs (a.k.a. the Linear Ordering Problem), which is algorithmically equivalent to finding a smallest possible subset of arcs whose removal makes the graph acyclic (a.k.a. the Feedback Arc Set Problem).

Jan 13, 2022: Released Algora|Core version 1.3, Algora|Dyn version 1.1.1.
Apr 10, 2020: Released Algora|Core version 1.2, Algora|Dyn version 1.1.
Oct 11, 2019: Released Algora|Core version 1.1, Algora|Dyn version 1.0.
Sep 18, 2019: Set up this website.

Algora has been used in the following publications:

Kathrin Hanauer, Monika Henzinger, Stefan Schmid, Jonathan Trummer: Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies. INFOCOM 2022, May 2-5, 2022. To appear. Visit code repository
Kathrin Hanauer, Monika Henzinger, Christian Schulz: Faster Fully Dynamic Transitive Closure. 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy. 14:1-14:14 Visit paper website
Kathrin Hanauer, Monika Henzinger, Christian Schulz: Fully Dynamic Single-Source Reachability in Practice: An Experimental Study. 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). 106-119. Visit paper website
Kathrin Hanauer: Linear Orderings of Sparse Graphs. PhD thesis. University of Passau, 2018.

Algora is free software and licensed under the GNU General Public License version 3.

It is developed semi-publicly on Gitlab and Github.

Algora|Core comes with a Doxyfile and a simple code example (see examples/). Further documentation and examples are on the TODO list…