simplextree

simplextree is an R package aimed at simplifying computation for general simplicial complexes of any dimension. This package facilitates this aim by providing R bindings to a Simplex Tree data structure, implemented using modern C++11 and exported as a Rcpp module. The underlying library implementation also exports a C++ header, which can be specified as a dependency and used in other packages via Rcpp attributes.

The Simplex Tree was originally introduced in the following paper:

Boissonnat, Jean-Daniel, and Clément Maria. "The simplex tree: An efficient data structure for general simplicial complexes." Algorithmica 70.3 (2014): 406-427.

A Simplex Tree is an ordered, trie-like structure whose nodes are in bijection with the faces of the complex. Here's a picture (taken from the paper) of a simplicial 3-complex (left) and its corresponding Simplex Tree (right):

Installation

The most recent release is available on CRAN and can be installed via the usual method

install.packages("simplextree")

Alternatively, the current development version can be installed with the devtools package:

require("devtools")
devtools::install_github("peekxc/simplextree")

Quickstart

library(simplextree)
st <- simplex_tree()              ## creates a simplex tree
st %>% insert(list(1:3, 4:5, 6))  ## Inserts simplices { 1, 2, 3 }, { 4, 5 }, and { 6 }

## Summary of complex
print(st) 
# Simplex Tree with (6, 4, 1) (0, 1, 2)-simplices

## More detailed look at structure
st %>% print_simplices("tree")
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0): 
# 4 (h = 1): .( 5 )
# 5 (h = 0): 
# 6 (h = 0): 

## Print the set of simplices making up the star of the simplex '2'
print_simplices(st %>% cofaces(2))
# 2, 2 3, 2 3 4, 2 3 4 5, 2 3 5, 2 4, 2 4 5, 2 5, 1 2, 1 2 3

## You can also compactly print traversals of the complex  
dfs <- preorder(st)
print_simplices(dfs, "column")
# 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4 5 6
#   2 2 3 3 3 3 3 4 4 5 6   3 3 3 3 4 4 5   4 4 5 6   5    
#     3   4 4 5 6   5         4 4 5   5       5            
#           5                   5

## Or save them as a list 
dfs_list <- as.list(dfs)
# list(1, c(1,2), ...)

## Get connected components 
print(st$connected_components)
# [1] 1 1 1 4 4 5

## Serialization/persistent storage options available
saveRDS(st %>% serialize(), file = tempfile())

## As are various export options
list_of_simplices <- st$as_list()
adj_matrix <- st$as_adjacency_matrix()
# ... see also as_adjacency_list(), as_edge_list

API Reference

Below is the API reference for the R-bindings of the SimplexTree class. A SimplexTree object can also be passed, manipulated, and modified via C++ in another R package as well. See Usage with Rcpp.

In what follows, individual simplex's are assumed to be integer vectors. Numeric vectors are implicitly cast to integer vectors. Some methods accept multiple simplices as well, which can be specified as a list of integer vectors.

SimplexTree

# simplex_tree()

Wrapper for constructing a SimplexTree instance. See below.

# SimplexTree (C++ Class)

Exposed binding for an internal SimplexTree C++ class. The binding is exposed as an Rcpp Module. Module instances are of the class type Rcpp_SimplexTree.

SimplexTree instances can be created with either simplex_tree() or new(SimplexTree).

Fields

Fields are data attributes associated with the SimplexTree instance containing useful information about the simplex tree. Writeable fields can be set by the user to change the behaviour of certain methods, whereas read-only fields are automatically updated as the tree is modified.

# SimplexTree $ n_simplices

An integer vector, where each index k denotes the number of (k-1)-simplices. ( Read-only )

# SimplexTree $ dimension

The dimension of a simplicial complex K is the highest dimension of any of K's simplices. ( Read-only )

# SimplexTree $ id_policy

The id_policy of the SimplexTree instance determines how new vertex ids are generated by the generate_ids method. Can be either "compressed" or "unique". Defaults to "compressed".

Properties

Properties are aliases to methods that act as data fields, but on access dynamically generate and return their values, much like active bindings in R. Unlike fields, properties do not store their results with the instance, and do not contribute to the memory footprint of the simplicial complex.

