Using Gudhi to get the free pairs

[lnajman]

Hi,

I would like to obtain the free pairs of a complex. In Boissonat's paper, it is written (section 2.2.2) that getting free pairs is easy with the simplex tree. However, the only way I am currently able to get free pairs with Gudhi is by doing the following

import gudhi as gd
def findFreePairs(st: gd.simplex_tree.SimplexTree):
  freepairs = list()
  st_gen = st.get_simplices()
  for (simplex, filtr) in st_gen:
    cofaces = st.get_cofaces(simplex, 1)
    if len(cofaces) == 1:
      freepairs.append((simplex, cofaces[0][0]))
  return freepairs

Is there a better way?

[mglisse]

What they say in the paper is that it is easy to check if a simplex is the smaller one of a pair, by checking that it has only one coface.

1. If you want all the pairs, you still need to go through all the simplices and check this property for each of them, like you are doing (or find some other argument to limit the search). I don't think they claim that it is easy to enumerate the pairs, or I missed a section in the paper.
2. In the paper, they use an augmented version of the simplex tree with extra pointers to speed up the computation of cofaces (at least when the complex has nice locality properties). In Gudhi, at least for now, we only have a basic version without those extra pointers, so computing cofaces is super slow.

To find cofaces more efficiently, you essentially have to maintain your own datastructure. For instance

num_cofaces=defaultdict(int)
for s,_ in st.get_simplices():
    for t,_ in st.get_boundaries(s):
        num_cofaces[tuple(t)]+=1
[x for x,y in num_cofaces.items() if y==1]

gives you the smaller simplex in each pair. Note that the pairs are not disjoint.

The "best" way depends on what you want to do with those pairs.

[lnajman]

Many thanks for your answer. Is there a plan to include (downward and upward) Hasse diagram of a complex in Gudhi in a future release? Such diagrams will be of great help for removing free pairs or other simplices, and doing similar operations on a complex.

[mglisse]

Is there a plan to include (downward and upward) Hasse diagram of a complex in Gudhi in a future release?

(the simplex tree already has a function to get the boundary of a simplex with reasonable performance, it is only the coboundary that is super slow)
Not in the short term. In the long term, we would like to have other datastructures for complexes. The simplex tree has some nice theoretical properties, but they mostly apply if you want an explicit representation (each cell really has some memory associated to it) and the dimension is large. For low dimension, it does not save much memory, and operations are slower than they would be with other structures. However, it is not yet clear what the right level of generality is (just simplicial complexes? Any Hasse diagram? Even more general? The more general it is, the less efficient it will be, and we do not have resources to implement and maintain a dozen different structures). There is one structure hidden somewhere deep in the Coxeter triangulation module, but we do not recommend using it at this point.

One thing that may appear in Gudhi is a structure to represent a boundary matrix, which in some sense is equivalent to a Hasse diagram, although the interface wouldn't be targeted to this kind of use.

Depending on what you are trying to do exactly, we have other things in the C++ part of the library. The skeleton-blocker datastructure implicitly represents simplicial complexes and has functionality to find edges that can be contracted without changing the topology. There is also the toplex map for another implicit representation. If your complex is a flag complex, we have edge collapses that work on an implicit representation and perform the equivalent of a large number of elementary collapses.

[lnajman]

What I am currently doing is some algorithms to compute a Morse gradient from a filtration (on a general complex), finding both critical simplices and free pairs. The basic building blocks for this type of algorithms are removal of free pairs, and removal of critical simplices (of maximal dimension). That could work directly on a filtration, just by changing the level of the filtration. However, I still need to identify free pairs and maximal simplices in a general complex. Ideally, that should work both for simplicial complexes and for cubical complexes. The Hasse diagram of simplicial and cubical complexes should be enough. In the near future, I hope to extend those algorithms to “repair” a filtration. The basic building blocks are the same.

I was hoping to rely on a library such as Gudhi to make the first tests. I do not need C++ speed at this stage, but I need to be able to work (in a reasonable time) with real data such as images, or large data points.