Metadata-Version: 2.4
Name: GASM-or
Version: 0.2.0
Summary: Graph Attributes and Structure Matching (GASM): graph matching on CPU and GPU.
Author-email: Raphaël Candelier <raphael.candelier@sorbonne-universite.fr>
License-Expression: GPL-3.0-or-later
Project-URL: Homepage, https://github.com/CandelierLab/GASM-or
Project-URL: Documentation, https://candelierlab.github.io/GASM-or/
Project-URL: Repository, https://github.com/CandelierLab/GASM-or.git
Project-URL: Issues, https://github.com/CandelierLab/GASM-or/issues
Keywords: graph matching,graph similarity,quadratic assignment,linear assignment,networkx,GPU,OpenCL
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.23
Requires-Dist: scipy>=1.9
Requires-Dist: networkx>=2.8
Provides-Extra: gpu
Requires-Dist: pyopencl>=2022.1; extra == "gpu"
Provides-Extra: benchmark
Requires-Dist: matplotlib>=3.6; extra == "benchmark"
Provides-Extra: doc
Requires-Dist: sphinx>=7.0; extra == "doc"
Requires-Dist: furo>=2023.0; extra == "doc"
Provides-Extra: test
Requires-Dist: pytest>=7.0; extra == "test"
Provides-Extra: dev
Requires-Dist: pyopencl>=2022.1; extra == "dev"
Requires-Dist: matplotlib>=3.6; extra == "dev"
Requires-Dist: sphinx>=7.0; extra == "dev"
Requires-Dist: furo>=2023.0; extra == "dev"
Requires-Dist: pytest>=7.0; extra == "dev"
Requires-Dist: build>=1.0; extra == "dev"
Requires-Dist: twine>=4.0; extra == "dev"
Dynamic: license-file

# GASM Official Repository

A python repository implementing an optimized version of the *Graph Attribute and Structure Matching* ([GASM](https://jgaa.info/index.php/jgaa/article/view/2979)) algorithm on both CPU and GPU.

Check out the [documentation](https://candelierlab.github.io/GASM-or/) !

## Installation

```
pip install --upgrade pip
pip install GASM-or
```

Optional extras:

```
pip install "GASM-or[gpu]"        # OpenCL GPU back-end (pyopencl)
pip install "GASM-or[benchmark]"  # matplotlib, for the benchmark scripts
pip install "GASM-or[doc]"        # sphinx + furo, to build the documentation
```

## Quick start

```python
import gasm
import networkx as nx

G1 = nx.gnp_random_graph(30, 0.1, seed=0)
G2 = nx.relabel_nodes(G1, {i: (i + 5) % 30 for i in G1.nodes()})

M = gasm.match(G1, G2)          # GPU by default, CPU fallback
print(M.matchups)               # list of (a, b) matched pairs
print(M.score)                  # global matching score
```

Force the CPU back-end, add attributes, or evaluate the result:

```python
M = gasm.match(G1, G2, platform="CPU")

attrs = [
    gasm.Attribute("weight", on="edge", kind="measurable", rho=0.1),
    gasm.Attribute("label", on="vertex", kind="categorical"),
]
M = gasm.match(G1, G2, attributes=attrs)

ground_truth = {i: (i + 5) % 30 for i in G1.nodes()}
M.accuracy(ground_truth)        # fraction of correct pairs
M.structural_quality(G1, G2)    # structural quality qS
```

## Features

- Faithful implementation of GASM for undirected and directed graphs.
- GPU (OpenCL) and CPU back-ends, with automatic CPU fallback.
- Vertex and edge attributes, categorical or measurable, with per-attribute uncertainty.
- Structure-only or attributes-only matching.
- Automatic complement procedure for dense graphs.
- Refined adaptive convergence criterion (with the article's fixed-iteration behaviour available on demand).
- Pluggable linear assignment solvers (Jonker-Volgenant, auction).

## Dependencies

Requires `numpy`, `scipy` and `networkx`. The GPU back-end additionally requires `pyopencl` and an OpenCL runtime.

## Benchmarks

The `benchmark/` scripts import the local package and offer quick and full modes:

```
python benchmark/accuracy_quality.py --mode quick
python benchmark/speed.py --mode full --platforms CPU GPU
```

## License

This project is licensed under the GNU General Public License v3.0 (GPL-3.0).
See the [LICENSE](LICENSE) file for the full text.

## Authors and acknowledgment

Crafted with ❤️ by Raphaël Candelier.
