May 15, 2013

VF Library

The library

The VFLib graph matching library is a graph matching library which provides several algorithms for graph isomorphism, graph-subgraph isomorphism and graph monomorphism. The library is an efficient implementation of the VF2 graph matching algorithm, currently among the fastest ones, able to process very huge graphs due to its linear memory complexity. The library is written in C++, and can be easily adapted to use different formats for the graphs, and different types of attributes.
The library documentation, including some usage examples, can be downloaded here.


Download

The software and the library documentation can be downloaded by requesting it at the following link.


References

If you use this library please cite:

  • A (sub)graph isomorphism algorithm for matching large graphs

Other reference papers are:

  • A large database of graphs and its use for benchmarking graph isomorphism algorithms
  • A performance comparison of five algorithms for graph isomorphism
  • An Algorithm for Subgraph Isomorphism
  • A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices

Useful papers are:

  • Thirty years of graph matching in pattern recognition
    A recent paper posed the question: “Graph Matching: What are we really talking about?”. Far from providing a definite answer to that question, in this paper we will try to characterize the role that graphs play within the Pattern Recognition field. To this aim two taxonomies are presented and discussed. The first includes almost all the graph matching algorithms proposed from the late seventies, and describes the different classes of algorithms. The second taxonomy considers the types of common applications of graph-based techniques in the Pattern Recognition and Machine Vision field.

  • Graph-Based Methods in Computer Vision: Developments and Applications
    Many computer vision applications require a comparison between two objects, or between an object and a reference model. When the objects or the scenes are represented by graphs, this comparison can be performed using some form of graph matching. The aim of this chapter is to introduce the main graph matching techniques that have been used for computer vision, and to relate each application with the techniques that are most suited to it.


The algorithm

A presentation of some of the algorithms implemented in our VFLib can be found here. (Available soon!!)


Contributions

  • Brian Kelley, at MIT Whitehead Institute for Biomedical Research, has developed a Python interfaceto VFLib, which can be found using this link. Brian has used this binding in his FROWNS chemioinformatics system.Python is a very popular scripting language, with object orientation, a clean syntax, and a very large library, making it one of the most powerful tools for complex application prototyping. See www.python.org for more information on this language.
  • VF2 has been included in Boost C++ library, widely used by the scientific community since providing support for tasks and structures such as linear algebra, image processing, regular expressions etc.
  • VF2 has been included in NetworkX 2.0 Python library

Applications

Some of the applicative domains where the VF method has been used are the following:

  • Virtual Network Mapping
  • Design of systems-on-chip
  • RDF Index
  • Biological Networks
  • Molecules detector
  • Automated Discovery of Custom Instructions
  • Disk-based graph indexing techniques

If you use this method in your application, please contact us in order to update this list!


Help

If you have any problems, do not hesitate to contact us here.