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.

fast_could_be_isomorphic(G1, G2)

Returns False if graphs are definitely not isomorphic.

faster_could_be_isomorphic(G1, G2)

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.