Skip to content
R package for simplifying general computation on simplicial complexes
C++ R
Branch: master
Clone or download

README.md

simplextree

Appveyor Windows Build status Travis OS X Build status Travis Linux X Build status

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):

simplex tree picture

Installation

The current development version can be installed with the devtools package:

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

A stable CRAN release is planned for the future.

Quickstart

library(simplextree)
st <- simplex_tree() ## instantiation wrapper
st$insert(list(1:3, 4:5, 6)) ## Inserts { 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_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'
st$traverse(2, function(simplex){ print(simplex) }, "star")
# [1] 1 2
# [1] 1 2 3
# [1] 2
# [1] 2 3

## Retrieves list of all simplices in DFS order, starting with the empty face 
dfs_list <- st$ltraverse(empty_face, identity, "dfs")

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

## Serialization/persistent storage options available
print(st$serialize())
# [[1]]
# [1] 1 2 3
# [[2]]
# [1] 4 5
# [[3]]
# [1] 6

## 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

# SimplexTree $ insert([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.

Note that the SimplexTree structure does not track orientation, e.g. the simplices (1, 2, 3) and (2, 1, 3) are considered identical.

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

# SimplexTree $ remove([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, 4, 1) (0, 1, 2)-simplices

# SimplexTree $ contract([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_tree()
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0): 
st$contract(c(1, 3))
st$print_tree()
# 1 (h = 1): .( 2 )
# 2 (h = 0): 

# SimplexTree $ collapse(...)

  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_tree()
# 1 (h = 2): .( 2 3 )..( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0): 
st$collapse(1:2, 1:3) ## collapse in the sense of (1)
st$print_tree()
# 1 (h = 1): .( 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0):
  
st$insert(list(1:3, 2:5))
st$print_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(3, 4, 5) ## collapse in the sense of (2)
st$print_tree()
# 1 (h = 2): .( 2 5 )..( 5 )
# 2 (h = 2): .( 5 )..( 5 )
# 5 (h = 1): .( 5 )

# SimplexTree $ expand(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.

This method assumes the dimension of the simplicial complex before expansion is 1.

Expansion example
st <- simplex_tree()
st$insert(list(c(1, 2), c(2, 3), c(1, 3)))
st$print_tree()
# 1 (h = 1): .( 2 3 )
# 2 (h = 1): .( 3 )
# 3 (h = 0):
  
st$expand(k=2) ## expand to simplicial 2-complex
st$print_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

# SimplexTree $ print_tree()

Prints the simplicial complex to standard out. By default, this is set to R's buffered output, which is shown in the R console. The printed format is:

[vertex] (h = [subtree height]): [subtree depth]([subtree])

Where each line corresponds to a vertex and its corresponding subtree. The subtree depth represents the set of sibling k-simplices at that level in tree, represented by a sequence of dots ('.').

# SimplexTree $ find([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.

# SimplexTree $ degree([vertices])

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

# SimplexTree $ adjacent(vertex)

Returns the set of vertices adjacent to a given vertex.

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

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

# SimplexTree $ is_tree()

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

# SimplexTree $ generate_ids(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. The traversal type determines the subset and path to iterate through. During the traversal, each simplex is passed to f as its only argument.

# SimplexTree $ traverse

  1. (f, type)
  2. ([simplex], f, type)
  3. ([simplex], f, type, params)

The traverse method has three overloads, based on the traversal type and intended usage of f.

(1) applies f to each simplex in the traversal path type, starting at the root of the tree.

(2) applies f to each simplex in the traversal path type , starting at the specified simplex in the tree. The root simplex (empty face) may be specified using the empty_face alias or the NULL keyword.

(3) applies f to each simplex in the traversal path type, starting at the specified simplex in the tree. The root simplex (empty face) may be specified using the NULL keyword or the empty_face alias. Additional parameters may be supplied to the traversal type as via params as a list.

Traversal Examples

Traverse using first overload (performs depth-first traversal on simplex tree):

st <- simplex_tree()
st$insert(1:3)
st$traverse(message, "dfs") # equivalent to 'st$traverse(NULL, message, "dfs")'
# (empty face)
# 1
# 12
# 123
# 13
# 2
# 23
# 3

Traverse using second overload (prints the cofaces of the vertex with label '1'):

st$traverse(1, message, "cofaces")
# 1
# 12
# 123
# 13

Traverse using third overload (prints the 1-simplices):

st$traverse(1, message, "maximal-skeleton", list(k=1))
# 1
# 12
# 123
# 13

# SimplexTree $ ltraverse(...)

Performs a traversal, returning a list of the same length as the traversal path, with each element containing the result of f. The parameters ... are the same as in traverse. ltraverse is meant to used in a similar way as lapply.

Traversal types

The type parameter passed to the traverse family of algorithms determines the subset and corresponding path that is enumerated in simplex tree. A traversal type is specified by a string, and its corresponding params are specified in a list. The currently supported traversal types are as follows:

# type = "dfs"

Performs a depth-first traversal of the SimplexTree starting at simplex. If simplex is not supplied, the traversal starts at the root node.

# type = "bfs"

Performs a breadth-first traversal of the SimplexTree starting at simplex. If simplex is not supplied, the traversal starts at the root node.

# type = "cofaces" or type = "star"

Traverse all of the cofaces (the star) of simplex in the SimplexTree. If simplex is not supplied, the traversal starts at the root node.

# type = "link"

Traverse all of the link of simplex in the SimplexTree. If simplex is not supplied, the traversal starts at the root node.

# type = "skeleton"

Traverses all of simplices in the the k-skeleton of the SimplexTree, where the dimension k must be supplied via params. If simplex is not supplied, the traversal starts at the root node.

# type = "maximal-skeleton"

Traverses all of simplices in the the maximal k-skeleton of the SimplexTree, where the dimension k must be supplied via params. If simplex is not supplied, the traversal starts at the root node.

Import / Export options

# SimplexTree $ serialize()

Serializes the simplex tree K into a minimal set of maximal faces of K needed to recover the simplex tree. Returns the set as list of simplices.

# SimplexTree $ deserialize()

Deserializes a list of simplices by successively inserting them into the simplex tree.

# SimplexTree $ save(filename)

Saves a serialized version the simplex tree to filename in the RDS file.

# SimplexTree $ load(filename)

Loads a RDS file saved to filename into the simplex tree.

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
stree <- simplextree::simplex_tree()
modify_tree(stree$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.

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.

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

st$print_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
You can’t perform that action at this time.