CODEWITHSUNDEEP
graph-theorygraph-algorithm
x00
x00

Reputation: 13843

Is there any classical algorithm to transform one tree (or a graph) to another in minimal number of steps

Let's say I have two graphs (trees in this case):

graph 1:
    root
        child_1
            leaf_1, leaf_2, leaf_3
        child_2
            leaf_1, leaf_2, leaf_4

graph 2:
    root
        child_1
            leaf_2, leaf_4
        child_2
            leaf_2, leaf_3

And I want to find the minimal sequence of steps to transform from graph 1 to graph 2.
I have at least two options:

  1.  child_1.delete(leaf_1)
 child_1.delete(leaf_3)
 child_1.add   (leaf_4)

 child_2.delete(leaf_1)
 child_2.delete(leaf_4)
 child_2.add   (leaf_3)

  2.  child_1.delete(leaf_1)

 child_2.delete(leaf_1)

 root  .delete(child_1)
 root  .append(child_1)

So how do I find the minimal sequence in the general case?

Upvotes: 0

Views: 98

Answers (1)

Pamphile
Pamphile

Reputation: 1906

This is related to the Graph Edit Distance (GED) problem (1, 2).

This is a NP-hard problem (3):

Therefore, graph edit distance can also be used to determine the subgraph isomorphism which is NP-Complete.
Then we can derive the following lemma.

Lemma 2.3. GED problem is NP-Hard.

Exact algorithms for computing the GED are generally based on the A* search algorithm (3):

The most widely used method for computing exact graph edit distance is based on the well-known A* algorithm

There are also polynomial approximate/heuristic algorithms (1):

Most of them have cubic computational time

For algorithm implementations, I suggest looking for "graph edit distance" at Github.

References:

Upvotes: 1

Related Questions