Computing Edit Distance between DAGs

[mhnamaki]

Hey, Thanks for sharing this nice library. I have two questions:

• Does it also work for DAGs?
• Can it produce edit distance operators that needed to modify a DAG/Tree to another one?

Best, Mohammad

[mateuszpawlik]

Does it also work for DAGs?

The tree edit distance we have implemented so far works only for rooted and ordered trees. There are works that solve the problem for unordered trees and graphs. However, computing edit distance is NP-complete for those cases.

If you explain your scenario in more details, I may be of more help.

Can it produce edit distance operators that needed to modify a DAG/Tree to another one?

There are two options. (1) You can compute an edit mapping, which tells you which nodes are renamed (mapped), which are deleted, and which inserted. (2) You can also compute an edit script which will list you the operations one by one, such that applying them in order on the source tree gives you the destination tree. So far, I haven't implemented these functionalities in C++. The edit mapping is implemented in the Java version of APTED algorithm.

[mhnamaki]

Thanks for the reply :). Nice work though.

I need to find the edit mapping between two DAGs (assuming we have renaming, deletion, and insertion as operators).

For each DAG, I'm able to add a virtual root and connect it to all the current roots. However, some nodes may have multiple parents which make it a DAG (non-tree).

I wanted to check to see if your current framework works for this case. The programming language doesn't matter :).

Best Mohammad

[mateuszpawlik]

I'd check the graph edit distance solutions. There's many recent works by David Blumenthal including implementations in GEDLIB library. Since the exact graph edit distance is computationally expensive, you may consider approximations.

[mateuszpawlik]

@mhnamaki: If you find a solution for DAG edit distance, please share with us here.

[mhnamaki]

Sure @mateuszpawlik . Thanks for your replies.