Paweł Pilarczyk
The CyMeAlg Software (Release 1.0)
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.
Files for Download
The following files are available here for free download
(note the Linux/Unix text format: line ending = LF):
Compilation
The compilation of the software should be relatively simple.
The GNU C++ compiler is strongly recommended.
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 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.