edu.stanford.math.plex

Class Simplex

java.lang.Object

edu.stanford.math.plex.Simplex

All Implemented Interfaces:

java.lang.Comparable<Simplex>

Direct Known Subclasses:

Packed2Simplex, Packed4Simplex, Packed6Simplex, Packed8Simplex

public abstract class Simplex
extends java.lang.Object
implements java.lang.Comparable<Simplex>

A Simplex is the basic unit for simplicial homology calculations, literally. That is, the module in which simplicial homology is defined is the free module over all simplices, so a simplex is actually a basis element for this module. Formally, simplices are elements of a set S of non-empty finite subsets of a set X which have the property that if B is an element of S, and A is a non-empty subset of B, then A is an element of S. Intuitively, if you imagine that the points of X are in some n-dimensional Euclidean space, then a simplex is that subset of Euclidean space that is given by the affine combinations of its "corners". For instance, if B is the triangle given by corners {a, b, c} is one of our simplices, then we require that the edge (line segment) given by {a, c} is also a simplex. While we can describe this relationship in a purely combinatorial fashion, the "meaning" is given by the choice of simplices S, and this methodology used here always makes some use of geometric techniques (e.g., metric spaces).

For reasons of efficiency, we use more than one encoding for simplices, instead of using the obvious "array of vertices". The reason for this is that these encodings of simplices can be much smaller, and the code to manage them much faster, than if we use the obvious implementation. We make Simplex an abstract class, instead of an interface, both because code written to this class will be slightly faster than if it were an interface, and because the root class is a convenient repository for some utilities needed by the extension classes, and for "global information" such as the characteristic of the base field.

All but the most naive encoding must have, either implicitly or explicitly, limits on the allowed dimension and number of landmarks that can be used to construct simplices. By default all limits will either be the explicit in the representation of the simplex or will be implicitly the largest values that are feasible for that representation. See the specific implementations for more details on this point.

The vertex set of any simplex depends on the context -- that is, for a Simplex s, s.vertices() is an array of integers of limited size, and the meaning of those integers will depend on the source of the Simplex s. The data sets we operate on frequently have millions of points (and we hope to push these even further in the future), but we only construct simplices from much smaller sets, often representative subsets we call "landmark sets". Since we are able to restrict landmarks to be in the thousands, or even hundreds, we use a smaller number of bits to encode the vertex sets for a simplex, often by "indirecting" through an array of landmark indices to some much larger data set. Thus, a vertex of 10 encoded within an instance of Simplex generally refers to the point whose index is the 10th entry in some landmark set, not the 10th point in the full data set.

Version:

0.1

Author:

Harlan Sexton

Field Summary

Fields

Modifier and Type	Field and Description
protected Chain	_chain
protected int	_findex The filtration index of the Simplex.

Constructor Summary

Constructors

Constructor and Description
Simplex()

Method Summary

Methods

Modifier and Type	Method and Description
Simplex	addVertex(int v) Add a vertex to a simplex.
Simplex	addVertex(int v, int f) Add a vertex to a simplex, and set the findex.
Chain	boundary(int p) Return the boundary of a simplex as a chain over a given characteristic.
abstract Simplex[]	boundaryArray() Return an array of simplices that describes the boundary.
Chain	chain() Get the chain value.
void	clearChain() Clear the chain value; used when we reuse the elementes in a stream.
int	compareTo(Simplex s) Implements Comparable interface.
abstract Simplex	copy() Make a "blank" copy of the Simplex -- equivalent to getSimplex(this.vertices()).
int	decrement_findex() Decrement the findex value -- this is a hack that should ONLY be used if you know what you are doing.
abstract int	dimension() Returns the dimension of self.
static double[]	dist_sort(double[] distances) Sort an array of double into increasing order, as needed for some Simplex operations.
boolean	equals(java.lang.Object obj) Overrides Object equals.
int	findex() Get the findex value.
static Simplex	getSimplex(int[] vertices) Get the simplex for a given set of vertices.
static Simplex	getSimplex(int[] vertices, int findex) Get the simplex for a given set of vertices, including setting findex.
static Simplex	getSimplexPresorted(int[] vertices) Get the simplex for an already verified array of vertices.
static Simplex	getSimplexPresorted(int[] vertices, int findex) Get the simplex for an already verified array of vertices, including setting findex.
int	hashCode() Overrides Object hashcode.
static Simplex	makeEdge(int v1, int v2, int findex) Get the edge for a pair of vertices.
static Simplex	makePoint(int v, int findex) Turn a vertex into a 0-simplex.
static void	persistence_sort(Simplex[] sarray) Sort, in place and using "persistence order", an array of simplices.
Chain	setChain(Chain c) Set the chain value, provided it hasn't already been set.
int	setfindex(int i) Set the findex value, provided it hasn't already been done.
static int[]	simplex_reverse_sort(int[] vertices) Sort a set of vertices into decreasing order, as needed for some Simplex operations.
boolean	subset(Simplex s) Is this a subset of s?
boolean	subset(Simplex s, int[] v, int[] sv) Is this a subset of s?
java.lang.String	toString() Represent a Simplex as a String.
static int[]	vertex_sort(int[] vertices) Sort a set of vertices into increasing order, as needed for some Simplex operations.
abstract int[]	vertices() Returns the indices of self as an array.
abstract int[]	vertices(int[] verts) Returns the indices of self as an array.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

