In this page a brief documentation of the ARG Database will be provided. More details can be found in this file.
The graph files
The graphs directory that you can download here contains 168 .zip files in which the actual graph files are stored in a compressed format. You will need a decompression utility able to deal with the .zip format in order to extract the graph files, if you have not yet installed one.
The name of the .zip files reflect the kind of graphs that are stored in the corresponding archives; in particular, the name is made of a prefix, which indicates the type of matching that holds between the graphs, and an identifier of the type of graphs (see section References for more details on the graph types). In TABLE 1 there is a list of prefixes with the corresponding meaning; TABLE 2 contains the description of the identifiers used for the types.
The prefix and the type identifier are separated by an underscore (“_”). Examples:
- The file si2_m2D.zip has the prefix si2, meaning that it contains pairs of graphs for which there is a graph-subgraph isomorphism relation, and the subgraph contain 20% of the nodes of the full graph; the type identifier is m2D, corresponding to bidimensional meshes with no additional random edges.
- The file mcs10_m2D.zip has the prefix mcs10, meaning that it contains pairs of graphs holding a common subgraph whose size is 10% of the size of the graphs; the type identifier is m2D, corresponding to bidimensional meshes with no additional random edges.
| Prefix | Description |
|---|---|
| iso | Pairs of isomorphic graphs |
si2 |
Pairs of graph-subgraph isomorphic unlabeled graphs; the subgraph size is 20% of the full graph |
si4 |
Pairs of graph-subgraph isomorphic unlabeled graphs; the subgraph size is 40% of the full graph |
si6 |
Pairs of graph-subgraph isomorphic unlabeled graphs; the subgraph size is 60% of the full graph |
mcs10 |
Pairs of labeled graphs, whose maximum common subgraph size is 10% of the graph size |
mcs30 |
Pairs of labeled graphs, whose maximum common subgraph size is 30% of the graph size |
mcs50 |
Pairs of labeled graphs, whose maximum common subgraph size is 50% of the graph size |
mcs70 |
Pairs of labeled graphs, whose maximum common subgraph size is 70% of the graph size |
mcs90 |
Pairs of labeled graphs, whose maximum common subgraph size is 90% of the graph size |
| Identifier | Description |
|---|---|
r001 |
randomly generated graphs with eta = 0.01 |
r005 |
randomly generated graphs with eta = 0.05 |
r01 |
randomly generated graphs with eta = 0.1 |
r02 |
randomly generated graphs with eta = 0.2 |
m2D |
bi-dimensional meshes with rho = 0 |
m2Dr2 |
bi-dimensional meshes with rho = 0.2 |
m2Dr4 |
bi-dimensional meshes with rho = 0.4 |
m2Dr6 |
bi-dimensional meshes with rho = 0.6 |
m3D |
tri-dimensional meshes with rho = 0 |
m3Dr2 |
tri-dimensional meshes with rho = 0.2 |
m3Dr4 |
tri-dimensional meshes with rho = 0.4 |
m3Dr6 |
tri-dimensional meshes with rho = 0.6 |
m4D |
quadri-dimensional meshes with rho = 0 |
m4Dr2 |
quadri-dimensional meshes with rho = 0.2 |
m4Dr4 |
quadri-dimensional meshes with rho = 0.4 |
m4Dr6 |
quadri-dimensional meshes with rho = 0.6 |
b03 |
bounded-valence graphs with valence = 3 |
b03m |
modified bounded-valence graphs with valence = 3 |
b06 |
bounded-valence graphs with valence = 6 |
b06m |
modified bounded-valence graphs with valence = 6 |
b09 |
bounded-valence graphs with valence = 9 |
b09m |
modified bounded-valence graphs with valence = 9 |
The files inside each .zip archive are divided into subdirectories, using three levels of grouping. The first level correspond to the type of matching, and the directories are named using the prefixes of TABLE 1. The second level groups together similar graph types; TABLE 2 shows the names of the directories, and the graph types they contain. Finally, the third level corresponds to graph types, and the directories are named after TABLE 2. For example, the graphs in the file si4_r01.zip get expanded into the directory si4/rand/r01/.
| Group | Corresponding types |
|---|---|
| rand | r001, r005, r01 ,r02 |
| m2D | m2D, m2Dr2, m2Dr4, m2Dr6 |
| m3D | m3D, m3Dr2, m3Dr4, m3Dr6 |
| m4D | m4D, m4Dr2, m4Dr4, m4Dr6 |
| bvg | b03, b03m, b06, b06m, b09, b09m |
Type groups
The name of the graph files in each .zip archive are obtained from the name of the .zip file by adding a suffix and an extension. The suffix, separated by an underscore (“_&”) from the graph type identifier, indicates the number of nodes in the graphs. The first letter of the suffix is “s“; for small graphs (i.e. up to 100 nodes) and “m” for medium-sized graphs (i.e. above 100 nodes but below 2000); after this letter, there is the decimal representation of the number of nodes. The file extension (separated by a period “.” from the rest of the file name) is made of a letter, which can be “A” or “B“, and two digits, forming a number from 00 to 99, that identifies one of the pairs of matching graphs. Within the pair, the graph with the “A” in the filename extension is the subgraph, for the subgraph-isomorphism matching types. For example, a graph file name could be mcs50_r01_s15.A27, meaning that the graph is the first of the pair #27 of randomly-generated graphs having a maximum common subgraph whose dimension is 50% of size of the graphs, with eta=0.01 and having 15 nodes.
The graph file format
The graphs are stored in a compact binary format, one graph per file. The file is composed of 16 bit words, which are represented using the so-called little-endian convention, i.e. the least significant byte of the word is stored first. Two different formats are used for labeled and unlabeled graphs. The functions to read these two different formats are provided below.
How to read unlabeled graphs
How to read labeled graphs
The ground truth files
For each .zip file in the graphs directory there is a corresponding .gtr file containing the ground truth regarding the pairs of graphs in the .zip archive. For example, the ground truth of the file iso_b03.zip is in iso_b03.gtr.
A ground truth file is a text file containing a line for each pair of graphs in the .zip file;
- Unlabeled graphs. The line has two fields, separated by a TAB character (ASCII 9), and is terminated by a LF character (ASCII 10). The first field is the name of the first graph of the pair, while the second field is the number of matchings found.
- Labeled graphs. The line has four fields, separated by a TAB character (ASCII 9), and is terminated by a LF character (ASCII 10). The first field is the name of the first graph of the pair, while the other fields are the number of matchings found. More in details, the second field is the number of maximum common sungraphs when the number of attributes of the graphs is fixed to 33% of graph size. Analogously, the third and the fourth fields are respectively the number of maximum common subgraphs when the number of attributes is fixed to 50% and 75% of the graph size.
For example, a line of the iso_b03.gtr file could be iso_b03_m1000.A00 1 to signify that between the graphs iso_b03_m1000.A00 and iso_b03_m1000.B00 there is only one isomorphism, while a line of the mcs10_b03.gtr file could be mcs10_b03_s20.A00 1 2 1 meaning that the graphs mcs10_b03_s20.A00 and mcs10_b03_s20.B00 holds respectively one, two and one maximum common subgraph when the number of attributes of the graphs is fixed to 33%, 50% and 75% of graph size.
All the graph pairs in the iso_* files are present in the corresponding ground truth files. However, for graph-subgraph isomorphisms, and for maxmum common subgraphs only a subset of the pairs have been accounted for in the ground truth files, due to the considerably larger computation time needed to generate this information.
Graphs Generator
The source files of the programs used to generate the graphs composing the database can be found here. These programs have been developed and used under Linux, and are not completely portable to other operating systems, since they use the /dev/urandom pseudo-device for initializing the random number generator. Each program generates a pair of graphs; we have used shell scripts to call repeatedly the programs with the proper arguments for generating the whole database.
In the following table there is an outline of the programs and of their command line arguments.
| Name | Arguments | Types generated |
|---|---|---|
gen |
nodes edges file1 file2 | iso*r001, iso*r005, iso*r01 |
gensub |
subgraph-nodes nodes edges file1 file2 | si*r001, si*r005, si*r01 |
genm2D |
nodes extra-edges file1 file2 | iso*m2D, iso*m2Dr2, iso*m2Dr4, iso*m2Dr6 |
gensubm2D |
subgraph-nodes nodes extra-edges file1 file2 | si*m2D, si*m2Dr2, si*m2Dr4, si*m2Dr6 |
genm3D |
nodes extra-edges file1 file2 | iso*m3D, iso*m3Dr2, iso*m3Dr4, iso*m3Dr6 |
gensubm3D |
subgraph-nodes nodes extra-edges file1 file2 | si*m3D, si*m3Dr2, si*m3Dr4, si*m3Dr6 |
genm4D |
nodes extra-edges file1 file2 | iso*m4D, iso*m4Dr2, iso*m4Dr4, iso*m4Dr6 |
gensubm4D |
subgraph-nodes nodes extra-edges file1 file2 | si*m4D, si*m4Dr2, si*m4Dr4, si*m4Dr6 |
genbvg |
nodes valence file1 file2 | iso*b03, iso*b06, iso*b09 |
gensubbvg |
subgraph-nodes nodes valence file1 file2 | si*b03, si*b06, si*b09 |
genbvgm |
nodes valence file1 file2 | iso*b03m, iso*b06m, iso*b09m |
gensubbvgm |
subgraph-nodes nodes valence file1 file2 | si*b03m, si*b06m, si*b09m |
genrndat |
nodes nodesub edges edgesub file1 file2 | mcs*r005, mcs*r01, mcs*r02 |
genm2Dat |
nodes nodesub edges extra-edgesub file1 file2 | mcs*m2D, mcs*m2Dr2, mcs*m2Dr4, mcs*m2Dr6 |
genm3Dat |
nodes nodesub edges extra-edgesub file1 file2 | mcs*m3D, mcs*m3Dr2, mcs*m3Dr4, mcs*m3Dr6 |
genm4Dat |
nodes nodesub edges extra-edgesub file1 file2 | mcs*m4D, mcs*m4Dr2, mcs*m4Dr4, mcs*m4Dr6 |
genbvgat |
nodes nodesub edges valence file1 file2 | mcs*b03, mcs*b06, mcs*b09 |
genbvgmat |
nodes nodesub edges valence file1 file2 | mcs*b03m, mcs*b06m, mcs*b09m |
For each program there is one source file with extension .cc. The programs gen, gensub, genm2D and gensubm2D need to be linked with the VFLIB graph matching library. All other files are self-contained.