Metadata-Version: 2.1
Name: nxnauty
Version: 1.0.1
Author: knv
Platform: Linux
Requires-Python: >=3.8
Summary: Canonical labelling and automorphism groups of NetworkX graphs, via nauty
Requires-Dist: networkx
Project-URL: Homepage, https://gitlab.com/knvvv/nxnauty
Project-URL: Documentation, https://knvvv.gitlab.io/nxnauty/
Project-URL: Issues, https://gitlab.com/knvvv/nxnauty/-/issues
Description-Content-Type: text/markdown

# nxnauty

Canonical labelling and automorphism groups of [NetworkX](https://networkx.org/) graphs, via
[nauty](https://pallini.di.uniroma1.it/).  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

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

```python
>>> 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

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

