gramag — Python Docs

Theory

We use the notation introduced in Chapter 2 of Hepworth and Willerton to denote the magnitude chain groups \(\mathrm{MC}_{k, l}\) and magnitude homology groups \(\mathrm{MH}_{k, l}\). We note that for each \(l\), the magnitude chain complex splits as a direct sum of chain complexes

\[\mathrm{MC}_{\ast, l} = \bigoplus_{(s, t) \in V\times V} \mathrm{MC}_{\ast,l}^{(s, t)}\]

where \(\mathrm{MC}_{k, l}^{(s, t)}\) is the subgroup of \(\mathrm{MC}_{k, l}\) freely generated by tuples \((x_0, \dots, x_k)\) satisfying

\(x_0 \neq x_1 \neq \dots \neq x_k\),
\(\ell(x_0, \dots, x_k) = l\),
\(x_0=s\) and \(x_k=t\).

It is easy to check that the boundary operators respects this decomposition, mapping \(\partial: \mathrm{MC}_{k, l}^{(s, t)} \to \mathrm{MC}_{k-1, l}^{(s, t)}\) and hence the chain complex splits as described above. Moreover, given an arbitrary subset \(\mathcal{P}\subseteq V\times V\), we introduce the notation

\[\mathrm{MC}_{\ast, l}^{\mathcal{P}} = \bigoplus_{(s, t) \in \mathcal{P}} \mathrm{MC}_{\ast,l}^{(s, t)}.\]

Since the chain complex splits, the magnitude homology also splits and hence we introduce the notation

\[\mathrm{MH}_{k, l}^{(s, t)} := H_k( \mathrm{MC}_{\ast, l}^{(s, t)} )\]

and

\[\mathrm{MH}_{k, l}^{\mathcal{P}} := H_k( \mathrm{MC}_{\ast, l}^{\mathcal{P}} ) = \bigoplus_{(s, t)\in\mathcal{P}} \mathrm{MH}_{k, l}^{(s, t)}\]

where \(H_k\) is the homology functor in degree k.

Python API

This Python package provides bindings to the Rust library gramag, which computes magnitude homology of finite, directed graphs. Usage of the package usually follows the following pattern:

Construct a MagGraph from your graph.
Search for paths to populate the magnitude chain groups, by calling populate_paths with an appropriate stopping condition.
Report the number of paths found via rank_generators.
Compute the ranks of all of the possible homology groups via rank_homology.
Investigate a particular homology group, by calling l_homology with representatives=True.

A simple example script illustrating this workflow is show below.

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])

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]]

class gramag.DirectSum

DirectSum objects represent a direct sum of homology groups \(\oplus_{((s, t), l)\in I}\mathrm{MH}_{k, l}^{(s, t)}\) for some indexing set \(I\subseteq (V\times V) \times \mathbb{N}\). The range of the homological degree \(k\) varies depending on the last call to populate_paths before each summand was created. If the range varies amongst the summands, we restrict to the smallest common sub-range.

Parameters:: edges (list[StlHomology], optional) – The list of summands to enter into the direct sum. Defaults to the empty sum.

add(summand)

Adds another summand to the direct sum, mutating the original sum.

Parameters:: summand (StlHomology) – The summand to be added to the sum
Returns:: Whether a summand with the same \(((s, t), l)\)-index already existed in the sum and was just replaced by this summand.
Return type:: bool

ranks

Retrieves the ranks of the homology groups.

Returns:: A dictionary where output[k] stores the rank \(\operatorname{rank}(\oplus_{((s, t), l)\in I}\mathrm{MH}_{k, l}^{(s, t)})\).
Return type:: dict[usize, usize]

representatives

Retrieves a (non-unique) set of representatives for the homology groups. Each representative is a \(\mathbb{Z}_2\)-linear combination of paths (i.e. a set of paths) and is thus represented by a list[list[usize]] where each inner list[usize] represents a path.

