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 : G = graph {{1,2},{2,3},{3,4},{4,5},{1,5}};

i2 : H = graph {{1,3},{3,5},{5,2},{2,4},{4,1}};

i3 : areIsomorphic(G, H)

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 = graphToString \ apply(permutations 5, P -> graph apply(5, i -> {P_i, P_((i+1)%5)}));

i5 : N = removeIsomorphs L

o5 = {Dhc}

o5 : List

i6 : stringToGraph first N

o6 = Graph{0 => {1, 4}}
           1 => {0, 2}
           2 => {1, 3}
           3 => {2, 4}
           4 => {0, 3}

o6 : Graph

Example: Checking for isomorphic graphs

See also