The CyMeAlg Software (Release 0.01)
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.
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
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.
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"
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.
; This is a sample graph.
0 -> 0 [1.12]
0 -> 1 [2.33]
1 -> 0 [-1e-6]
2 -> 0 
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).
This software package is published under the terms
of the GNU
General Public License, version 3.
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.