With CoMRiT one can compute realisations of finite metric spaces (i.e., weighted graphs representing whose shortest-path distance represents the metric).
Description
The software works by finding paths in the the tight-span of the metric space without computing the tight-span itself explicitly, as described in detail in the paper Computing Realizations of Finite Metric Spaces by Herrmann, Moulton and Spillner. The program is implemented as part of the Metrics extension of polymake which defines a finite metric space as a polymake object. The software also includes an implementation to compute cut-points of the tight-span of a metric space (Dress et al. 2010, see also the BloDec program) and routines to compute optimal Manhattan networks and shortest realising subgraphs of a graph as described in the paper. The implementation as an extension of polymake allows for sever! al additional features such as computing the tight-span, visualising graphs and realisations, and producing metrics from graphs and other given data.
Availability
The software is implemented in C++ and Java as an extension of the software system polymake. You must download and install polymake (version 2.12) before you can use CoMRiT. Then, download our extension and extract it, start polymake and run 'import_extension DIR;' where DIR is the directory you extracted the file to (This may take some time as polymake will then compile the extension for you). More information go to polymake extensions.
You need to satisfy all prerequisites for polymake and to use the routines for computing minimal Manhattan networks and shortest realising subgraphs, you also need the GNU General Public License.
CoMRiT is copyright (c) Sven Herrmann and Andreas Spillner and is freely available under the General Public License. Polymake and GLPK operate under the same licence.
If you use CoMRiT, please cite the reference below.
Documentation
Support
For technical questions or feature requests, contact Dr. Sven Herrmann.
References
S. Herrmann, V. Moulton and A. Spillner, Computing Realizations of Finite Metric Spaces, 2012.
Cut-point computation
A. Dress, K.T. Huber, J. Koolen, V. Moulton and A. Spillner, An algorithm for computing cutpoints in finite metric spaces, J. Classification, 27(2) 158-172, 2010.
Research Team
Dr. Sven Herrmann, Prof. Vincent Moulton, Dr. Andreas Spillner.