# 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
```

```
[4]:
```

```
def reduce(graph, colors):
tr = oapackage.reduceGraphNauty(graph, colors=colors, verbose=0)
tri = inverse_permutation(tr)
graph_reduced = oapackage.transformGraphMatrix(graph, tri)
colors_reduced = [colors[idx] for idx in tr]
return graph_reduced, colors_reduced, tr
graph_reduced, colors_reduced, tr = reduce(graph, colors)
print("input graph: ")
print(graph)
print("normal form reduction: %s" % (tr,))
print("reduced graph: ")
print(graph_reduced)
print("colors reduced: %s" % (colors_reduced,))
```

```
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]]
normal form reduction: (1, 2, 0, 4, 3)
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.

```
[5]:
```

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

```
random permutation: [3 2 0 4 1]
```

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]
```

```
[6]:
```

```
graph2_reduced, colors2_reduced, tr2 = reduce(graph2, colors2)
print("input graph: ")
print(graph2)
print("tr2: %s" % (tr2,))
print("reduced graph: ")
print(graph2_reduced)
print("colors2_reduced: %s" % (colors2_reduced,))
```

```
input 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]]
tr2: (4, 1, 2, 3, 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]]
colors2_reduced: [0, 0, 0, 1, 1]
```

Check that the two reduced graphs are equal.

```
[9]:
```

```
if np.all(graph_reduced == graph2_reduced):
print("reduced arrays are equal!")
if np.all(colors_reduced == colors2_reduced):
print("reduced colors are equal!")
```

```
reduced arrays are equal!
reduced colors are equal!
```