Skip to main content

nxnauty

Canonical labelling and automorphism groups of NetworkX graphs, via nauty. A C++/pybind11 extension that takes graphs directly -- no container class, no manual relabelling -- and answers the questions about one 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]}
data_certificate(graph, node_color=..., ...)             -> DataCertificate
data_hash(graph, node_color=..., ...)                    -> str
topology_hash(graph, node_match=..., ...)                -> str
color_hash(value)                                        -> bytes

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

pip install nxnauty

Prebuilt modules for CPython 3.8 - 3.14 on x86_64 Linux, one per interpreter: the install picks the one matching yours, so nothing is compiled and no toolchain is needed. They are built against an old glibc (symbols up to GLIBC_2.16), so they run on CentOS 7 and anything newer. networkx is the only dependency.

Usage

>>> import networkx as nx, nxnauty
>>> a = nx.cycle_graph(6)
>>> b = nx.relabel_nodes(a, {i: (i * 5) % 6 for i in a})      # the same ring, relabelled
>>> nxnauty.are_isomorphic(a, b)
True
>>> nxnauty.are_isomorphic(a, b, get_mapping=True)[0]        # with a mapping, if you want one
True
>>> nxnauty.certificate(a)[:12].hex()                        # equal bytes iff isomorphic
'000000000000006000000000'
>>> nxnauty.canon_label(a)                                   # label -> canonical position
{0: 0, 1: 1, 5: 2, 3: 3, 2: 4, 4: 5}
>>> group = nxnauty.automorphism_group(a)
>>> len(group['generators']), group['order'], group['orbits']
(2, (12.0, 0), {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0})
>>> sorted(nxnauty.canonical_graph(a).edges())               # the canonical form, as a graph
[(0, 1), (0, 2), (1, 4), (2, 5), (3, 4), (3, 5)]
>>> [sorted(bucket) for bucket in nxnauty.classify([a, b, nx.path_graph(6)]).values()]
[[0, 1], [2]]

group['order'] is |Aut(G)| as mantissa * 10 ** exponent, so a group that is too large to hold as an int is still exact.

Colourings

A colouring compares attribute dictionaries instead of plain graph structure. node_match / edge_match are predicates; node_color / edge_color are keys -- one attribute dict in, an immutable value out, whose digest is the colour. The three entry points where the colour values reach the answer take a key: data_certificate, data_hash and are_isomorphic. The rest refuse them, because a canonical form, a group and a bucket are invariants of the coloured structure, and there the values are discarded before nauty runs.

>>> for graph in (a, b):                                     # which element a node is
...     for node in graph:
...         graph.nodes[node]['symbol'] = 'C' if node % 3 else 'O'
>>> key = lambda attrs: attrs['symbol']
>>> nxnauty.data_hash(a, node_color=key)[:16]                # the value-sensitive graph id
'ed472cef143513b2'
>>> same = lambda one, other: one['symbol'] == other['symbol']
>>> nxnauty.topology_hash(a, node_match=same)[:16]           # structure only, blind to the values
'574c2a89d0cd991a'
>>> nxnauty.are_isomorphic(a, b, node_color=key)             # the same key colours both graphs
True

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 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.

Type information

Stubs for the extension module (nxnauty/core.pyi, marked with py.typed) ship with the distribution, so Pyright and Pylance give completion, signatures and hover text -- 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.

Documentation and source

License

GPL v3, without warranty. nauty is covered by its own licensing terms.

Metadata

Release files for nxnauty 1.0.1

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.1
File Size Uploaded Provenance Actions
nxnauty-1.0.1.tar.gz 1.8 MB Without provenance Details for nxnauty-1.0.1.tar.gz

Release files / nxnauty-1.0.1.tar.gz

Download URL nxnauty-1.0.1.tar.gz
Size 1.8 MB
Tags Source
SHA-256 checksum
How to use checksums
ab03f7e0a53dc85bb685b37e9581dc6f861b565136d949ee0afc5680d4fd5670
BLAKE2b-256 checksum
How to use checksums
97142ca76e0590aa85bdc5d3cbcd0dbdfa222960b44333a2dce1538fd7f4a1a8
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.1

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.1 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