An implementation of the Kuhn–Munkres algorithm.

Copyright (c) 2007-2013 John Weaver and contributors.
Licensed under the GPLv2. See the file COPYING for details.

For use:

• C++ compiler with C++11 support.

For development:

• GCC (tested on 4.6.3, 4.8);
• GNU Make;
• CMake (2.8.12);
• the test suite requires the Google C++ Test Framework;
• microbenchmarking requires Benchmark, Celero, Hayai and gprof;
• code coverage requires gcov and lcov;
• static code analyzer requires cppcheck.

The project is developed under the GNU/Linux OS with the gcc compiler and usually not tested under other OSs and compilers. But the project does not use OS or compiler specific features (types, attributes, etc) so it's expected that the project will be normally work under other platforms.

These steps are the easiest way to get started:

• download: $ git clone https://github.com/saebyn/munkres-cpp.git && cd munkres-cpp
• build: $ mkdir build && cd build && cmake .. && make
• install: $ make install

TBD

For development purpose, the project implements a variety of build targets. All of them help to continuously check correctness of algorithm implementation, performance, memory management, etc. Pass the-DMUNKRESCPP_DEVEL_MODE=ON option to CMake to enable development mode.

Build and execute the test suite with these commands:

$ git clone https://github.com/saebyn/munkres-cpp.git
$ cd munkres-cpp
$ mkdir build && cd build
$ cmake -DCMAKE_BUILD_TYPE=Debug -DMUNKRESCPP_DEVEL_MODE=ON ..
$ make tests
$ tests/munkrestest

You must compile unit tests in debug mode to get a correct code coverage report.

$ <build and Launch unit tests>
$ make coverage
$ firefox coverage/index.html &

Since the unit tests call all functions which implement the algorithm, using valgrind on the unit test runner is an appropriate way to check memory management.

$ <build unit tests>
$ valgrind tests/munkrestest

First, build them:

$ git clone https://github.com/saebyn/munkres-cpp.git
$ cd munkres-cpp
$ mkdir build && cd build
$ cmake -DCMAKE_BUILD_TYPE=Release -DMUNKRESCPP_DEVEL_MODE=ON ..
$ make benchmarks

To get comparable results it's required to generate the data set wich will be used for all benchmarks:

$ benchmarks/tools/generator/matrixgenerator.bin {dim_1 dim_2 ... dim_n}

Where every dim_x parameter generates a square matrix with dim_x dimension. To launch microbenchmarks, perform the following commands:

$ benchmarks/tests/munkresbenchmark_celero.bin
$ benchmarks/tests/munkresbenchmark_google.bin
$ benchmarks/tests/munkresbenchmark_hayai.bin
$ benchmarks/tests/munkresbenchmark_rdtsc.bin

$ <build microbenchmarks and generate data set>
$ benchmarks/tests/munkresbenchmark_gprof.bin
$ gprof benchmarks/tests/munkresbenchmark_gprof.bin gmon.out -p -b

$ make cppcheck

TBD

Check the issues list at GitHub.