#

Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

#

networkx.algorithms.isomorphism.tree_isomorphism.tree_isomorphism

tree_isomorphism(t1, t2)[source]

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 – 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.

Return type

list

Notes

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