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.
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,))
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!
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
.
- 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 ofn
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.
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.