What is the maximum edit distance between two graphs?

[martinwz]

Hi, I have a question about the maximum graph edit distance between two graphs. If Graph A has M nodes, B has N nodes, what is the maximum graph edit distance calculated by GMatch4py between A and B? Is there an upper bound? Whether the maximum graph editing distance depends on M and N? Finally, which paper presented the calculation algorithm used in GMatch4py? Looking forward to reply!

[NicolasMICAUX]

upper bound => i think not if you want bounded metrics, use ged.distance or ged.similarity

Finally, which paper presented the calculation algorithm used in GMatch4py? I found that some algos are referenced in the docstrings e.g. Implementation of Hausdorff Edit Distance described in Improved quadratic time approximation of graph edit distance by Hausdorff matching and greedy assignement Andreas Fischer, Kaspar Riesen, Horst Bunke 2016 in gmatch4py/ged/hausdorff_edit_distance.pyx