# SimplexTree $ connected_components

Returns the connected components of the simplicial complex.

Each connected component is associated with an integer; the result of this function is an integer vector mapping the (ordered) set vertices to their corresponding connected component.

# SimplexTree $ vertices

Returns the 0-simplices in the simplicial complex as an n-length vector, where n is the number of 0-simplices.

# SimplexTree $ edges

Returns the 1-simplices in the simplicial complex as an ( n x 2 ) matrix, where n is the number of 1-simplices.

# SimplexTree $ triangles

Returns the 2-simplices in the simplicial complex as an ( n x 3 ) matrix, where n is the number of 2-simplices.

# SimplexTree $ quads

Returns the 3-simplices in the simplicial complex as an ( n x 4 ) matrix, where n is the number of 3-simplices.

Modifying the tree

# insert(SimplexTree, [simplices])

Inserts simplices into the simplex tree. Each simplex is ordered prior to insertion. If a simplex already exists, the tree is not modified. To keep the property of being a simplex tree, the proper faces of simplex are also inserted.

Insertion examples

​

st <- simplex_tree()
st %>% insert(c(1, 2, 3))       ## insert the simplex { 1, 2, 3 }
st %>% insert(list(c(4, 5), 6)) ## insert the simplices { 4, 5 } and { 6 }
print(st)
# Simplex Tree with (6, 4, 1) (0, 1, 2)-simplices

# remove(SimplexTree, [simplices])

Removes simplices from the simplex tree. Each simplex is ordered prior to removal. If a simplex doesn't exist, the tree is not modified. To keep the property of being a simplex tree, the cofaces of simplex are also removed.

Removal examples

​

st <- simplex_tree()
st %>% insert(list(c(1, 2, 3), c(4, 5), 6))
st %>% remove(c(2, 3)) ## { 2, 3 } and { 1, 2, 3 } both removed
print(st)
# Simplex Tree with (6, 3) (0, 1)-simplices

# contract(SimplexTree, [a, b])

Performs and edge contraction, contracting vertex b to vertex a. This is equivalent to removing vertex b from the simplex tree and augmenting the link of vertex a with the link of vertex b. If the edge does not exist in the tree, the tree is not modified.

Contraction example

st <- simplex_tree()
st %>% insert(1:3)
st %>% print_simplices("tree")
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0): 
st %>% contract(c(1, 3))
st %>% print_simplices("tree")
# 1 (h = 1): .( 2 )
# 2 (h = 0): 

# collapse(SimplexTree, ...)

1. ([tau], [sigma])
2. ((u, v), w)

Performs an elementary collapse. There are multiple simplifying operations that have been referred to as elementary collapses; this method provides two such operations.

(1) elementary collapse ( from 1 )

Collapses tau through its coface sigma if sigma is the only coface of tau, where tau and sigma are both simplexes.

(2) vertex collapse ( from 2 )

Collapses a free pair (u, v) -> (w), where u, v, and w are all vertices.

Note that an elementary collapse in this sense has an injectivity requirement that either u = w, such that (u, v) -> (u), or v = w, such that (u, v) -> (v). If (u, v) -> (w) is specified, where u != w and v != w , the collapse is decomposed into two elementary collapses, (u, w) -> (w) and (v, w) -> (w), and both are performed.

Collapse example

st <- simplex_tree()
st %>% insert(1:3)
st %>% print_simplices("tree")
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0): 
st %>% collapse(list(1:2, 1:3)) ## collapse in the sense of (1)
st %>% print_simplices("tree")
# 1 (h = 1): .( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0):
  
st %>% insert(list(1:3, 2:5))
st %>% print_simplices("tree")
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 3): .( 3 4 5 )..( 4 5 5 )...( 5 )
# 3 (h = 2): .( 4 5 )..( 5 )
# 4 (h = 1): .( 5 )
# 5 (h = 0): 
st %>% collapse(list(3, 4), 5) ## collapse in the sense of (2)
st %>% print_simplices("tree")
# 1 (h = 2): .( 2 5 )..( 5 )
# 2 (h = 2): .( 5 )..( 5 )
# 5 (h = 1): .( 5 )

