The CyMeAlg Software (Release 0.01)

Minimum Cycle Mean Algorithms for Directed Graphs.
A C++ Implementation

This website contains software referred to in the paper A space-efficient algorithm for computing the minimum cycle mean in a directed graph by Paweł Pilarczyk.

The algorithms described in the paper are implemented in C++ using templates (generic programming technique). A sample test program is provided. Detailed documentation was generated using Doxygen and is available for off-line browsing. The software is published here under the terms of the GNU GPL Version 3+.

This piece of software contains an implementation of a few graph algorithms, and is mainly focused on demonstrating a new memory efficient version of Karp's algorithm for the computation of minimum mean cycle weight in a directed graph.

Compilation. The compilation of the software should be relatively simple. The GNU C++ compiler should be used. The Boost library collection should be present in the system. Please, edit the file makefile in the directory into which the source code has been unpacked to make sure that the paths and other settings are correct. Then run the command make. Although this software uses parts of the CHomP library, all the relevant files have been included in this distribution, so it is not necessary to download or compile it first.

In Linux, all the necessary utilities should be present in the system by default (the GNU C++ compiler and the GNU make), but in Windows one should install them first, for example, using the Minimalist GNU for Windows development environment.

Software Library. The main part of this software is provided in terms of a C++ library, programmed as templates of classes and functions for optimal flexibility (so-called generic programming technique). All the header files of which the programming library consists are located in the subdirectory cymealg.

Test Program. A simple command-line driven program is provided for testing purposes. The program displays brief usage information when called without arguments. The program reads data from a file in the text format and displays all the results to the output stream, which is the screen by default, but can also be logged to a file using the "--log filename" command-line argument.

Data Format. A graph in the text format is stored in an intuitive way. The vertices of the graph are assumed to be labeled by consecutive integers, starting with 0. The number of vertices in the graph is determined automatically if there exists an outgoing edge from the vertex with the higher number; otherwise it must be given explicitly. Arcs are defined by the numbers of vertices separated with an arrow bulit from the dash and the "greater than" character. Weights of each edge are provided in brackets after the definition of each arc. All text that begins with a semicolon is ignored until the end of the line. For example:

; This is a sample graph.
4 vertices
0 -> 0 [1.12]
0 -> 1 [2.33]
1 -> 0 [-1e-6]
2 -> 0 [14]

Examples. A selection of sample graphs are included in a separate file, available for download from project's website. Please, be warned that processing some of the larger examples may require considerable resources (memory, CPU time).

License. This software package is published under the terms of the GNU General Public License, version 3.


Acknowledgment. The research whose results are described here has received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no. 622033.