Binaries and Source code

General instructions

Code and implementation

  • All methods are implemented in C/C++ (unless indicated otherwise).
  • Each compressed file contains a README file. Please have a look at this file for more details about how to import/configure/execute the code. It also explains how to integrate CPLEX libraries into the project.
  • All the below projects/executables require the input graphs to be in DAT format. The basic graph files format is GXL, however since the code is written in C, the format was modified to make the parser faster by getting rid of the XML tags and long structures. Please refer to the last section in this page the GXL to DAT format is given in C#.
  • Graph instances: Each project/executable receives two graph files as inputs, along with other parameters. So in order to run a method with multiple instances, the executable must be called in a (batch file)-type code to pass each time a different instance. An alternative is to get the source code and modify it to consider all database instances.

Databases and cost functions

All databases used in the experiments can be found online (see page Graph Databases).

Please refer to the manuscript (Section 4.2) for details and explanations about each database and its cost functions.

The cost functions implementation for each database can be found in a class called "GMEntity.cpp" in any of the below source code project.

Matheuristics

Local Branching (LocBra) + Justice and Hero (JH) model


Ref. [Darwiche et al. (2019). A local branching heuristic for solving a Graph Edit Distance Problem. C&OR] Ref. [Darwiche et al. (2018). Graph Edit Distance: Accuracy of Local Branching from an application point of view. PRL]

Local Branching (LocBra) + F3 model


Ref. [Darwiche et al. (2019). Résoudre le problème de la distance d'édition entre graphes avec les matheuristiques. ROADEF19]

Variable Partitioning Local Search (VPLS) + F3 model


Ref. [Darwiche et al. (2019). Solving the graph edit distance problem with variable partitioning local search. GbR19]

Mixed Integer Linear Programs (MILP)

F3 model


Ref. [Darwiche et al. (2018). Graph Edit Distance in the exact context. S+SSPR]

Object-based Model (ObM)


Ref. [Darwiche et al. (2018). Formulation linéaire en nombres entiers pour le problème de la distance d'édition entre graphes. ROADEF18]

Vertex-based Model (VbM)


Ref. Thesis manuscript - Section 5.2.1

JH model


Ref. [Justice and Hero (2006). A binary linear programming formulation of the graph edit distance. TPAMI]

F2 model


Ref. [Lerouge et al. (2017). New binary linear programming formulation to compute the graph edit distance. PR]

F1 model


Ref. [Lerouge et al. (2017). New binary linear programming formulation to compute the graph edit distance. PR]

Heuristics

Integrated Projected Fixed Point (IPFP) and Graduated Non Convexity and Concavity Procedure (GNCCP) heuristics


Ref. [Bougleux et al. (2017). Graph edit distance as a quadratic assignment problem. PRL]

Converter GXL - DAT

Example of a graph in DAT format

Source Code

This is a C# class that converts a database of GXL files into DAT files, which can later be used as inputs to the above projects/executables.

Usage: the dir variable needs to be changed, pointing to the folder with the GXL files are. The code will create a new folder at the same level with "_DAT" added to the original folder name.