Graph database

VF3 is a graph matching algorithm, specialized in solving graph isomorphism and graph-subgraph isomorphism. In particular, it is able to solve both testing and listing problems, being able to determine not only if the isomorphism exists (testing) but also where and how many times a pattern graph is present inside the target graph (listing).

The MIVIA LDGraphs (MIVIA Large Dense Graphs) dataset is a new dataset for benchmarking exact graph matching algorithms. It aims to extend the MIVIA graphs dataset, widely used in the last ten years, with bigger and more dense graphs, so as to face with the problems nowadays encountered in real applications devoted for instance to bioinformatics and social network analysis.

The ARG Database is a huge collection of labeled and unlabeled graphs. The aim of this collection is to provide the graph research community with a standard test ground for the benchmarking of graph matching algorithms.The database is organized in two section: labeled and unlabeled graphs. Both labeled and unlabeled graphs have been randomly generated according to different generation models (2D, 3D and 4D regular meshes, 2D, 3D and 4D nearly-regular meshes, bounded valence, nearly-bounded valence, randomly generated) regular, each involving different possible parameter settings. As a result, 168 diverse kinds of graphs are contained in the database. Each type of unlabeled graph is represented by thousands of pairs of graphs for which an isomorphism or a graph-subgraph isomorphism relation holds, for a total of 143,600 graphs. Furthermore, each type of labeled graph is represented by thousands of pairs of graphs holding a not trivial common subgraph, for a total of 166,000 graphs. Currently graphs have size ranging from a few up to thousands of nodes.

This 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 web page contains the library documentation, including some usage examples, and the source files of the library.