Binaries and Source code
General instructions
General instructions
Code and implementation
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
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
Matheuristics
Local Branching (LocBra) + Justice and Hero (JH) model
Local Branching (LocBra) + Justice and Hero (JH) model
- Binaries: MIP_JH_LB_Binaries
- Source code: MIP_JH_LB
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
Local Branching (LocBra) + F3 model
- Binaries: MIPGED_MOR_LB_Binaries
- Source code: MIP_MOR_LB
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
Variable Partitioning Local Search (VPLS) + F3 model
- Binaries: VPLS_MOR_Binaries
- Source code: VPLS_MOR
Ref. [Darwiche et al. (2019). Solving the graph edit distance problem with variable partitioning local search. GbR19]
Mixed Integer Linear Programs (MILP)
Mixed Integer Linear Programs (MILP)
F3 model
F3 model
- Binaries: MIPGED_MOR_Binaries
- Source code: MIPGED_MOR
Ref. [Darwiche et al. (2018). Graph Edit Distance in the exact context. S+SSPR]
Object-based Model (ObM)
Object-based Model (ObM)
- Source code: MIPGED_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)
Vertex-based Model (VbM)
- Source code: MIPGED_VbM
Ref. Thesis manuscript - Section 5.2.1
JH model
JH model
- Source code: MIPGED_JH
Ref. [Justice and Hero (2006). A binary linear programming formulation of the graph edit distance. TPAMI]
F2 model
F2 model
- Source code: MIPGED_F2
Ref. [Lerouge et al. (2017). New binary linear programming formulation to compute the graph edit distance. PR]
F1 model
F1 model
- Source code: MIPGED_F1
Ref. [Lerouge et al. (2017). New binary linear programming formulation to compute the graph edit distance. PR]
Heuristics
Heuristics
Integrated Projected Fixed Point (IPFP) and Graduated Non Convexity and Concavity Procedure (GNCCP) heuristics
Integrated Projected Fixed Point (IPFP) and Graduated Non Convexity and Concavity Procedure (GNCCP) heuristics
- Source code: IPFP_GNCCP
Ref. [Bougleux et al. (2017). Graph edit distance as a quadratic assignment problem. PRL]
Converter GXL - DAT
Converter GXL - DAT
Example of a graph in DAT format
Example of a graph in DAT format
- Original GXL file: house.seq0.gxl (taken from CMUHOUSE database)
- DAT file : house.seq0.dat
Source Code
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.