# Example script to use Nauty from PythonΒΆ

Nauty can be used to reduce any graph into a normal form. In this notebook, we show how to use the Nauty functionality from Python.

[1]:

import numpy as np
import oapackage


Define a function to invert a permutation.

[2]:

def inverse_permutation(perm):
inverse = [0] * len(perm)
for i, p in enumerate(perm):
inverse[p] = i
return inverse


We define a graph with 5 nodes. The graph is defined by the incidence matrix of size $$5\times 5$$ and a coloring with two colors.

[3]:

graph= np.zeros( (5,5), dtype=int); graph[0,1]=graph[0,2]=graph[0,3]=graph[1,3]=1;
graph = np.maximum(graph, graph.T) # make array symmetric
colors = [0,0,0,1,1]


Reduce the graph to normal form using Nauty.

[4]:

help(oapackage.reduceGraphNauty)

Help on function reduceGraphNauty in module oalib:

reduceGraphNauty(G, colors=None, verbose=1)
Return vertex transformation reducing array to normal form

The reduction is calculated using Nauty <http://users.cecs.anu.edu.au/~bdm/nauty/>_

Args:
G (numpy array or array_link) :   the graph in incidence matrix form
colors (list or None): an optional vertex coloring
Returns:
v: relabelling of the vertices


[6]:

tr = oapackage.reduceGraphNauty(graph, colors=colors, verbose=0)
tri = inverse_permutation(tr)

graph_reduced=oapackage.transformGraphMatrix(graph, tri)

print('normal form reduction: %s' % (tr,))
print('input graph: ')
print(graph)

print('reduced graph: ')
print(graph_reduced)

colorsr=[colors[idx] for idx in tri]
print('colors reduced: %s' % (colorsr,))

normal form reduction: (1, 2, 0, 4, 3)
input graph:
[[0 1 1 1 0]
[1 0 0 1 0]
[1 0 0 0 0]
[1 1 0 0 0]
[0 0 0 0 0]]
reduced graph:
[[0 0 1 0 1]
[0 0 1 0 0]
[1 1 0 0 1]
[0 0 0 0 0]
[1 0 1 0 0]]
colors reduced: [0, 0, 0, 1, 1]


Apply a random permutation to the graph and reduce the graph again.

[7]:

perm = np.random.permutation(5); iperm = inverse_permutation(perm)
print('permutation: %s' % (perm,))
graph2 = graph[perm, :][:,perm]
colors2=[colors[idx] for idx in perm]

permutation: [4 3 2 1 0]


Show the transformed matrix and color vector.

[8]:

print(graph2)
print(colors2)

[[0 0 0 0 0]
[0 0 0 1 1]
[0 0 0 0 1]
[0 1 0 0 1]
[0 1 1 1 0]]
[1, 1, 0, 0, 0]

[9]:

tr2 = oapackage.reduceGraphNauty(graph2, colors=colors2, verbose=0)
tr2i = inverse_permutation(tr2)

colors2r=[colors2[idx] for idx in tr2]

graph2reduced=oapackage.transformGraphMatrix(graph2, tr2i)

print('tr2: %s' % (tr2,))
print('input graph: ')
print(graph2)

print('reduced graph: ')
print(graph2reduced)

print('colors2r: %s' % (colors2r,))

tr2: (3, 2, 4, 0, 1)
input graph:
[[0 0 0 0 0]
[0 0 0 1 1]
[0 0 0 0 1]
[0 1 0 0 1]
[0 1 1 1 0]]
reduced graph:
[[0 0 1 0 1]
[0 0 1 0 0]
[1 1 0 0 1]
[0 0 0 0 0]
[1 0 1 0 0]]
colors2r: [0, 0, 0, 1, 1]


Check that the two reduced graphs are equal.

[10]:

if np.all(graph_reduced==graph2reduced):
print('reduced arrays are equal!')

reduced arrays are equal!