rooted_tree_isomorphism

rooted_tree_isomorphism(t1, root1, t2, root2)

Return an isomorphic mapping between rooted trees t1 and t2 with roots root1 and root2, respectively.

These trees may be either directed or undirected, but if they are directed, all edges should flow from the root.

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. This is a subroutine used to implement tree_isomorphism, but will be somewhat faster if you already have rooted trees.

Parameters:

t1NetworkX graph

One of the trees being compared

root1node

A node of t1 which is the root of the tree

t2NetworkX graph

The other tree being compared

root2node

a node of t2 which is the root of the tree

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