# expand(SimplexTree, k)

Performs a k-expansion, constructing the k-skeleton as a flag complex. The expansion is performed by successively inserting all the simplices of k-skeleton into the tree.

Expansion example

st <- simplex_tree()
st %>% insert(list(c(1, 2), c(2, 3), c(1, 3)))
st %>% print_simplices("tree")
# 1 (h = 1): .( 2 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0):
  
st %>% expand(k=2) ## expand to simplicial 2-complex
st %>% print_simplices("tree")
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0): 

# SimplexTree $ as_XPtr()

Converts the simplex tree into an XPtr, sometimes called an external pointer. XPtr's can be passed as an SEXP to other C/C++ functions via R's C API or Rcpp. For usage, see Usage with Rcpp.

This method does not register a delete finalizer.

Querying the tree

# print_simplices(SimplexTree, format = "short")

Prints a formatted summary of the simplicial complex to R's buffered output. By default, this shows up on the R console. Available outputs include "summary", "tree", "cousins", "short", "column", or "row". See the internal R documentation for more details.

# find(SimplexTree, [simplices])

Traverses the simplex tree downard starting at the root by successively using each of the ordered labels in simplex as keys. Returns a logical indicating whether simplex was found, for each simplex in simplices. Each simplex is sorted prior to traversing.

# degree(SimplexTree, [vertices])

Returns the degree of a given vertex or set of vertices.

# adjacent(SimplexTree, vertex)

Returns the set of vertices adjacent to a given vertex.

# is_face(SimplexTree, [tau], [sigma])

Returns a logical indicating whether tau is a face of sigma.

# is_tree(SimplexTree)

Returns a logical indicating whether the simplex tree is fully connected and acyclic.

# generate_ids(SimplexTree, n)

Generates n new vertex ids which do not exist in the tree according to the current id_policy.

Traversals

The SimplexTree data structure supports various types of traversals. A traversal is a (possibly optimized) path that allows iteration through a subset of the SimplexTree. Once a traversal is parameterized, they can be saved as variables and used as arguments into the free function traverse, straverse, and ltraverse. They can also be converted explicitly to list form via the as.list S3 specialization.

# traverse(traversal, f)

Executes a given traversal, passing each simplex in the traversal as the only argument to f. Output returned by f, if any, is discarded. This function does not return a value.

# ltraverse(traversal, f)

Executes a given traversal, passing each simplex in the traversal as the only argument to f, returning a list of the same length as the traversal path whose elements contain the result of f. ltraverse is meant to used in a similar way as lapply.

# straverse(traversal, f)

Executes a given traversal, passing each simplex in the traversal as the only argument to f, returning a vector of the same length as the traversal path whose elements contain the result of f. straverse is meant to used in a similar way as sapply.

The currently supported traversals are the following:

# preorder(SimplexTree, simplex)

Performs a preorder traversal of the SimplexTree starting at simplex. If simplex is not supplied, the traversal starts at the first vertex in the complex.

# level_order(SimplexTree, simplex)

Performs a level order traversal of the SimplexTree starting at simplex. If simplex is not supplied, the traversal starts at the first vertex in the complex.

# faces(SimplexTree, simplex)

Performs a traversal over the faces of simplex in the SimplexTree. Supplying simplex is required.

# cofaces(SimplexTree, simplex)

Traverse all of the cofaces (the star) of simplex in the SimplexTree. Supplying simplex is required.

# coface_roots(SimplexTree, simplex)

Traverse all of the roots whose subtrees comprise the cofaces of simplex in the SimplexTree. Supplying simplex is required.

# link(SimplexTree, simplex)

Traverse all of the simplices of the link of simplex in the SimplexTree. Supplying simplex is required.

# k_skeleton(SimplexTree, k, simplex)

Traverses all of simplices of dimension k or less in the SimplexTree. If simplex is not supplied, the traversal starts at the first vertex in the complex.

# k_simplices(SimplexTree, k, simplex)

Traverses all of simplices of dimension k in the SimplexTree. If simplex is not supplied, the traversal starts at the first vertex in the complex.

