edu.stanford.math.plex4.streams.impl

Class FlagComplexStream

java.lang.Object

edu.stanford.math.plex4.streams.interfaces.PrimitiveStream<Simplex>

edu.stanford.math.plex4.streams.impl.FlagComplexStream

All Implemented Interfaces:

AbstractFilteredStream<Simplex>, java.lang.Iterable<Simplex>

Direct Known Subclasses:

FlexibleVietorisRipsStream, LazyWitnessStream

public abstract class FlagComplexStream
extends PrimitiveStream<Simplex>

This class implements a simplex stream with the property that given its 1-skeleton, its higher skeletons are maximal in the following sense. A k-simplex [v_0, ..., v_k] is a member of the complex iff all of its edges [v_i, v_j] are in the complex.

This class is abstract in that it does not provide a mechanism for constructing the 1-skeleton, and only constructs the higher order skeletons inductively. The reason is that there are different choices for definitions of the 1-skeletons, the main ones being the lazy witness complex, the Vietoris-Rips complex, and the clique complex. Thus a child class must provide the implementation of the 1-skeleton.

Also note that the FlagComplexStream construction can be used with any finite metric space. For information on the implementation, consult the paper "Fast Construction of the Vietoris-Rips Complex", by Afra Zomorodian. This implementation uses the incremental algorithm described in the above paper.

Author:

Andrew Tausz

Field Summary

Fields

Modifier and Type	Field and Description
protected FiltrationConverter	converter This converts between filtration indices and values
protected int[]	indices
protected int	maxAllowableDimension The maximum allowable dimension of the complex.
protected UndirectedWeightedListGraph	neighborhoodGraph Stores the neighborhood graph.

Fields inherited from class edu.stanford.math.plex4.streams.interfaces.PrimitiveStream

storageStructure

Constructor Summary

Constructors

Constructor and Description
FlagComplexStream(int maxAllowableDimension, FiltrationConverter converter) This constructor initializes the class.
FlagComplexStream(int maxAllowableDimension, FiltrationConverter converter, int[] indices)
FlagComplexStream(int maxAllowableDimension, FiltrationConverter converter, StreamStorageStructure<Simplex> storageStructure) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	addCofaces(UndirectedWeightedListGraph G, int k, Simplex tau, gnu.trove.TIntHashSet N, double filtrationValue) This function inductively adds all of the cofaces of the simplex tau to the complex.
protected void	constructComplex() This abstract function performs the construction of the filtered chain complex.
protected abstract UndirectedWeightedListGraph	constructEdges() This function implements the construction of the 1-skeleton.
FiltrationConverter	getConverter() This function returns the FiltrationConverter object used by the complex.
double	getFiltrationValue(Simplex simplex)
UndirectedWeightedListGraph	getNeighborhoodGraph() This returns the neighborhood graph (equivalent to the 1-skeleton) of the complex.
protected void	incrementalExpansion(UndirectedWeightedListGraph G, int k) This function performs the incremental expansion of the complex.
<G> PersistenceInvariantDescriptor<Interval<java.lang.Double>,G>	transform(PersistenceInvariantDescriptor<Interval<java.lang.Integer>,G> barcodeCollection) This function transforms the given collection of filtration index barcodes into filtration value barcodes.

Methods inherited from class edu.stanford.math.plex4.streams.interfaces.PrimitiveStream

containsElement, finalizeStream, getBasisComparator, getBoundary, getBoundaryCoefficients, getDimension, getFiltrationIndex, getMaximumFiltrationIndex, getMinimumFiltrationIndex, getSize, isFinalized, iterator, validate, validateVerbose

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

maxAllowableDimension

protected final int maxAllowableDimension

The maximum allowable dimension of the complex.

neighborhoodGraph

protected UndirectedWeightedListGraph neighborhoodGraph

Stores the neighborhood graph.

converter

protected FiltrationConverter converter

This converts between filtration indices and values

indices

protected int[] indices

Constructor Detail

FlagComplexStream

public FlagComplexStream(int maxAllowableDimension,
                 FiltrationConverter converter)

This constructor initializes the class.

Parameters:

maxAllowableDimension - the maximum dimension of the simplicial complex

converter - a FiltrationConverter for translating between filtration indices and values

FlagComplexStream

public FlagComplexStream(int maxAllowableDimension,
                 FiltrationConverter converter,
                 int[] indices)

FlagComplexStream

public FlagComplexStream(int maxAllowableDimension,
                 FiltrationConverter converter,
                 StreamStorageStructure<Simplex> storageStructure)

Constructor.

Parameters:

maxAllowableDimension - the maximum dimension of the simplicial complex

converter - a FiltrationConverter for translating between filtration indices and values

storageStructure - the StreamStorageStructure to use

Method Detail

constructEdges

protected abstract UndirectedWeightedListGraph constructEdges()

This function implements the construction of the 1-skeleton. It must output a list containing pairs of filtration values and 1-simplices. The filtration value of an edge is the threshold value at which the edge appears in the filtered sequence of simplicial complexes.

Returns:

the 1-skeleton of the complex along with its filtration values

getNeighborhoodGraph

public UndirectedWeightedListGraph getNeighborhoodGraph()

This returns the neighborhood graph (equivalent to the 1-skeleton) of the complex.

Returns:

the neighborhood graph

getFiltrationValue

public double getFiltrationValue(Simplex simplex)

getConverter

public FiltrationConverter getConverter()

This function returns the FiltrationConverter object used by the complex.

Returns:

the FiltrationConverter used by the complex

transform

public <G> PersistenceInvariantDescriptor<Interval<java.lang.Double>,G> transform(PersistenceInvariantDescriptor<Interval<java.lang.Integer>,G> barcodeCollection)

This function transforms the given collection of filtration index barcodes into filtration value barcodes.

Type Parameters:

G -

Parameters:

barcodeCollection - the set of filtration index barcodes

Returns:

the barcodes transformed into filtration value form

constructComplex

protected void constructComplex()

Description copied from class: PrimitiveStream

This abstract function performs the construction of the filtered chain complex. For example, this might construct the complex from a metric space via a Vietoris-Rips or witness construction.

Specified by:

constructComplex in class PrimitiveStream<Simplex>

incrementalExpansion

protected void incrementalExpansion(UndirectedWeightedListGraph G,
                        int k)

This function performs the incremental expansion of the complex.

Parameters:

G - the neighborhood graph

k - the maximum dimension

addCofaces

protected void addCofaces(UndirectedWeightedListGraph G,
              int k,
              Simplex tau,
              gnu.trove.TIntHashSet N,
              double filtrationValue)

This function inductively adds all of the cofaces of the simplex tau to the complex. For more information about this algorithm, consult the paper "Fast Construction of the Vietoris-Rips Complex" by Afra Zomorodian.

Parameters:

G - the neighborhood graph

k - the maximum allowable dimension

tau - the current simplex to add

N - the lower neighbors to investigate

filtrationValue - the filtration value of the current simplex, tau