Edit distance between two graphs

algorithm language-agnostic levenshtein-distance edit-distance
linello picture linello · May 6, 2013 · Viewed 9.4k times · Source

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.

Answer

jason.Z picture jason.Z · Jun 10, 2013

I think graph edit distance is the measure that you were looking for.

Graph edit distance measures the minimum number of graph edit operations to transform one graph to another, and the allowed graph edit operations includes:

  • Insert/delete an isolated vertex
  • Insert/delete an edge
  • Change the label of a vertex/edge (if labeled graphs)

However, computing the graph edit distance between two graphs is NP-hard. The most efficient algorithm for computing this is an A*-based algorithm, and there are other sub-optimal algorithms.

Related questions

Getting the closest string match

I need a way to compare multiple strings to a test string and return the string that closely resembles it: TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW CHOICE A : THE RED COW JUMPED OVER THE GREEN CHICKEN …

Read More
What algorithm gives suggestions in a spell checker?

What algorithm is typically used when implementing a spell checker that is accompanied with word suggestions? At first I thought it might make sense to check each new word typed (if not found in the dictionary) against it's Levenshtein distance …

Read More
What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

Read More