Discrete Configuration Complex (Graph to Cell)

Given a graph $G$, the Discrete Configuration Complex $D_k(G)$ is the set of all $k$-tuples of edges and vertices in $G$ which form a legal configuration. A legal configuration is one in which none of the vertices or edges in the configuration are incident to one and other - for example, no two edges share a vertex, and no vertex in a configuration is also contained in an edge.

This is an example of a cube complex - a topological space constructed entirely from unions of hypercubes. It was originally constructed by Abrams [3] and used to represent robot motion planning problems, where the k tuple represents k different robots and the complex captures how the robots can move around without colliding into each other. See [1], [2], [3], and [4] for a more detailed explanation.

Unfortunately, since TopoNetX does not support cell complexes of dimensions > 2, this implementation will only construct the 2-skeleton of $D_k(G)$. However, this code already implements the necessary methods for generating higher-order cell complexes, and can be easily updated as soon as TopoNetX supports dimensions > 2.

[1] A. Abrams and R. Ghrist. Finding topology in a factory: Configuration spaces. Amer. Math. Monthly 109:140–150, 2002. [2] A. Abrams and R. Ghrist. State complexes for metamorphic robot systems. Int. J. Robotics Research 23(7–8):809–824, 2004. [3] A. D. Abrams. Configuration Spaces and Braid Groups of Graphs. Ph.D. thesis, Dept. Math., U.C. Berkeley, 2000. link.

From https://github.com/pyt-team/challenge-icml-2024/pull/65