Skip to main content

nxnauty

Canonical labelling and automorphism groups of NetworkX graphs, via nauty. A C++/pybind11 extension that takes NetworkX graphs directly — no container class, no manual relabelling — and answers the questions about a single graph or a pair of them.

are_isomorphic(source, target, get_mapping=False, ...)   -> bool | (bool, mapping|None)
certificate(graph, ...)                                  -> bytes
canon_label(graph, ...)                                  -> {label: canonical position}
canonical_graph(graph, ...)                              -> nx.Graph
automorphism_group(graph, ...)                           -> {generators, order, orbits}
get_automorphisms(graph, ..., limit=1000)                -> [ {label: image}, ... ]
classify(graphs, ...)                                    -> {certificate: [indices]}

Every function accepts the same two predicates, in vf3py's order: node_match(source_attrs, target_attrs) and edge_match(source_attrs, target_attrs); None accepts everything.

Installing

python3 -m pip install .        # from this directory, or from an unpacked sdist

The distribution carries a prebuilt module for each interpreter it was assembled for, and the install picks the one matching the running interpreter, so no compiler is needed. A wheel built here is tagged for that interpreter and platform: do not publish it under another tag.

pyproject.toml is the package definition. The few lines of setup.py next to it exist for the three fields a file cannot know — which prebuilt module matches the interpreter doing the installing, the Requires-Python pin that goes with it, and the wheel tag — and tests/check_packaging.py builds a wheel to prove all three hold.

Type information

The distribution carries type stubs (nxnauty/core.pyi, marked with py.typed), so Pyright and pylance give completion, signatures and hover text for the extension module — including the get_mapping overload of are_isomorphic, the DiGraph-in/DiGraph-out overload of canonical_graph, and the keys of the dict automorphism_group returns. tests/check_typing.py holds the stubs to the module: it fails if a parameter name, order, default or docstring drifts from what the extension reports, and it runs Pyright over a probe of correct usage (must be clean) and one of deliberate mistakes (must be caught). The release driver re-runs pybind11-stubgen against the staged package for the same reason, so a docstring changed in C++ and not in the stub stops the release.

What to know before using it

  • certificate is the cheapest isomorphism test there is (equal bytes iff isomorphic), but two certificates are only comparable under the same predicate semantics. With a predicate the certificate is the canonical form of the encoded graph and its colour ids are numbered from the attribute values present, so a corpus with different value sets is bucketed more finely than "isomorphic under the predicate" — are_isomorphic is the function that answers that question.
  • Predicates that are not equivalence relations have no meaning on a single graph and are refused by the single-graph functions (ApplicabilityScopeError); are_isomorphic groups the two graphs jointly and accepts them.
  • Isomorphism is bijective and induced: different vertex counts are False, not an error, and subgraph/monomorphism search is not part of this library.
  • nx.MultiGraph, graphs with zero vertices, and self-loops are refused rather than silently reinterpreted.
  • Which isomorphism get_mapping=True returns is unspecified — it is the one the canonical labellings induce. Check validity, never a particular mapping.

Building from source

python3 build.py                # conan (pybind11, boost) + cmake, then a smoke test
python3 tests/check_stage*.py   # the gates, plus tests/check_typing.py for the stubs
python3 release_assemble/release_assemble.py --full --package   # every env, then the sdist

build.py builds for the interpreter that runs it. The release driver does that once per available interpreter, stages each module into release_assemble/nxnauty_release/nxnauty/, runs the gates against the staged package, and can then produce dist/nxnauty-<version>.tar.gz.

Documentation

The design and its reasoning — what nauty can and cannot answer, how predicates become colours, what is preserved from pynauty, what is deliberately different — is in REWRITE.md next to this file in the source tree, section by section, with the gates that hold each claim.

Metadata

Release files for nxnauty 1.0.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for nxnauty 1.0.0
File Size Uploaded Provenance Actions
nxnauty-1.0.0.tar.gz 1.8 MB Without provenance Details for nxnauty-1.0.0.tar.gz

Release files / nxnauty-1.0.0.tar.gz

Download URL nxnauty-1.0.0.tar.gz
Size 1.8 MB
Tags Source
SHA-256 checksum
How to use checksums
bcc2ebbfda12c5d7b71f2ec1083ef9e7c0b7896bf2ec6c51f130670f103e72b8
BLAKE2b-256 checksum
How to use checksums
6d685c6c02b8515be2ade67cc4dbfb92440b3e7024115494ce0fbfacb1e7f497
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.15

Security for nxnauty 1.0.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

1.0.0 This release

1 release file No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page