junipertcy/simpliciality-testing

A backtracking-based algorithm to check if a given degree-size sequence can realize a simplicial complex

Simplicial-test implements a deterministic, backtracking-based algorithm to check whether a degree-size sequence is simplicial.

This is the software repository behind the paper:

• Construction of simplicial complexes with prescribed degree-size sequences, published in Physical Review E 104, L042303 (2021).

Read it on: arXiv:2106.00185 or Phys. Rev. E.

• For full documentation, please visit this site.
• For general Q&A, ideas, or other things, please visit Discussions.
• For software-related bugs, issues, or suggestions, please use Issues.

First steps

Simplicial-test is on PyPI. To start, hit this command on the shell:

$ pip install simplicial-test

Here's a typical simplicial complex realization problem: Can d = (3, 3, 2, 2, 1, 1, 1, 1) and s = (4, 3, 2, 2, 2, 1) be the degree-size sequence of some simplicial complex?

In your Python console, simplicial-test is invoked using:

>>> from simplicial_test import Test, compute_joint_seq, if_facets_simplicial
>>> degree_list = [3, 3, 2, 2, 1, 1, 1, 1]
>>> size_list = [4, 3, 2, 2, 2, 1]
>>> st = Test(degree_list, size_list)  # visit the docs for other options, like setting a cutoff to give up.
>>> is_simplicial, facets = st.is_simplicial()  # actual computation
>>> assert is_simplicial is True
>>> assert if_facets_simplicial(facets) is True
>>> assert compute_joint_seq(facets) == (sorted(degree_list, reverse=True), sorted(size_list, reverse=True))
>>> facets
((0, 1, 2, 4), (0, 1, 3), (0, 5), (1, 6), (2, 3), (7,))

Command-line Utility and Unit Tests

Alternatively, you may install Simplicial-test from the source:

$ git clone https://github.com/junipertcy/simplicial-test.git
$ cd simplicial-test
$ python setup.py install  # if you do not want to install it yet, skip this step.

In the simplicial-test folder, there's a useful script that allows you to do the simplicial test (even when it's not installed), by hard-coded integer sequences in datasets/00_degs.txt and datasets/00_sizes.txt as the input.

$ python utils/is_simplicial.py --help

Usage: is_simplicial.py [OPTIONS]

Options:
  -k, --degree_seq_file FILENAME  Path to degree sequence file.
  -s, --size_seq_file FILENAME    Path to size sequence file.
  -c, --cutoff INTEGER            Cutoff (max. steps) to the search.
  -w, --width INTEGER             Search width (see the docs).
  -d, --depth INTEGER             Backtrack depth (see the docs).
  --verbose                       Turn on the verbose mode.
  --help                          Show this message and exit.

To run the simplicial test on the command line:

$ python utils/is_simplicial.py -k datasets/00_degs.txt -s datasets/00_sizes.txt

Yes, the degree-size sequence is simplicial. 
The complex is: ((0, 1, 2, 3), (0, 1, 4), (0, 1, 5), (0, 2, 4), (3, 6), (7,))

Look, the program gives an affirmative answer, with a realization in the standard output.

Simplicial-test implements a search algorithm for solving the simplicial realization problem. If your input degree-size sequence is not realizable (as a simplicial complex), we may need to traverse the entire search tree, which would take a huge amount of time!

Thru numerical experiments, we find that the majority of the input degree-size sequences lie in the polynomial regime, which means that they can be solved rather easily.

For example, you can assemble a simplicial complex from the degree-size sequence of the crime network dataset, from this Phys. Rev. E paper, which contains 551 nodes and 194 facets, via

$ python utils/is_simplicial.py -k datasets/crime_degs.txt -s datasets/crime_sizes.txt

Boom! You'll see the realization in standard output. It's fast, isn't it?

Lastly, remember to check out the docs for the full documentation!

Development

Simplicial-test uses poetry for packaging and tox for testing. Once you have these two libraries installed, you can run tox to standardize testing on various Python versions (cf. tox.ini)

You may also test with your local environment (for details, see tests/), by running pytest.

Related links

• To see how Simplicial-test scales, check out this benchmark.
• The simplicial configuration model (SCM) - the paper (arXiv) that inspires this work.
• The implementation of the SCM sampler.
• The partition numbers: A000041.
• SageMath's random_element_uniform() that returns a random partition of n with uniform probability.
• The Erdős–Gallai theorem for graphicality testing.
• The Gale–Ryser theorem for bigraphicality testing.
• The Havel–Hakimi algorithm for constructive graphical realization.

Acknowledgement

The simplicial-test library is inspired and supported by Josh Grochow, Jean-Gabriel Young, and Alice Patania.

We want to thank Stefanie Molin (@stefmolin) for their Custom-Colormaps, Iacopo Iacopini (@iaciac) for their py-draw-simplicial-complex, whose repositories make pretty figures, and Austin Benson (@arbenson) for their hypergraph datasets that helped identify bugs of the algorithm in larger instance sizes.