# maximal(SimplexTree)

Performs a traversal over the maximal faces in the SimplexTree. A simplex is considered maximal in this case if it has itself as its only coface.

Import / Export options

# serialize(SimplexTree)

Serializes the simplex tree K into some of smaller representation needed to recover the simplex tree.

# SimplexTree $ deserialize(complex, SimplexTree)

Deserializes complex, the result of serialize, into the given SimplexTree if supplied, or an empty SimplexTree otherwise.

Conversions

The full simplicial complex can always be converted to a list of matrices, and the 1-skeleton can also be converted to any of the standard graph representations.

# SimplexTree $ as_list()

Converts the simplex tree to list of (n x k) matrices, where each matrix represents the set of k-1 simplices.

# SimplexTree $ as_edge_list()

Converts the 1-skeleton to an edge list.

# SimplexTree $ as_adjacency_list()

Converts the 1-skeleton to an adjacency list.

# SimplexTree $ as_adjacency_matrix()

Converts the 1-skeleton to an adjacency matrix.

Usage with Rcpp

There are two ways to use a SimplexTree object with Rcpp.

1. Pure Rcpp

If you're developing purely in Rcpp, you can just use the SimplexTree class directly. The SimplexTree is header-only, and can be imported via the Rcpp::depends attribute (see Rcpp Attributes)

Example Usage in Rcpp

#include "Rcpp.h"

// [[Rcpp::depends(simplextree)]]
#include "simplextree.h"

void my_function(){
  SimplexTree st = SimplexTree();
  ...
}

If you're developing using a package, make sure to add simplextree to the LinkingTo list to ensure the header is properly included (e.g. -I"<...>/simplextree/include" should appear in the build steps).

2. Moving between R and Rcpp

A SimplexTree Rcpp module can be passed directly from R to any Rcpp method. To do so, export the object as an external pointer (XPtr) in R, pass the SEXP directly to the method, then wrap as as smart external pointer on the C++ side.

Example Usage with R and Rcpp

For example, on the C++ side, one might do:

// my_source.cpp
#include "Rcpp.h"

// [[Rcpp::depends(simplextree)]]
#include "simplextree.h"

[[Rcpp::export]]
void modify_tree(SEXP stree){
  Rcpp::XPtr<SimplexTree> stree_ptr(stree);
  stree_ptr->print_tree();
  ....
}

Then on the R-side, use as_XPtr method to get an XPtr.

# my_source.R
st <- simplex_tree()
modify_tree(st$as_XPtr())

Note that the C++ class contains a superset of the functionality exported to R, however they do not necessarily have the same bindings. See the header file for a complete list.

Visualizing the complex

Summarizing the complex can be achieved via either the overridden S3 print generic or the more detailed print_tree method.

library(simplextree)
st <- simplex_tree()
st %>% insert(list(1:3, 3:6))

print(st)
# Simplex Tree with (6, 9, 5, 1) (0, 1, 2, 3)-simplices

print_simplices(st, "tree")
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 3): .( 4 5 6 )..( 5 6 6 )...( 6 )
# 4 (h = 2): .( 5 6 )..( 6 )
# 5 (h = 1): .( 6 )
# 6 (h = 0): 

Alternatively, the plot generic is also overridden for SimplexTree objects (of class type 'Rcpp_SimplexTree') to display the complex with base graphics.

st %>% insert(list(6:7, 7:8, 8:10, 11:12))
plot(st)

There are many other options for controlling how the complex is displayed (e.g. the positions of the simplices, the sizes/linewidths of the vertices/edges, the vertex labels, whether to color only maximal faces or individual simplices, etc.). For the full documentation, see ?plot.simplextree.

More information

The full documentation for both the plot package is available in the man pages.

## see ?simplextree

References

1. Boissonnat, Jean-Daniel, and Clément Maria. "The simplex tree: An efficient data structure for general simplicial complexes." Algorithmica 70.3 (2014): 406-427.

2. Dey, Tamal K., Fengtao Fan, and Yusu Wang. "Computing topological persistence for simplicial maps." Proceedings of the thirtieth annual symposium on Computational geometry. ACM, 2014.