_findex

protected int _findex

The filtration index of the Simplex.

Theoretically this could be abstract, but in all of the implementations we use this value is hard enough to find that it makes sense to cache it in the instance. Also, doing it this way allows us to make it effectively final without forcing the implementations to compute it during instance creation. We also get rid of the table T[] in the algorithm (see Persistence and references therein) by storing the reduced boundary chain directly in the Simplex instance. This is simpler, faster, and may even be smaller (it depends on what percentage of slots in T[] actually got filled).

_chain

protected Chain _chain

Constructor Detail

Simplex

public Simplex()

Method Detail

setfindex

public int setfindex(int i)

Set the findex value, provided it hasn't already been done.

Returns:

the findex value.

decrement_findex

public int decrement_findex()

Decrement the findex value -- this is a hack that should ONLY be used if you know what you are doing. Changing the findex of a Simplex already in a stream is a disaster.

Returns:

the findex value.

setChain

public Chain setChain(Chain c)

Set the chain value, provided it hasn't already been set.

Returns:

the chain value.

Throws:

java.lang.IllegalStateException - when setChain() has already been called without an intervening clearChain() call.

clearChain

public void clearChain()

Clear the chain value; used when we reuse the elementes in a stream.

findex

public int findex()

Get the findex value. Should be as fast as if the slot were accessible.

Returns:

the findex value.

chain

public Chain chain()

Get the chain value. Should be as fast as if the slot were accessible.

Returns:

the chain value.

dimension

public abstract int dimension()

Returns the dimension of self.

Returns:

int, the dimension (i.e., 1 more than the number of vertices) of the simplex.

copy

public abstract Simplex copy()

Make a "blank" copy of the Simplex -- equivalent to getSimplex(this.vertices()).

Returns:

the copied instance.

vertices

public abstract int[] vertices()

Returns the indices of self as an array.

Returns:

an int[] of indices into the LandmarkIndexArray.

vertices

public abstract int[] vertices(int[] verts)

Returns the indices of self as an array.

Parameters:

verts - An int[] in which to store the vertices -- it must be at at least as long as the number of vertices.

Returns:

an int[] of indices into the LandmarkIndexArray.

subset

public boolean subset(Simplex s)

Is this a subset of s?

Parameters:

s - The simplex to which to compare this.

Returns:

True if this is a subset of s, else false.

subset

public boolean subset(Simplex s,
             int[] v,
             int[] sv)

Is this a subset of s?

Parameters:

s - The simplex to which to compare this.

v - An int[] in which to put the vertices of this -- must be at least as long as the number of vertices.

sv - An int[] in which to put the vertices of s -- must be at least as long as the number of vertices of s.

Returns:

True if this is a subset of s, else false.

hashCode

public int hashCode()

Overrides Object hashcode.

Overrides:

hashCode in class java.lang.Object

Returns:

CRC hash of the vertex set.

equals

public boolean equals(java.lang.Object obj)

