We based our protocol on the ICPR GED contest : https://gdc2016.greyc.fr/ .

Among the data sets available, we chose the GREC data set for two reasons. First, graphs sizes range from 5 to 20 nodes and these sizes are amendable to compute optimal solutions. Second, GREC the cost function defined in the contest is complex enough to cover a large range of matching cases. This cost function is not a constant and includes euclidean distances between point coordinates.

Cost functions :

Code for the cost functions

Node cost function, Edge cost function :

From the GREC database, we chose the subset of graphs called "MIXED" because it holds 10 graphs of various sizes.

<?xml version="1.0"?>

<GraphCollection>

<grec>

<print file="image4_43.gxl" class="4"/>

<print file="image8_7.gxl" class="8"/>

<print file="image22_29.gxl" class="22"/>

<print file="image7_34.gxl" class="7"/>

<print file="image7_37.gxl" class="7"/>

<print file="image7_38.gxl" class="7"/>

<print file="image21_4.gxl" class="21"/>

<print file="image18_14.gxl" class="18"/>

<print file="image18_16.gxl" class="18"/>

<print file="image21_31.gxl" class="21"/>

</grec>

</GraphCollection>

The whole GREC database