This package provides data structures and algorithms for combinatorial topology. Currently, it can handle abstract simplicial complexes, directed complexes, and combinatorial codes. The package is written in Julia language. The long-term goal of this project is to be a "swiss-knife" for manipulating (very large) combinatorial structures, with an eye towards topological data analysis.
DISCLAIMER: This software is still in development. The documentation is currently very sparse. Use at your own risk! Please let us know if you'd like to contribute. The work was supported by the ARO award W911NF-15-1-0084.
This package interfaces with existing software for homology computations, such as Perseus. In the future, Simplicial will interface with other TDA software.
julia> Pkg.update(); Pkg.add("Plotly")
julia> Pkg.clone("https://github.com/nebneuron/Simplicial.git")
julia> using Simplicial
Let's create a filtration of Dowker complexes of a matrix A:
julia> A=rand(10,30); K, GraphDensity=DowkerComplex(A); show(K)
Let's compute the persistent intervals of the Dowker complex of A, in dimension <=2 and going no further than graph density<=0.7:
julia> Intervals, GraphDensity= DowkerPersistentintervals(A,0.7,2);
Let's plot the Betti curves for these persistent intervals:
julia> using Plotly
julia> PlotBettiCurves(Intervals,GraphDensity,2)
The module Simplicial defines the following types:
- The type
CodeWord
is an alias forSet{Int16}
. It is always recommended to use it instead of Set{Int}, as the exact data types may change in the future. CombinatorialCode
for combinatorial codes.SimplicialComplex
for simplicial complexes.FiltrationOfSimplicialComplexes
for increasing sequences of simplicial complexes.
There is a number of utility constants, such as emptyset
(the empty set as an instance of type CodeWord
).
Objects of this type represent combinatorial codes (V,C). It has the following constructors:
C = CombinatorialCode(ListOfWords::Array{Any,1})
will convert each element ofListOfWords
into aCodeWord
, then remove repetitions of words, before storing them in sorted order inC.words
. Moreover, it setsC.vertices
to be the union of all sets inListOfWords
C = CombinatorialCode(words::Array{CodeWord,1}, vertices::CodeWord)
same as above, except it manually setsC.vertices
C = CombinatorialCode(SC::SimplicialComplex)
creates a code which stores every face ofSC
The following methods are defined:
HasEmptySet(code::CombinatorialCode)
returns true if the emptyset is an element ofcode
Objects of this type represent simplicial complexes (V,D). They are stored as a list of the facets of D. It has the following constructors:
K = SimplicialComplex(ListOfWords::Array{Any,1})
converts the elements ofListOfWords
toCodeWord
and then stores the maximal (by set inclusion) words. Moreover, it setsK.vertices
to the union of the facets.K = SimplicialComplex(CC::CombinatorialCode)
creates a simplicial complex which represents the "subset-completion" ofCC
(It's what you think it is; the description is still to be written).
The following methods are defined:
isvoid(code::CombinatorialCode)
returns true ifcode
contains no codewords (not even the empty set)isirrelevant(code::CombinatorialCode)
returns true ifcode
consists of only the empty setisvoid(K::SimplicialComplex)
returns true ifK
contains no facets (not even the empty set)isirrelevant(K::SimplicialComplex)
returns true ifK
has only the empty set
Equality comparison operator has the following methods added:
==(SC1::SimplicialComplex, SC2::SimplicialComplex)
compares two instances ofSimplicialComplex
==(C1::CombinatorialCode,C2::CombinatorialCode)
compares two instances ofCombinatorialCode
Membership query can operate on the following types:
in(word::CodeWord,code::CombinatorialCode)
returns true ifword
is an element ofcode.words
in(a::Array{Int,1},c::CombinatorialCode)
in(word::CodeWord,K::SimplicialComplex)
in(a::Array{Int,1},K::SimplicialComplex)
Methods for pretty-printing are added:
show(c::CodeWord)
show(K::SimplicialComplex)
Methods for computing the link of a codeword or simplex:
link(SC::SimplicialComplex, sigma::Set{Int})
returns a new complex representing the link ofsigma
inSC
link(C::CombinatorialCode, sigma::Set{Int})
returns a new code representing the link ofsigma
inC
del(SC::SimplicialComplex, sigma::Set{Int})
returns a newSimplicialComplex
withsigma
and all its cofaces deleted.del(C::CombinatorialCode, sigma::Set{Int})
returns a newCombinatorialCode
by subtractingsigma
from each codeword inC
returns a new simplicial complex which is the Alexander Dual of SC. WARNING: THERE IS CURRENTLY A BUG IN Alexander_dual(SC::SimplicialComplex). DO NOT USE
Definition: A combinatorial code is a pair (V,C) where V is a finite set (typically the set {1,...,n} for some n) and C is a set of subsets of V. The elements of C are called codewords; the set V is sometimes called the set of vertices.
Definition: An abstract simplicial complex is a pair (V,D) where V is a finite set and D is a collection of subsets of V satisfying two conditions:
- for all v in V, {v} is in D
- for all s in D, if t is a subset of s, then t is in D We typically refer to a simplicial complex simply as D. If s is in D, we call s a face of D or a simplex of D (from here forward, we will use "face" exclusively). The subsets of a face are, in turn, its faces, and its supersets (in D) are its cofaces. When D is ambiguously used to refer to the pair (V,D), we denote V by V(D).
We call attention to a special case here: there are two possible simplicial complexes with empty vertex (i.e. V = {}). The first is the void complex, or the null complex, where D is also empty (so V = {}, D = {}). The other is the irrelevant complex or the empty complex, where D contains only one set, the empty set (so V = {}, D = {{}}).
- The dimension of a face is one less than the number of elements in that face. The dimension of a simplicial complex is the maximum of the dimensions of its faces. In particular, this means the empty complex has dimension -1. We define the dimension of the void complex to be -Infinity.
- A facet is a maximal (by set inclusion) face of a simplicial complex. A simplicial complex is pure if all its facets are of the same dimension.
- The Alexander dual of a simplicial complex (V,D) is the complex (V,D') where s is in D' iff V \ s is not in D.
- The link of a face s is the simplicial complex link(s,D) = {t \subset V : s \cap t = empty, s \cup t \in D}.