Overrides Object equals.

This test is equivalent to an equality test on the vertices.

Overrides:

equals in class java.lang.Object

Parameters:

obj - object to compare.

Returns:

true or false, depending on whether or not the Simplex is = to obj.

compareTo

public int compareTo(Simplex s)

Implements Comparable interface.

This test is equivalent to lexicographic comparison of the vertex arrays.

Specified by:

compareTo in interface java.lang.Comparable<Simplex>

Parameters:

s - Simplex to compare.

Returns:

negative, 0, or positive, if this <, =, resp. > than s.

getSimplex

public static Simplex getSimplex(int[] vertices)

Get the simplex for a given set of vertices.

Parameters:

vertices - The vertex set.

Returns:

A simplex for that set of vertices.

getSimplex

public static Simplex getSimplex(int[] vertices,
                 int findex)

Get the simplex for a given set of vertices, including setting findex.

Parameters:

vertices - The vertex set.

findex - The Filtration index.

Returns:

A simplex for that set of vertices.

getSimplexPresorted

public static Simplex getSimplexPresorted(int[] vertices)

Get the simplex for an already verified array of vertices.

Parameters:

vertices - The vertex set.

Returns:

A simplex for that set of vertices.

getSimplexPresorted

public static Simplex getSimplexPresorted(int[] vertices,
                          int findex)

Get the simplex for an already verified array of vertices, including setting findex.

Parameters:

vertices - The vertex set.

findex - The Filtration index.

Returns:

A simplex for that set of vertices.

makeEdge

public static Simplex makeEdge(int v1,
               int v2,
               int findex)

Get the edge for a pair of vertices.

Parameters:

v1 - One vertex.

v2 - Another vertex.

Returns:

A 1-simplex, or edge.

makePoint

public static Simplex makePoint(int v,
                int findex)

Turn a vertex into a 0-simplex.

Parameters:

v - The vertex.

Returns:

A 0-simplex, or point.

addVertex

public Simplex addVertex(int v)

Add a vertex to a simplex.

I can't recall why this method exists, so the implementation is the easiest one I can think of.

Parameters:

v - A vertex to adjoin.

Returns:

The new simplex.

addVertex

public Simplex addVertex(int v,
                int f)

Add a vertex to a simplex, and set the findex.

Parameters:

v - A vertex to adjoin.

f - The new findex.

Returns:

The new simplex.

toString

public java.lang.String toString()

Represent a Simplex as a String.

Overrides:

toString in class java.lang.Object

Returns:

A string that describes a Simplex.

vertex_sort

public static int[] vertex_sort(int[] vertices)

Sort a set of vertices into increasing order, as needed for some Simplex operations. We use the bubblesort algorithm, since that is fastest for very short arrays, which is what we have in practice.

Parameters:

vertices - The vertex set.

Returns:

The sorted vertices.

dist_sort

public static double[] dist_sort(double[] distances)

Sort an array of double into increasing order, as needed for some Simplex operations. We use the bubblesort algorithm, since that is fastest for very short arrays, which is what we have in practice.

Parameters:

distances - An array of double to be sorted..

Returns:

The sorted array.

simplex_reverse_sort

public static int[] simplex_reverse_sort(int[] vertices)

Sort a set of vertices into decreasing order, as needed for some Simplex operations. We use the bubblesort algorithm, since that is fastest for very short arrays, which is what we have in practice.

Parameters:

vertices - The vertex set.

Returns:

The reverse sorted vertices.

persistence_sort

public static void persistence_sort(Simplex[] sarray)

Sort, in place and using "persistence order", an array of simplices. Null entries will be pushed to the end of the array -- that is, null is considered to be larger than any non-null Simplex.

boundaryArray

public abstract Simplex[] boundaryArray()

Return an array of simplices that describes the boundary. The sign associated with a face is -1 to the power of the index of that face in the array. There is a static class method in Chain that will convert an array of this type into a Chain for use in homology calculations.

Returns:

[face0, face1, ...]

boundary

public Chain boundary(int p)

Return the boundary of a simplex as a chain over a given characteristic.

Parameters:

p - The characteristic

Returns:

A chain representing the boundary.