Metadata-Version: 2.1
Name: nxnauty
Version: 1.0.0
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/vf3py
Description-Content-Type: text/markdown

# nxnauty

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

