Skip to main content

Isomorphism testing and automorphisms of graphs.

Project description

Build and test

Pynauty

Pynauty can be used to compare graphs for isomorphism and to determine their automorphism group in a Python programming environment. Pynauty is a Python/C extension module using library components from the Nauty package by Brendan McKay.

Usage

Here is an example of pynauty's usage in an interactive session.

>>> from pynauty import *
>>> 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 = [
 ],
)
>>> autgrp(g)
([[3, 4, 2, 0, 1]], 2.0, 0, [0, 1, 2, 0, 1], 3)
>>> 
>>> g.connect_vertex(1, [3])
>>> autgrp(g)
([[0, 1, 3, 2, 4], [1, 0, 2, 3, 4]], 4.0, 0, [0, 0, 2, 2, 4], 3)
>>>
>>> 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)
>>>

Installation

Installing from PyPi

You can install pynauty using pip, just type

pip install --upgrade pynauty

Many binary wheels are provided for recent Linux and macOS systems. When your system is not compatible with any of the provided binary wheels pip attempts to build the wheel of the extension module in your local system. This happens automatically and the process is transparent to the user. For local builds pip expects that the required tools are available.

You can force the local (re)compilation during install by issuing

pip install --no-binary pynauty pynauty

Regardless of which way the installation was accomplished, afterwards you can test the result by running the provided tests.

python <path-to-installed-package>/pynauty/tests/test_minimal.py

If you have pytest installed then you can run the full test suit by issuing

pip install pytest
python -m pytest <path-to-installed-package>/pynauty

That takes a few seconds but then you can be sure in having a binary compatible module.

Documentation

The pynauty package comes with an HTML documentation with examples. You can read it with your favorite browser:

<your-browser>  <path-to-installed-package>/pynauty/docs/html/index.html

Building manually from sources

Requirements

Apart from Python the requirements are the same as for building Nauty.

  • Python 3.7 - 3.9
  • An ANSI C compiler
  • GNU make

Download sources

You can download the source distribution form PyPi by issuing:

pip download --no-binary pynauty pynauty

Please note, the source distribution also contains Nauty27r1's source.

Build, test, install

If you really are interested in the low level details then unpack the downloaded source distribution, change into pynauty's directory and type make. The Makefile is self-documenting in the sense that invoking make without arguments will list all available targets with short explanations.

Contributing

Questions, bug reports, pull requests, especially the ones extending the Python module's functionality, are welcome. Please, open an issue first to discuss what you would like to change.

Pull requests must be made on a dedicated topic-branch of your choice and not against upstream/main. Before submitting a pull request, make sure that your fork is up to date with upstream. Also update tests, documentation, examples as appropriate with the changes in your PR.

Contributors

  • @goens helped creating pytest components.

  • Sam Morley-Short (@sammorley-short) added canon_label() function.

License

Pynauty is distributed under the terms of GPL v3 WITHOUT ANY WARRANTY. For the exact details on licensing see the file COPYING.

Please note, Nauty is covered by its own licensing terms. For the exact details see the file src/nauty27r1/COPYRIGHT.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for pynauty, version 1.0.2
Filename, size File type Python version Upload date Hashes
Filename, size pynauty-1.0.2-cp37-cp37m-macosx_10_14_x86_64.whl (298.9 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size pynauty-1.0.2-cp37-cp37m-manylinux_2_31_x86_64.whl (321.6 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size pynauty-1.0.2-cp38-cp38-macosx_10_14_x86_64.whl (298.9 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size pynauty-1.0.2-cp38-cp38-manylinux_2_31_x86_64.whl (321.2 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size pynauty-1.0.2-cp39-cp39-macosx_10_14_x86_64.whl (298.9 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size pynauty-1.0.2-cp39-cp39-manylinux_2_31_x86_64.whl (320.4 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size pynauty-1.0.2-cp39-cp39-manylinux_2_33_x86_64.whl (315.7 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size pynauty-1.0.2.tar.gz (1.9 MB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page