1.1   Licence

Copyright (c) 2004 Peter Dobcsanyi

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

Please note, Nauty's source code is not distributed with this package you need to download it separately. It is covered by its own licencing terms. For details, see Nauty's web-site.

2.1   Dependencies

To build pynauty the following components are needed:

• Python 2.3 or newer. Python is available from Python.org both in source and in binary forms. Binaries can be found for many, including Windows and Mac, platforms. Alternatively, all general Linux distributions provide Python.
• The Nauty package.
• A good ANSI C compiler.

In general, pynauty should work on all platforms (Linux, Windows, Mac, etc.) where Python can run and Nauty's source can be complied. Compilation of Nauty may or may not work on Windows depending on available compilers and environment. For details, see Nauty's documentation.

2.2   Compiling Nauty

Download Nauty, untar the distribution file then change to the nautyNN/ directory. Run ./configure. After ./configure has run successfully, you need to compile only a few object files. Type the following make command:

make nautyB.o nautilB.o naugraphB.o

Should you encounter any difficulties with compiling Nauty, please, consult Nauty's documentation.

2.3   Installing pynauty

Download pynauty, untar the distribution file then change to the pynauty-x.y/ directory. You need to edit the setup.py file and set the parameter nauty_dir to the directory path which contains Nauty. The path specification can be either absolute or relative to pynauty-x.y/. After editing setup.py, run it:

python setup.py install

Apart from the standard commands, setup.py also accepts the following package specific commands:

clean

remove build/ dist/ MANIFEST

uninstall

remove all installed components from the system

distclean

clean + uninstall

2.4   Documentation

The documentation can be found in the doc/ subdirectory.

3.1   Vertex coloring

Let V be the set of vertices of a graph G. A partition of vertices is a collection of non-empty and pairwise disjoint subsets (parts) of V such that the union of these subsets is V. A vertex-coloring defines a partition of vertices, with vertices of the same color belonging to the same part. Similarly, a partition of vertices defines a vertex-coloring by giving the same distinct color to vertices in the same part. So vertex-coloring and partition of vertices are essentially the same.

In pynauty, a vertex-coloring 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 non-empty 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. If there is no builtin set datatype available then pynauty exports a set datatype which is based on the sets module.

The significance of vertex-coloring 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 vertex-colored graphs are isomorphic if there is a bijection between their vertex sets which preserves adjacency and color.

3.2   class GraphD

Class GraphD provides an ADT for simple (no multiple edges) vertex-colored (un)directed graphs based on an adjacency dictionary. The vertices must be represented by integers starting with 0.

A GraphD object has the following attributes and methods:

no_vertices

The number of vertices. Mandatory argument at object creation time.

directed

A Boolean value indicating whether the graph is directed or not. Optional argument, the default is False.

adjacency_dict

A dictionary containing the adjacency lists for the graph. A typical entry would look like v : [v0, v1, ...], which means that v has (optionally directed) edges to v0, v1, .... Optional argument, the default is {}.

vertex_coloring

This is to specify vertex-coloring. It is a list of subsets of the vertex set of the graph. Optional argument, the default is the empty list [], which means all vertices have the same color.

set_adjacency_dict(adj_dict)

Set the graph's adjacency_dict to the new adj_dict.

connect_vertex(v, neighbors)

Connect vertex v to the list of vertices given by neighbors. If any of the specified vertices is not between 0 and no_vertices-1 inclusive then ValueError exception will be raised. To add an isolated vertex to the graph specify an empty neighbors list.

An already existing adjacency list for v is simply replaced with the new list given by neighbors.

set_vertex_coloring(coloring)

Set the graph's vertex_coloring to the new coloring.

In the example below we build a simple graph g:

>>> from pynauty import *
>>> 
>>> g = GraphD(5)
>>> g.connect_vertex(0, [1, 2, 3])
>>> g.connect_vertex(2, [1, 3, 4])
>>> g.connect_vertex(4, [3])
>>> g.set_vertex_coloring([set([0,2]), set([4])])
>>> 
>>> print g
GraphD(no_vertices=5, directed=False,
 adjacency_dict = {
  0: [1, 2, 3],
  2: [1, 3, 4],
  4: [3],
 },
 vertex_coloring = [
  set([0, 2]),
  set([4]),
  set([1, 3]),
 ]
)
>>> 

3.3   class GraphM

Class GraphM provides an ADT based on a adjacency matrix to to represent simple (un)directed graphs. The matrix used is a Numarray object. UNDER DEVELOPMENT -- not in the current release.

3.4   Functions

graph_automorphism_group(g)

Return a list of generators for the automorphism group of the vertex-colored graph g. g must be an instance of either GraphD or GraphM. Each generator is represented as a permutation of the vertices.

is_isomorphic_graph(a, b)

Return True if a and b are isomorphic graphs, otherwise return False. a and b must be an instance of either GraphD or GraphM. When all vertices have the same color (practically no vertex-coloring) this function tests the usual graph isomorphism.

Here is how to get the automorphism group of a graph:

>>> print g
GraphD(no_vertices=5, directed=False,
 adjacency_dict = {
  0: [1, 2, 3],
  2: [1, 3, 4],
  4: [3],
 },
 vertex_coloring = [
 ]
)
>>> 
>>> graph_automorphism_group(g)
[[3, 4, 2, 0, 1]]

Adding a new edge changes the symmetries of the graph:

>>> g.connect_vertex(1, [3])
>>> print g
GraphD(no_vertices=5, directed=False,
 adjacency_dict = {
  0: [1, 2, 3],
  1: [3],
  2: [1, 3, 4],
  4: [3],
 },
 vertex_coloring = [
 ]
)
>>> 
>>> graph_automorphism_group(g)
[[0, 1, 3, 2, 4], [1, 0, 2, 3, 4]]

"Fixing" vertex 3:

>>> g.set_vertex_coloring([set([3])])
>>> print g
GraphD(no_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]),
 ]
)
>>> graph_automorphism_group(g)
[[1, 0, 2, 3, 4]]