Computing Maximum Common Subgraphs: software
This page contains the software of the algorithms presented in:
- L. Schietgat, J. Ramon, M. Bruynooghe: A Polynomial-time Maximum Common Subgraph Algorithm for Outerplanar Graphs and its Application to Chemoinformatics (accepted for Annals of Mathematics and Artificial Intelligence 2013) [preprint, DOI]
- L. Schietgat, F. Costa, J. Ramon, L. De Raedt: Effective feature construction by maximum common subgraph sampling, Machine Learning 83(2), 137-161, 2011. [preprint, DOI]
The algorithm is implemented as a feature in the package FOG, developed by Jan Ramon.
A binary executable for Linux can be downloaded here. The C++ source code is available from the author upon request.
A script to convert graph data from gSpan-format to FOG-format: gspan2line.perl (thanks to Björn Bringmann).
Usage: perl gspan2line.perl dataset.gspan > dataset.fog
Computing an MCS between two graphs in a dataset:
./fog -db=dataset.fog -cmd=distance -id1=0 -id2=1
Sampling k MCSs at random:
./fog -db=dataset.fog -cmd=sample_mcs -id1=k
Sampling all MCSs:
./fog -db=dataset.fog -cmd=all_mcs
The output of the algorithm is written in the file mcs_patterns.fog, which can be again converted into the gSpan-format with: line2gspan.perl.
Please direct questions to Leander Schietgat.