RI A subgraph isomorphism algorithm.
3.3
April, 2014

Description

RI is a general purpose algorithm for one-to-one exact subgraph isomorphism problem maintaining topological constraints. It is both a C++ library and a standalone tool, providing developing API and a command line interface, with no dependencies out of standard GNU C++ library. RI works on Unix and Mac OS X systems with G++ installed, and it can be compiled under Windows using Gygwin. Working graphs may be directed, undirected, multigraphs with optional attributes both on nodes and edges. Customizable features allow user-defined behaviors for attribute comparisons and the algorithm's flow.

RI aims to provide a better search strategy for the common used backtracking approach to the subgraph isomorphism problem. It can be integrated with additional preprocessing steps or it can be used for the verification of candidate structures coming from data mining, data indexing or other filtering techniques. RI is able to find graphs isomorphisms, subgraph isomorphisms and induced subgraph isomorphisms. It is distributed in several versions divide chiefly in two groups respectively for static or dynamically changing attributes. All proposed versions are developed taking into account trade-offs between time and memory requirements. Optional behaviors such as stop at first encountered match, processing of result matches, type of isomorphism and additional features may be enabled thanks to high modularity and library's API.

The RI project also aims to provide a comparison of existing exact subgraph matching algorithms on synthetic and real life graphs. An initial collection of datasets is proposed, it includes synthetic and biological graphs but further types of data regarding other research areas (i.e. engineering, computer vision, etc...) are coming. A list of proposed application is also given.

Please send us an email to get software sources or datasets (see Contacts).

License

RI is distributed under the MIT license. This means that it is free for both academic and commercial use. Note however that some third party components in RI require that you reference certain works in scientific publications.
You are free to link or use RI inside source code of your own program. If do so, please reference (cite) RI and this website. We appreciate bug fixes and would be happy to collaborate for improvements.

Copyright (c) 2013 by Rosalba Giugno
This library contains portions of other open source products covered by separate licenses. Please see the corresponding source files for specific terms.
RI is provided under the terms of The MIT License (MIT):
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Contacts

For software sources, databases, helps and bugs please send an email to Rosalba Giugno giugno@dmi.unict.it and Vincenzo Bonnici vincenzo.bonnici@univr.it.

Developed by:

Vincenzo Bonnici1, Rosalba Giugno2, Alfredo Pulvirenti2, Dennis Shasha3 and Alfredo Ferro2
University of Verona1, University of Catania2 and New York University3
vincenzo.bonnici@univr.com - giugno@dmi.unict.it - apulvirenti@dmi.unict.it - shasha@cs.nyu.edu - ferro@dmi.unict.it

References

If you have used any of the RI project software, please cite the following paper:

Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha and Alfredo Ferro. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics 2013, 14(Suppl 7):S13 doi:10.1186/1471-2105-14-S7-S13.

Cited by

A list of works citing the RI project software:

<< RI seems to be currently the best algorithm for subgraph isomorphism...>>
Vincenzo Carletti, Pasquale Foggia, Mario Vento. Performance Comparison of Five Exact Graph Matching Algorithms on Biological Databases. New Trends in Image Analysis and Processing – ICIAP 2013. Lecture Notes in Computer Science Volume 8158, 2013, pp 409-417.