Note

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

# Isomorphism¶

 is_isomorphic(G1, G2[, node_match, edge_match]) Returns True if the graphs G1 and G2 are isomorphic and False otherwise. could_be_isomorphic(G1, G2) Returns False if graphs are definitely not isomorphic. Returns False if graphs are definitely not isomorphic. Returns False if graphs are definitely not isomorphic.

## Tree Isomorphism¶

An algorithm for finding if two undirected trees are isomorphic, and if so returns an isomorphism between the two sets of nodes.

This algorithm uses a routine to tell if two rooted trees (trees with a specified root node) are isomorphic, which may be independently useful.

This implements an algorithm from: The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman Addison-Wesley Publishing 1974 Example 3.2 pp. 84-86.

A more understandable version of this algorithm is described in: Homework Assignment 5 McGill University SOCS 308-250B, Winter 2002 by Matthew Suderman http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf

 rooted_tree_isomorphism(t1, root1, t2, root2) Given two rooted trees t1 and t2, with roots root1 and root2 respectivly this routine will determine if they are isomorphic. tree_isomorphism(t1, t2) Given two undirected (or free) trees t1 and t2, this routine will determine if they are isomorphic.