Returns:: A dictionary where output[k] stores a list of representatives for \(\oplus_{((s, t), l)\in I}\mathrm{MH}_{k, l}^{\mathcal{P}}\) with len(output[k]) \(=\operatorname{rank}(\oplus_{((s, t), l)\in I}\mathrm{MH}_{k, l}^{\mathcal{P}})\).
Return type:: dict[usize, list[list[list[usize]]]]
Raises:: TypeError – If this homology was computed with representatives = False then an error is raised.

class gramag.MagGraph

The main container for a (directed, unweighted) graph from which magnitude homology can be computed. Upon construction, all pairwise distances will be computed via Dijkstra’s algorithm (in parallel starting from each node) Before computing homology, you should first call the member function populate_paths.

The graph container is constructed by provided a list of directed edges. A few rules:

Nodes are labelled by integers
Edges are provided as a list of tuples of vertices
Isolated vertices are not supported at the moment

Parameters:: edges (list[tuple[int, int]]) – The list of directed edges in the graph

static from_distance_matrix(distance_matrix)

Call this to compute the magnitude homology of a finite quasimetric space. Simply pass in your distance matrix as the first parameter, using -1 to denote an infinite distance. You will get back a MagGraph (this is a bit of a hack) from which you can compute magnitude homology.

Parameters:: distance_matrix (list[list[int]]) – The distance matrix of your finite quasimetric space.
Returns:: A MagGraph object representing the apce.
Return type:: MagGraph

l_homology(l, representatives=Ellipsis, node_pairs=Ellipsis)

Computes magnitude homology \(\mathrm{MH}_{k, l}^{\mathcal{P}}\) for a fixed length \(l\) and all possible homological degrees \(k\), summed over a list of node pairs \(\mathcal{P}\). The homology for each node pair \((s, t)\in\mathcal{P}\) is computed in parallel.

Parameters:

l (int) – The fixed length \(l\), as described above.
representatives (bool, optional) – Whether to compute representatives of each homology group. Defaults to False.
node_pairs (list[tuple[int, int]], optional) – The list of node pairs \(\mathcal{P}\) over which to compute and sum magnitude homology. Defaults to all possible node pairs.

Returns:

The requested homology groups.

Return type:

DirectSum

Raises:

TypeError – If no paths have been found with length \(\geq l\), an error is raised.

populate_paths(*, k_max=Ellipsis, l_max=Ellipsis)

You must call this method before attempting to compute any homology.

This method performs a parallelised breadth-first search to find all paths in the graph, subject to a stopping condition. You must provide exactly one of k_max or l_max; typically l_max is faster but allows you to compute fewer homology groups:

If you provide l_max then you will be able to compute \(\mathrm{MH}_{k, l}\) whenever \(l\leq\) l_max (and hence \(k \leq\) l_max).
If you provide k_max then you will be able to compute \(\mathrm{MH}_{k, l}\) whenever \(k <\) k_max (in which case \(l\) can be arbirarily large) or \(l \leq\) k_max (in which case \(k\leq\) k_max).

Parameters:

k_max (init, optional) – If provided, finds all \((k, l)\)-paths where \(k \leq\) k_max.
l_max (init, optional) – If provided, finds all \((k, l)\)-paths where \(l \leq\) l_max.

Raises:

TypeError – Raises an exception unless exactly one of k_max and l_max is provided.

rank_generators(node_pairs=Ellipsis)

Computes all possible magnitude chain group ranks \(\operatorname{rank}(\mathrm{MC}_{k, l}^\mathcal{P})\), summed over a list of node pairs \(\mathcal{P}\).

Parameters:: node_pairs (list[tuple[int, int]], optional) – The list of node pairs \(\mathcal{P}\) over which to compute and sum the ranks. Defaults to all possible node pairs.
Returns:: The ranks of the known chain groups groups, where \(\operatorname{rank}(\mathrm{MC}_{k,l}^\mathcal{P})\) is stored in output[l][k].
Return type:: list[list[int]]

