Skip to main content
`Ctrl`+`K`

# tree_isomorphism

tree_isomorphism(t1, t2)

  Given two undirected (or free) trees `t1` and `t2`, this routine will determine if they are isomorphic. It returns the isomorphism, a mapping of the nodes of `t1` onto the nodes of `t2`, such that two trees are then identical.

  Note that two trees may have more than one isomorphism, and this routine just returns one valid mapping.

  Parameters:
    t1 undirected NetworkX graph

      One of the trees being compared

    t2 undirected NetworkX graph

      The other tree being compared

  Returns:
    isomorphism list

      A list of pairs in which the left element is a node in `t1` and the right element is a node in `t2`. The pairs are in arbitrary order. If the nodes in one tree is mapped to the names in the other, then trees will be identical. Note that an isomorphism will not necessarily be unique.

      If `t1` and `t2` are not isomorphic, then it returns the empty list.

  Notes

  This runs in O(n*log(n)) time for trees with n nodes.