gramag 0.4.0

Graph Magnitude Homology in Rust, with Python bindings

gramag

Graph Magnitude Homology in Rust, with Python bindings

Overview

gramag is a library for computing the magnitude homology of finite (directed) graphs in Python and Rust. The library is capable of computing homology ranks and representatives, over ℤ₂. For background on graph magnitude homology, see the original paper by Hepworth and Willerton [1].

Computational detail

In an attempt to compute magnitude homology for large graphs, we attempt to parallelise computation wherever possible; this may result in increased memory usage. In particular, the initial basis for each of the magnitude chain groups is computed via a parallelised breadth-first search. To limit the number of threads used, simply set the environment variable RAYON_NUM_THREADS appropriately.

Throughout the codebase we make extensive use of the fact that the magnitude chain complex splits over node pairs, i.e. $$MC_{\bullet, \bullet} = \bigoplus_{(s, t)\in V\times V} MC_{\bullet, \bullet}^{(s, t)}$$ where $MC_{\bullet, \bullet}^{(s, t)}$ is the sub-complex of $MC_{\bullet, \bullet}$ generated by those paths starting at $s$ and ending at $t$. All of the Python APIs admit a node_pairs argument to restrict the set of node pairs $(s, t)$ over which this direct sum is computed. Unfortunately, the initial path search does not admit such an argument at the moment.

Python

The easiest way to use gramag is to install the Python bindings. Pre-compiled packages are available for most systems on PyPi, failing which the source distribution can be installed in the presence of a suitable cargo toolchain. On most modern systems, gramag can be installed through pip via:

pip install gramag

Usage

Full documentation is available on Read The Docs or can be built from source by calling

just setup_venv
just py_docs_open

A simple example script is provided in simple.py.

from gramag import MagGraph, format_rank_table

# Create your graph
# A few rules:
# 1. Nodes are labelled by integers
# 2. Edges are provided as a list of tuples of vertices
# 3. Isolated vertices are not supported at the moment
mg = MagGraph([(0, 1), (0, 2), (0, 3), (1, 6), (2, 6), (3, 4), (4, 5), (5, 6)])

# Compute generators of all MC^{(s, t)}_{k, l} for l<=6
mg.populate_paths(l_max=6)

# Reports the ranks of MC^{(s, t)}_{k, l}, summed over (s, t)
rk_gens = mg.rank_generators()

# For each l, in parallel across each (s, t), computes MH^{(s, t)}_{k, l}
# Adds up the rank for each k, l
rk_hom = mg.rank_homology()

# Pretty print
print("Rank of MC:")
print(format_rank_table(rk_gens))

print("Rank of MH:")
print(format_rank_table(rk_hom))

# Compute homology summed over a given list of (s, t)
print("Rank of MH^{(0, 6)}:")
print(format_rank_table(mg.rank_homology(node_pairs=[(0, 6)])))

# Compute homology with representatives, at a given l
homology = mg.l_homology(4, representatives=True)
print("Representatives for MH_{2, 4}:")
print(homology.representatives[2])

which outputs

Rank of MC:
╭─────┬─────────────────────╮
│ k=  │ 0  1  2  3  4  5  6 │
├─────┼─────────────────────┤
│ l=0 │ 7                   │
│ l=1 │ .  8                │
│ l=2 │ .  4  5             │
│ l=3 │ .  2  4  2          │
│ l=4 │ .  .  3  3  1       │
│ l=5 │ .  .  .  .  .  .    │
│ l=6 │ .  .  .  .  .  .  . │
╰─────┴─────────────────────╯
Rank of MH:
╭─────┬─────────────────────╮
│ k=  │ 0  1  2  3  4  5  6 │
├─────┼─────────────────────┤
│ l=0 │ 7                   │
│ l=1 │ .  8                │
│ l=2 │ .  .  1             │
│ l=3 │ .  .  .  .          │
│ l=4 │ .  .  1  .  .       │
│ l=5 │ .  .  .  .  .  .    │
│ l=6 │ .  .  .  .  .  .  . │
╰─────┴─────────────────────╯
Rank of MH^{(0, 6)}:
╭─────┬─────────────────────╮
│ k=  │ 0  1  2  3  4  5  6 │
├─────┼─────────────────────┤
│ l=0 │ .                   │
│ l=1 │ .  .                │
│ l=2 │ .  .  1             │
│ l=3 │ .  .  .  .          │
│ l=4 │ .  .  1  .  .       │
│ l=5 │ .  .  .  .  .  .    │
│ l=6 │ .  .  .  .  .  .  . │
╰─────┴─────────────────────╯
Representatives for MH_{2, 4}:
[[[0, 5, 6]]

For more detailed usage, please refer to advanced.py.

Rust

The Rust library has not yet been finalised.

References

[1] Hepworth, Richard, and Simon Willerton. "Categorifying the magnitude of a graph." arXiv preprint arXiv:1505.04125 (2015).