Source code for permaviss.simplicial_complexes.flag_complex

###############################################################################
# flag complexes for graphs:
# This is used e.g. for computing the nerve of a cover.

import numpy as np

###############################################################################


[docs]def _lower_neighbours(G, u): """Given a graph `G` and a vertex `u` in `G`, we return a list with the vertices in `G` that are lower than `u` and are connected to `u` by an edge in `G`. Parameters ---------- G : :obj:`Numpy Array(no. of edges, 2)` Matrix storing the edges of the graph. u : int Vertex of the graph. Returns ------- lower_neighbours : :obj:`list` List of lower neighbours of `u` in `G`. """ lower_neighbours = [] for e in G: if max(e) == u: lower_neighbours.append(min(e)) return np.unique(lower_neighbours)
############################################################################### # Main function
[docs]def flag_complex(G, no_vertices, max_dim): """Compute the flag complex of a graph `G` up to a maximum dimension `max_dim`. Parameters ---------- G : :obj:`Numpy Array(no. of edges, 2)` Matrix storing the edges of the graph. no_vertices : int Number of vertices in graph `G` max_dim : int Maximum dimension Returns ------- fl_cpx : :obj:`list(Numpy Array)` Flag complex of `G`. The `0` entry stores the number of vertices. For a higher entry `i`, `fl_cpx[i]` stores a :obj:`Numpy Array` matrix with the `i` simplices from `fl_cpx`. """ if max_dim < 0: print("Cannot compute a complex of dimension: {}".format(max_dim)) raise ValueError fl_cpx = [] for i in range(max_dim + 1): fl_cpx.append([]) fl_cpx[0] = no_vertices if max_dim == 0: return fl_cpx fl_cpx[1] = np.copy(G) # Build flag complex inductively for d in range(1, max_dim): for simplex in fl_cpx[d]: N = _lower_neighbours(fl_cpx[1], simplex[0]) for v in simplex[1:]: N = np.intersect1d(N, _lower_neighbours(fl_cpx[1], v)) # find simplices containing simplex and add them if np.size(N) > 0: simplices = np.ones((np.size(N), 1 + np.size(simplex))) simplices = np.multiply(np.append([1], simplex), simplices) simplices[:, 0] = N if isinstance(fl_cpx[d+1], list): fl_cpx[d + 1] = simplices else: fl_cpx[d+1] = np.append(fl_cpx[d + 1], simplices, 0) return fl_cpx