rank_homology(node_pairs=Ellipsis)

Computes all possible magnitude homology ranks \(\operatorname{rank}(\mathrm{MH}_{k, l}^\mathcal{P})\), summed over a list of node pairs \(\mathcal{P}\). The homology for each node pair \((s, t)\in\mathcal{P}\) is computed in parallel.

Parameters:: node_pairs (list[tuple[int, int]], optional) – The list of node pairs \(\mathcal{P}\) over which to compute and sum magnitude homology. Defaults to all possible node pairs.
Returns:: The ranks of the known homology groups, where \(\operatorname{rank}(\mathrm{MH}_{k,l}^\mathcal{P})\) is stored in output[l][k].
Return type:: list[List[int]]

stl_homology(node_pair, l, representatives=Ellipsis)

Computes magnitude homology \(\mathrm{MH}_{k, l}^{(s, t)}\) for a fixed node pair \((s, t)\), a fixed length \(l\) and all possible homological degrees \(k\).

Parameters:

node_pair (tuple[int, int]) – The node pair \((s, t)\), as described above.
l (int) – The fixed length \(l\), as described above.
representatives (bool, optional) – Whether to compute representatives of each homology group. Defaults to False.

Returns:

The requested homology groups.

Return type:

StlHomology

Raises:

TypeError – If no paths have been found with length \(\geq l\), an error is raised.

class gramag.StlHomology

StlHomology objects represent the homology groups \(\mathrm{MH}_{k, l}^{(s, t)}\) for some fixed node pair \((s, t)\in V \times V\) and a fixed length \(l\). The range of the homological degree \(k\) varies depending on the last call to populate_paths.

ranks

Retrieves the ranks of the homology groups.

Returns:: A dictionary where output[k] stores the rank \(\operatorname{rank}(\mathrm{MH}_{k, l}^{(s, t)})\).
Return type:: dict[usize, usize]

representatives

Retrieves a (non-unique) set of representatives for the homology groups. Each representative is a \(\mathbb{Z}_2\)-linear combination of paths (i.e. a set of paths) and is thus represented by a list[list[usize]] where each inner list[usize] represents a path.

Returns:: A dictionary where output[k] stores a list of representatives for \(\mathrm{MH}_{k, l}^{(s, t)}\) with len(output[k]) \(=\operatorname{rank}(\mathrm{MH}_{k, l}^{(s, t)})\).
Return type:: dict[usize, list[list[list[usize]]]]
Raises:: TypeError – If this homology was computed with representatives = False then an error is raised.

gramag.format_rank_table(table, above_diagonal=Ellipsis, unknown=Ellipsis, zero=Ellipsis)

Formats a table of numbers, such as those outputted by rank_homology or rank_generators.

Parameters:

table (list[list[Int]]) – The table to format.
above_diagonal (str, optional) – The string to display for the ranks of all groups above the diagonal (which are necessarily 0). Defaults to the empty string.
unknown (str, optional) – The string to disply when the rank of a group is unknown. Defaults to "?".
zero (str, optional) – The string to disply when the rank of a group is zero. Defaults to ".".

Returns:

The formatted table.

Return type:

str

gramag.version()

Returns:: The current version of gramag.
Return type:: str

Doctests

>>> from gramag import MagGraph, format_rank_table
>>> mg = MagGraph([(0, 1), (0, 2), (1, 4), (2, 3), (3, 4)])
>>> mg.populate_paths(l_max=3)
>>> print(format_rank_table(mg.rank_homology()))
╭─────┬────────────╮
│ k=  │ 0  1  2  3 │
├─────┼────────────┤
│ l=0 │ 5          │
│ l=1 │ .  5       │
│ l=2 │ .  .  .    │
│ l=3 │ .  .  1  . │
╰─────┴────────────╯