# 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

## 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.