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

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

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

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)

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)

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)

Source code: MIPGED_VbM

Ref. Thesis manuscript - Section 5.2.1

JH model

Source code: MIPGED_JH

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

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

Source code: MIPGED_F1

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

Source code: IPFP_GNCCP

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

Converter GXL - DAT

Example of a graph in DAT format

Original GXL file: house.seq0.gxl (taken from CMUHOUSE database)
DAT file : house.seq0.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.

Google Sites

Report abuse