Isomorphic Trees - AHU Algorithm

Isomorphic trees are trees that have the same shape or structure, but may differ in the labels of their nodes. In other words, two trees are isomorphic if one can be transformed into the other by renaming the nodes.

For example, consider the two binary trees below:

Although the labels of the nodes in the two trees are different, the shape or structure of the trees is the same. We can transform the tree (A) into the tree (B) by renaming its nodes as follows:

A -> X
B -> Z
C -> Y
D -> I
E -> J

Similarly, two graphs are isomorphic if they have the same connectivity pattern, even if their vertices and edges are labeled differently.

AHU Algorithm

The AHU algorithm is a well-known algorithm for testing isomorphism of rooted trees. The algorithm was developed by Alfred Aho, John Hopcroft, and Jeffrey Ullman, and is named after their initials.

The AHU algorithm works by comparing the canonical form of two trees to determine if they are isomorphic.

The canonical form of a tree is a unique labeling of the nodes of the tree such that isomorphic trees have the same canonical form. The labeling is obtained by assigning a rank to each node in the tree based on its subtree structure.

The rank of a node is a string that represents the ranks of its children, ordered lexicographically (lexicographic order is the ordering of words or strings based on the alphabetical order of their component letters).

The canonical form of a tree is obtained by labeling the nodes in post-order traversal, using the ranks of their children to compute their own rank.

To use the AHU algorithm to test the isomorphism of two trees T1 and T2:

1. Compute the canonical form of T1 and T2.
2. Compare the canonical forms of T1 and T2 to determine if they are equal. If they are equal, then T1 and T2 are isomorphic. If they are not equal, then T1 and T2 are not isomorphic.

The AHU algorithm has a time complexity of O(n log n), where n is the number of nodes in the trees. This makes it one of the most efficient algorithms for testing the isomorphism of trees.

Note that the AHU algorithm only works for rooted trees, where each node has at most one parent. It cannot be used for testing the isomorphism of general graphs.

Steps

1. Find center(s) of both trees. If there are multiple centers, tree needs to be rooted at all centers
2. Root the tree at the center node(s)
3. Run AHU algorithm, and collect ranks i.e. perform post order traversal on tree, assign ranks and sort them lexicographically
4. If both tree has same ranks for any centers, trees are isomorphic

The following articles provide more information on finding tree centers and rooting trees

• How to find center(s) of a tree
• How to root a tree

Example

• Following script check if the above given trees (A & B) are isomorphic or not. Each node is assigned a tuple () upon visiting until a sorted string rank is calculated for whole tree

fun getExampleATree(): Map<String, List<String>> {
    return mutableMapOf<String, List<String>>().apply {
        put("1", listOf("2", "3"))
        put("2", listOf("4", "1"))
        put("3", listOf("5"))
        put("4", listOf("2"))
        put("5", listOf("3"))
    }
}

fun getExampleBTree(): Map<String, List<String>> {
    return mutableMapOf<String, List<String>>().apply {
        put("a", listOf("b", "c"))
        put("b", listOf("d", "a"))
        put("c", listOf("a"))
        put("d", listOf("e"))
        put("e", listOf("d"))
    }
}

//sampleStart
fun main() {
    // click + to see full script
    val adjacencyMapA = getExampleATree()
    val adjacencyMapB = getExampleBTree()

    val centersA = findCenter(adjacencyMapA)
    val centersB = findCenter(adjacencyMapB)
    println("center(s) of Tree (A) -> $centersA")
    println("center(s) of Tree (B) -> $centersB")

    val treeARanks = mutableListOf<String>()
    val treeBRanks = mutableListOf<String>()

    // if there are multiple centers, tree is rooted for each center
    // and rank is calculated
    centersA.forEach { center ->
        val root = TreeNode(value = center, parent = null,
                children = mutableListOf())
        rootTreeAtNode(root, adjacencyMapA)
        treeARanks.add(getTreeRank(root))
    }
    centersB.forEach { center ->
        val root = TreeNode(value = center, parent = null,
                children = mutableListOf())
        rootTreeAtNode(root, adjacencyMapB)
        treeBRanks.add(getTreeRank(root))
    }

    treeARanks.forEach {
        if (treeBRanks.contains(it)) {
            println("trees are isomorphic")
        }
    }
}

fun getTreeRank(tree: TreeNode): String {
    fun postOrderTraversal(node: TreeNode): String {
        // assign rank to this node and append ranks for all
        // child nodes to its rank
        val ranks = StringBuilder().append("()")
        node.children.forEach {
            ranks.append(postOrderTraversal(it))
        }
        return ranks.toString()
    }
    // sort the rank lexicographically
    val treeRank = postOrderTraversal(tree).toCharArray().also { it.sort() }
    return treeRank.concatToString()
}

fun findCenter(adjacencyMap: Map<String, List<String>>): List<String> {
    val degree = mutableMapOf<String, Int>()
    var leaves = mutableListOf<String>()

    adjacencyMap.keys.forEach { node ->
        degree[node] = degree.getOrDefault(node, 0).plus(
                adjacencyMap.getValue(node).size
        )
        val isLeafNode = degree[node] == 0 || degree[node] == 1
        if (isLeafNode) {
            leaves.add(node)
        }
    }


    val noOfNodes = adjacencyMap.keys.size
    var currentLeaveCount = leaves.size

    while (currentLeaveCount < noOfNodes) {
        val newLeaves = mutableListOf<String>()
        leaves.forEach { leafNode ->
            adjacencyMap[leafNode]?.forEach { adjacentNode ->
                degree[adjacentNode] = degree.getValue(adjacentNode) - 1
                // add adjacent node to leave if degree became 0 after update
                if (degree[adjacentNode] == 1) {
                    newLeaves.add(adjacentNode)
                }
            }
            degree[leafNode] = 0
        }
        currentLeaveCount += newLeaves.size
        leaves = newLeaves
    }
    return leaves
}

class TreeNode(
        val value: String,
        val parent: TreeNode? = null,
        val children: MutableList<TreeNode> = mutableListOf(),
)

fun rootTreeAtNode(node: TreeNode, adjacencyMap: Map<String, List<String>>) {
    adjacencyMap.getValue(node.value).forEach { adjacentNode ->
        if (node.parent?.value != adjacentNode) {
            val childNode = TreeNode(value = adjacentNode, parent = node)
            node.children.add(childNode)
            rootTreeAtNode(childNode, adjacencyMap)
        }
    }
}
//sampleEnd