Sunday, April 1, 2012

Tree Isomorphism

One interesting problem that has come up recently in this project is to create an algorithm that can efficiently tell if two existential graphs are identical. At first, this sounds like simple tree isomorphism, for which linear time algorithms exist, but its actually more complex then that, since tree isomorphism only compares the structure of the graph, and doesn't check if the variables match up properly. If the graph is highly symmetric, there could be a large number(exponential) of ways that the structure of the graph can be matched, which all have to be checked to make sure the variables match up. This would lead to a very expensive algorithm. Fortunately, we have come up with a efficient (n^2 time) algorithm, which is as follows:

  1. Go through a tree and make a list of all unique variables used in that tree
  2. Make sure that the list is identical to the one for the other tree, otherwise they can't match
  3. Assign each variable in the list a number starting from 2
  4. Go through each tree again, and for every node:
    • If variable n is a child of that node, create a new child node that has n children
    • If the node was empty (no variables or children) create a child node that has one child
  5. Run a tree isomorphism algorithm on the new trees, if they match, then the original graphs were identical

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This problem looks like unification problem (I could be wrong) Please check these links
    just in case:

    http://en.wikipedia.org/wiki/Unification_(computer_science)
    http://stackoverflow.com/questions/4477588/what-is-a-unification-algorithm

    ReplyDelete