User’s Guide¶
The pynauty module provides a Graph class to represent graphs and functions for isomorphism testing and computing automorphism groups of graphs. The graphs can be undirected or directed. They can contain loops but no multiple edges. There is always a vertexcoloring associated with them. Ordinary, that is not vertexcolored, graphs can be represented with all vertices having the same color.
Vertex Coloring¶
Let V be the set of vertices of a graph G. A partition of vertices is a collection of nonempty and pairwise disjoint subsets (parts) of V such that the union of these subsets is V. A vertexcoloring defines a partition of vertices, with vertices of the same color belonging to the same part. Similarly, a partition of vertices defines a vertexcoloring by giving the same distinct color to vertices in the same part. So vertexcoloring and partition of vertices are essentially the same.
In pynauty, a vertexcoloring is specified as an ordered partition of vertices. The order of parts is significant but the order of vertices within each part is not. Such an ordered partition is represented by a list of sets where each set in the list specifies a subset of the vertex set. So the color of a vertex is the index of the part containing the vertex. The subsets must be nonempty and pairwise disjoint. It is not a requirement to cover all vertices, all the vertices not appearing are put together in a single part of their own.
The significance of vertexcoloring while computing with graphs in pynauty is the following. The partition induced by a vertex coloring imposes the restriction on possible automorphisms of the graph that vertices must stay in their original part (i.e. keep their color) under any automorphism.
Two vertexcolored graphs are isomorphic if there is a bijection between their vertex sets which preserves adjacency and color.
Classes¶

class
pynauty.
Graph
(number_of_vertices, directed=False, adjacency_dict={}, vertex_coloring=[])[source]¶ Graph instantiates an adjacency dictionary based graph object. It can represent vertex colored, directed or undirected graphs.

connect_vertex
(v, neighbors)[source]¶ Connect a vertex to some other vertices.
 v
 A vertex of the Graph. The tail of the arcs if the Graph is directed.
 neighbors
 A vertex or a list of vertices to which v should be connected. The heads of the arcs if the Graph is directed.

Functions¶

pynauty.
autgrp
(g)[source]¶ Compute the automorphism group of a graph.
 g
 A Graph object.
 return > (generators, grpsize1, grpsize2, orbits, numorbits)
 For the detailed description of the returned components, see Nauty’s documentation.

pynauty.
isomorphic
(a, b)[source]¶ Determine if two graphs are isomorphic.
 a,b
 Two Graph objects.
 return >
 True if a and b are isomorphic graphs, False otherwise,
Examples¶
These examples show using pynauty in interactive sessions. We assume that the pynauty module has been imported by:
>>> from pynauty import *
Create a Graph object by connetcting some vertices step by step:
>>> g = Graph(5)
>>> g.connect_vertex(0, [1, 2, 3])
>>> g.connect_vertex(2, [1, 3, 4])
>>> g.connect_vertex(4, [3])
>>>
>>> print(g)
Graph(number_of_vertices=5, directed=False,
adjacency_dict = {
0: [1, 2, 3],
2: [1, 3, 4],
4: [3],
},
vertex_coloring = [
],
)
The same graph can be created in one step by supplying the adjacency relations to Graph:
>>> g = Graph(number_of_vertices=5, directed=False,
... adjacency_dict = {
... 0: [1, 2, 3],
... 2: [1, 3, 4],
... 4: [3],
... },
... )
>>>
Compute the automorphism group of the graph:
>>> autgrp(g)
([[3, 4, 2, 0, 1]], 2.0, 0, [0, 1, 2, 0, 1], 3)
>>>
Let’s add a new edge and see how the automorphism group would change:
>>> g.connect_vertex(1, [3])
>>> print(g)
Graph(number_of_vertices=5, directed=False,
adjacency_dict = {
0: [1, 2, 3],
1: [3],
2: [1, 3, 4],
4: [3],
},
vertex_coloring = [
],
)
>>> autgrp(g)
([[0, 1, 3, 2, 4], [1, 0, 2, 3, 4]], 4.0, 0, [0, 0, 2, 2, 4], 3)
>>>
Fixing vertex 3 by coloring reduces the automorphism group:
>>> g.set_vertex_coloring([set([3])])
>>> print(g)
Graph(number_of_vertices=5, directed=False,
adjacency_dict = {
0: [1, 2, 3],
1: [3],
2: [1, 3, 4],
4: [3],
},
vertex_coloring = [
set([3]),
set([0, 1, 2, 4]),
],
)
>>> autgrp(g)
([[1, 0, 2, 3, 4]], 2.0, 0, [0, 0, 2, 3, 4], 4)
>>>
Testing two graphs for isomorphism:
In [8]: print(a)
Graph(number_of_vertices=13, directed=False,
adjacency_dict = {
0: [6, 7, 8, 9],
1: [6, 7, 8, 11],
2: [7, 8, 10, 12],
3: [7, 9, 11, 12],
4: [8, 10, 11, 12],
5: [9, 10, 11, 12],
6: [0, 1, 9, 10],
7: [0, 1, 2, 3],
8: [0, 1, 2, 4],
9: [0, 3, 5, 6],
10: [2, 4, 5, 6],
11: [1, 3, 4, 5],
12: [2, 3, 4, 5],
},
vertex_coloring = [
],
)
In [9]: b = deepcopy(a)
In [10]: delete_random_edge(b)
Out[10]: (9, 3)
In [11]: print(b)
Graph(number_of_vertices=13, directed=False,
adjacency_dict = {
0: [6, 7, 8, 9],
1: [6, 7, 8, 11],
2: [7, 8, 10, 12],
3: [7, 11, 12],
4: [8, 10, 11, 12],
5: [9, 10, 11, 12],
6: [0, 1, 9, 10],
7: [0, 1, 2, 3],
8: [0, 1, 2, 4],
9: [0, 5, 6],
10: [2, 4, 5, 6],
11: [1, 3, 4, 5],
12: [2, 3, 4, 5],
},
vertex_coloring = [
],
)
In [12]: isomorphic(a,b)
Out[12]: False