NOTICE
======

This package (`acdc-search`, importable as `acdc`) is a Python translation of the
MATLAB reference implementation of AC(+)DC search, published as supplementary
material to:

    D. D. Lee, A. Matsliah and L. K. Saul,
    "AC(+)DC search: behind the winning solution to the FlyWire graph-matching
    challenge",
    Transactions on Machine Learning Research (01/2026).
    https://openreview.net/forum?id=8MjCOMyaDf

The original MATLAB implementation is:

    Copyright (c) 2025 Daniel Lee and Lawrence Saul

and is distributed under the MIT licence. That licence, including its copyright
and permission notices, is reproduced in full in the LICENSE file of this
package, as the licence requires.

Because the original is MIT-licensed, this translation is offered under the MIT
licence as well (see LICENSE). If you use this package, please cite the paper
above: the algorithm is the authors' work, and this is a translation of it.

This package does not redistribute any of the original MATLAB source files.


Summary of changes
------------------

The MIT licence does not require modifications to be documented. The following
summary is provided for clarity about how faithful the translation is:

  * The algorithm was translated from MATLAB to Python, using NumPy and SciPy
    for array and sparse-matrix operations, and reorganised from a flat set of
    scripts into an installable package with a documented public API:

        compute_gradient.m + score expression        ->  acdc/objective.py
        permutation_match.m                          ->  acdc/matching.py
        do_frank_wolfe.m                             ->  acdc/frank_wolfe.py
        evaluate_swaps.m, make_swaps.m,
          greedy_search.m                            ->  acdc/swaps.py
        main_acdc.m, main_continuous.m,
          main_discrete.m                            ->  acdc/core.py

  * Node indices are 0-based throughout, following Python convention, rather
    than 1-based as in MATLAB.

  * The linear-assignment subproblem, solved in the original by the undocumented
    internal routine `matlab.internal.graph.perfectMatching`, is solved here by
    SciPy: `scipy.optimize.linear_sum_assignment` (`solver='dense'`, the default
    and the faithful analogue) or
    `scipy.sparse.csgraph.min_weight_full_bipartite_matching`
    (`solver='sparse'`, faster at scale but restricted to stored edges).

  * The warm-start preconditioner that the original applies before its
    assignment solver is omitted. Its transform adds only per-row and
    per-column constants and so does not change the optimal matching; it existed
    to speed up MATLAB's sparse solver.

  * The FlyWire-specific I/O routines (`read_connectome.m`, `read_solution.m`,
    `save_solution.m`) and the figure-generation scripts were not translated;
    this package covers the core algorithm only.

  * A test suite (`tests/`) and a scaling benchmark (`benchmark.py`) were added.
    These are original to this package and have no counterpart in the MATLAB
    implementation.

  * Three inner loops -- the gradient accumulation, the greedy pairwise-swap
    loop, and the support-restricted part of the swap-gain quadratic term --
    are compiled with numba (`acdc/_kernels.py`) rather than expressed as NumPy
    array operations. They visit elements in the same order as the original and
    are bit-identical to it.

    The greedy swap loop additionally judges each candidate swap by the exact
    change it makes to the score, computed over the rows and columns it can
    affect, where `make_swaps.m` recomputes the entire score after every trial.
    The accept/reject decision is the same; only the cost of reaching it
    differs. The Frank-Wolfe line search likewise evaluates the vertex gradient
    at the O(n) entries it reads instead of over all n^2.

Further notes on fidelity to the original are given in the README.


Connectome data
---------------

This package ships no data. The connectome CSV files distributed alongside the
original MATLAB code were obtained from the VNC Matching Challenge website,

    https://codex.flywire.ai/app/vnc_matching_challenge

and the supplementary material asks that the contest organisers be acknowledged
for any further use of that data. This applies to anyone using those files with
this package; it is not a condition of the software licence.
