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]


Source code

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.

Quick manual

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.