Example: Checking for isomorphic graphs

The main use of nauty is to determine if two graphs are isomorphic. We can demonstrate it for two given graphs with the method areIsomorphic.

i1 : R = QQ[a..e];

i2 : G = graph {{a, c}, {c, e}, {e, b}, {b, d}, {d, a}};

i3 : areIsomorphic(cycle R, G)

o3 = true

Further, a list of graphs can be reduced to only graphs that are non-isomorphic with the method removeIsomorphs. Here we create a list of 120 different labellings of the 5-cycle and use nauty to verify they are indeed all the same.

i4 : L = apply(permutations gens R, P -> graphToString graph apply(5, i-> {P_i, P_((i+1)%5)}));

i5 : N = removeIsomorphs L

o5 = {Dhc}

o5 : List

i6 : stringToGraph(first N, R)

o6 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}
           "ring" => R
           "vertices" => {a, b, c, d, e}

o6 : Graph

Example: Checking for isomorphic graphs

See also