pyflagser.flagser_unweighted

pyflagser.flagser_unweighted(adjacency_matrix, min_dimension=0, max_dimension=inf, directed=True, coeff=2, approximation=None)

Compute homology of a directed/undirected flag complex.

From an adjacency_matrix construct all cells forming its associated flag complex and compute its homology.

Parameters
adjacency_matrix2d ndarray or scipy.sparse matrix of shape (n_vertices, n_vertices), required

Adjacency matrix of a directed/undirected unweighted graph. It is understood as a boolean matrix. Off-diagonal, 0 or False values denote abstent edges while non-0 or True values denote edges which are present. Diagonal values are ignored.

min_dimensionint, optional, default: 0

Minimum homology dimension to compute.

max_dimensionint or np.inf, optional, default: np.inf

Maximum homology dimension to compute.

directedbool, optional, default: True

If True, computes homology for the directed flad complex determined by adjacency_matrix. If False, computes homology for the undirected flag complex obtained by considering all edges as undirected, and it is therefore sufficient (but not necessary) to pass an upper-triangular matrix.

coeffint, optional, default: 2

Compute homology with coefficients in the prime field \(\mathbb{F}_p = \{ 0, \ldots, p - 1 \}\) where \(p\) equals coeff.

approximationint or None, optional, default: None

Skip all cells creating columns in the reduction matrix with more than this number of entries. Use this for hard problems; a good value is often 100,000. Increase for higher precision, decrease for faster computation. If None, no approximation is made and all cells are used. For more details, please refer to [1].

Returns
outdict of list

A dictionary with the following key-value pairs:

  • 'betti': list of int Betti numbers, per dimension greater than or equal than min_dimension and less than max_dimension.

  • 'cell_count': list of int Cell counts (number of simplices), per dimension greater than or equal to min_dimension and less than max_dimension.

  • 'euler': int Euler characteristic.

Notes

The input graphs cannot contain self-loops, i.e. edges that start and end in the same vertex, therefore diagonal elements of the input adjacency matrix will be ignored.

References

1

D. Luetgehetmann, “Documentation of the C++ flagser library”; GitHub: luetge/flagser.