tree_isomorphism#

tree_isomorphism(t1, t2)[source]#

Return an isomorphic mapping between two trees t1 and t2.

If t1 and t2 are not isomorphic, an empty list is returned. Note that two trees may have more than one isomorphism, and this routine just returns one valid mapping.

Parameters:

t1undirected NetworkX graph

One of the trees being compared

t2undirected NetworkX graph

The other tree being compared

Returns:

isomorphismlist

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.

Raises:

NetworkXError

If either t1 or t2 is not a tree

Notes

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