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.