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
certificateis 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_isomorphicis 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_isomorphicgroups 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=Truereturns 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
- Docs: https://knvvv.gitlab.io/nxnauty/
- Source, tests and the design document (
REWRITE.md): https://gitlab.com/knvvv/nxnauty
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)
| 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.