algorithmlanguage-agnosticlevenshtein-distanceedit-distance

Edit distance between two graphs

I'm just wondering if, like for strings where we have the Levenshtein distance (or edit distance) between two strings, is there something similar for graphs?

I mean, a scalar measure that identifies the number of atomic operations (node and edges insertion/deletion) to transform a graph G1 to a graph G2.

Solution

  • Currently, the most efficient exact answer is Depth-First Graph Edit Distance (DF-GED), from An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. An implementation exists in Python's networkx library as the function optimal_edit_paths, among other related functions.