Subgraph Isomorphism Algorithm

This page contains the implementation and instances from paper Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem of Malík, Suchý and Valla.

Content

subiso.tar.gz	algorithm implementation
LibUCW.tar.gz	LibUCW library needed to run the algorithm
data.tar.gz	data used for benchmarks

Installation guide

Prerequisites

Module consists of C implementation files, C header files and an installation file Makefile. It is intended to be run on a unix-like system. For the installation, the system is required to contain the following prerequisites:

GNU tools:

gcc version 4.0 or higher
bash version 2.0 or higher

LibUCW (for installation guide see http://www.ucw.cz/libucw/)
Additional LibUCW prerequisites:

perl
pkg-config

Installation

The installation is to be performed from the folder containing installation file Makefile. There are in total three modes in which the module can be installed:

Installation by command make – This is the default mode of installation. It produces minimal information about the run and yields the maximal performance. It is suitable for the regular usage of the module, or for the performance testing of the module.
Installation by command make tests – This is the testing mode of installation. It produces minimal information about the run, but in addition tests the validity of structures created during the run. It is suitable for the qualitative testing of the module.
Installation by command make debug – This is the debug mode of installation. It produces detailed information about the run and the structures used in the run. It is suitable for the debugging purposes.

After a successful installation, a binary executable file grs is produced. To uninstall the module or to change the installation type of the module, it is required to execute command make clean. After its execution the module folder is reverted to its original state.

Usage

The module is accessible through command-line interface and the input is loaded through specifiable external files. The output from the module is directed to the standard output. After a successful installation, the module can be run via binary file grs created during the installation.

Run parameters

To run the module, there are mandatory parameters which have to be specified. The full interface of the module can be found by using --help option.

Graph file formats

Graph files which are presented to the module must be in accordance to a specific format, which is in one of the following forms.

Basic graph file format

On the first line of the graph file, there is a number of vertices n of the graph. On the i-th from the next n lines, there is information about the neighbors of the (i − 1)-th vertex (vertices are thus to be numbered from 0). Specifically, there is a number s_{i − 1} of neighbors of vertex i − 1. After that, there are s_{i − 1} numbers, each of which represents a neighbor of vertex i − 1. An example of this input format is shown below:

Extended source graph file format

his format additionaly specifies, for each vertex of the source graph, which vertices of the pattern graph can be mapped on that particular vertex. The format is derived from the basic graph format. The only difference is that additionaly, on the start of i-th line (before the information about the neighbors of the (i − 1)-th vertex), there is a bitmask of length m, where m is the number of vertices of the pattern graph that is about to be searched. In the bitmask on i-th line, the value of j-th bit from the left specifies whether vertex (j − 1) of the pattern graph can be mapped on vertex (i − 1) of the source graph. If the value of such bit is 1, the mapping is possible, and vice-versa. An example of this input format is shown below:

    4
    100 3 2 3 1
    111 1 0
    001 2 3 0
    000 2 0 2

Produced output

The algorithm continuously produces result subgraphs, because its main part is run repeatedly. To allow users of the module to extract results in cases when the specified number of runs has not yet been finished, found unique subgraphs are outputted after each run. In case the module recieves a SIGINT signal, it finishes it work after completing the first unfinished run. Each run of the module is logged and the logs are to be found in file grs.log. Accordingly to the specified option, the output is either in human-readable, or machine-readable format.