RI A subgraph isomorphism algorithm.
3.3
April, 2014

Distributions

RI is distributed in several versions with different supported features depending on input graphs properties. We suggest to choose of a version based on your specific graph properties to avoid un-useful memory usage. However if you send us details concerning your application and data we can suggest the best algorithm to use.

The RI project provides a query extractor, for generating pattern graphs from target graphs with specified properties, and a C++ implementation of FocusSearch, originally developed in Modula2 by the author.

All the softwares are distributed under the RI project license and can be requested by email (see Contacts).

RI-3.3 low memory usage | Low memory requirement implementation. Compatibility of nodes and edges attributes is done during the backtracking operations.
RI-Ds-3.3 high speed performance | Domains based implementation. Compatibility maps (domains) for pattern nodes are built before the backtracking step. It avoids redundant compatibility checks between nodes of pattern graph and target nodes. Checks regard nodes attributes and neighborhood topology. Additional space to store compatibility maps as bit vectors is required.
RI-FullyDs enumerable edge attributes | Fully domains based implementation. Compatibility maps (domains) for nodes and edges are built before the backtracking operations. It requires that edges attributes can be mapped to unique identifiers. For example, you can't use this version if you have weighed graphs and you want to use approximated edge attributes comparisons. Additional space to store compatibility maps as bit vectors is required.
Query extractor | A tool for extract queries (patterns) from target graphs.
FocusSearch-C++ | A C++ implementation of FocusSearch. [Ullmann JR: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J. Exp. Algorithmics 2011, 15:1.6:1.1-1.6:1.64.]

Please note that older versions (such as RI-3.2 and RI-Ds-3.2) are no longer available.

Usage

RI - CLI (Command Line Interface)

Before usinf the RI command line interface of all distributions, please rebuilt it by make -B

.

All versions of RI take in input the same parameters:

./ri ISO_TYPE INPUT_FORMAT target_graph pattern_graph

ISO_TYPE | specify isomorphism
--- | ---
iso | bijective graphs isomorphism.
ind | induced subgraph isomorphism
mono | monomorphism, the classical subgraph matching

INPUT_FORMAT | specify input file format
--- | ---
gfd | directed graphs with attributes only on nodes.
gfu | undirected graphs with attributes only on nodes.
ged | directed graphs with attributes both on nodes and edges.
geu | undirected graphs with attributes both on nodes and edges.
vfu | Sansone et al. file format for labeled directed graphs with attributes only on nodes.

Query extractor

Before using the query extractor tool please rebuilt it by make -B querygen

./querygen [gfu gfd] input_graph number_of_nodes number_of_edges output_file number_of_queries

The query extractor tries to extract a total amount of number_of_queries subgraphs, from the given input_graph, with the specified number_of_nodes and number_of_edges, saving them at the specified output prefix output_file.

You can set the number_of_nodes or number_of_edges to -1 to do not specify them. For example, let the number_of_edges fixed to a value and the number_of_nodes set to the -1, than the extractor tries to extract a subgraph just with the given number of edges not caring the number of nodes. You can also set number_of_nodes to a decimal value between 0 and 1 to specify it as a percentage of the number_of_edges.

Note that if the input parameters do not reflect the properties of the input_graph you can obtain an unwanted resulting subgraph. So, the extractor tries first to generate a graph with the specified number of edges and the maximum possible number of nodes near to the input value. This does not exclude that a subgraph with the specified number of edges will be extracted.

FocusSearch-C++

Before use the FocusSearch-C++ command line interface of all distributions, please rebuilt it by make -B

.

The tool usage is:

./fsearch ISO_TYPE INPUT_FORMAT target_graph pattern_graph

ISO_TYPE | specify isomorphism
--- | ---
mono | monomorphism, the classical subgraph matching

INPUT_FORMAT | specify input file format
--- | ---
gfd | directed graphs with attributes only on nodes.
gfu | undirected graphs with attributes only on nodes.
vfu | Sansone et al. file format for labeled directed graphs with attributes only on nodes.

Default graph file format

The RI project provides two graph file format gfu and gfd, respectively for undirected and directed graphs with attributes only on nodes.

Graphs are stored in text files containing one or more items.
The current input format allows the description of undirect graphs with labels on nodes.

#[graph_name]
[number of nodes]
[label_of_first_node]
[label_of_second_node]
...
[number of edges]
[node id] [node id]
[node id] [node id]
...

Node ids are assigned following the order in which they are written in the input file, starting from 0.

[graph_name] and labels can not contain blank characters (spaces).
Labels are case sensitive.

An example of input file is the following:

#my_graph
4
A
B
C
Br
5
0 1
2 1
2 3
0 3
0 2

Indeed, an example of input file in geu format (undirected graph with labels both on nodes and attibutes) is:

#my_graph
4
A
B
C
Br
5
0 1 a
2 1 n
2 3 m
0 3 k
0 2 a