What is the maximum edit distance between two graphs?

jacquesfize / GMatch4py

A graph matching library for Python

MIT License

193 stars 40 forks source link

What is the maximum edit distance between two graphs? #29

Open martinwz opened 3 years ago

martinwz commented 3 years ago

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 commented 2 years ago

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