edu.stanford.math.plex4.streams.impl

Class LazyWitnessStream<T>

java.lang.Object

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

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

edu.stanford.math.plex4.streams.impl.LazyWitnessStream<T>

Type Parameters:

T - the type of the underlying metric space

All Implemented Interfaces:

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

public class LazyWitnessStream<T>
extends FlagComplexStream

This class implements the lazy witness complex described in the paper "Topological estimation using witness complexes", by Vin de Silva and Gunnar Carlsson. The details of the construction are described in this paper. Note that a lazy witness complex is fully described by its 1-skeleton, therefore we simply derive from the FlagComplexStream class.

Author:

Andrew Tausz

Field Summary

Fields

Modifier and Type	Field and Description
protected double[][]	D
protected double	epsilon
protected int	L
protected LandmarkSelector<T>	landmarkSelector This is the selection of landmark points
protected double[]	m
protected double	maxDistance The maximum distance allowed between two connected vertices.
protected AbstractSearchableMetricSpace<T>	metricSpace This is the metric space upon which the stream is built from.
protected int	N
protected int	nu This is the nu value described in the paper.
protected boolean	plex3Compatible

Fields inherited from class edu.stanford.math.plex4.streams.impl.FlagComplexStream

converter, indices, maxAllowableDimension, neighborhoodGraph

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

storageStructure

Constructor Summary

Constructors

Constructor and Description
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double[] filtrationValues)
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double[] filtrationValues, int nu)
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double[] filtrationValues, int[] indices)
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double[] filtrationValues, int nu, int[] indices)
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double maxDistance, int numDivisions)
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double maxDistance, int[] indices)
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double maxDistance, int nu, int numDivisions) Constructor which initializes the complex with a metric space.
LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace, LandmarkSelector<T> landmarkSelector, int maxDimension, double maxDistance, int nu, int[] indices)

Method Summary

Methods

Modifier and Type	Method and Description
protected UndirectedWeightedListGraph	constructEdges() This function implements the construction of the 1-skeleton.
protected static boolean	contains(int[] array, int value)
protected gnu.trove.TIntHashSet	getAllWitnesses(double e_ij, int... externalIndices)
java.util.List<Simplex>	getAssociatedSimplices(int witness) This function returns the list of simplices such that they have the given point as their witness.
static int	getDefaultNuValue()
protected edu.stanford.math.primitivelib.autogen.pair.IntDoublePair	getWitnessAndDistance(int... landmarkIndices)
protected boolean	isWitness(int x, int[] externalIndices)
protected boolean	isWitness(int x, Simplex simplex)
void	setPlex3Compatbility(boolean value)
protected void	updateWitnessInformation(int n_star, double e_ij, int... externalIndices)
protected void	updateWitnessInformationInternalIndices(int n_star, double e_ij, int... internalIndices)

Methods inherited from class edu.stanford.math.plex4.streams.impl.FlagComplexStream

addCofaces, constructComplex, getConverter, getFiltrationValue, getNeighborhoodGraph, incrementalExpansion, transform

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

metricSpace

protected final AbstractSearchableMetricSpace<T> metricSpace

This is the metric space upon which the stream is built from.

landmarkSelector

protected final LandmarkSelector<T> landmarkSelector

This is the selection of landmark points

nu

protected final int nu

This is the nu value described in the paper. Note that we use the default value of 2.

maxDistance

protected final double maxDistance

The maximum distance allowed between two connected vertices.

D

protected double[][] D

m

protected double[] m

N

protected final int N

L

protected final int L

epsilon

protected final double epsilon

See Also:

Constant Field Values

plex3Compatible

protected boolean plex3Compatible

Constructor Detail

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double maxDistance,
                 int nu,
                 int numDivisions)

Constructor which initializes the complex with a metric space.

Parameters:

metricSpace - the metric space to use in the construction of the complex

maxDistance - the maximum allowable distance

maxDimension - the maximum dimension of the complex

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double maxDistance,
                 int numDivisions)

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double maxDistance,
                 int nu,
                 int[] indices)

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double maxDistance,
                 int[] indices)

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double[] filtrationValues,
                 int nu)

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double[] filtrationValues)

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double[] filtrationValues,
                 int nu,
                 int[] indices)

LazyWitnessStream

public LazyWitnessStream(AbstractSearchableMetricSpace<T> metricSpace,
                 LandmarkSelector<T> landmarkSelector,
                 int maxDimension,
                 double[] filtrationValues,
                 int[] indices)

Method Detail

setPlex3Compatbility

public void setPlex3Compatbility(boolean value)

getDefaultNuValue

public static int getDefaultNuValue()

getAssociatedSimplices

public java.util.List<Simplex> getAssociatedSimplices(int witness)

This function returns the list of simplices such that they have the given point as their witness. If there are no such points, this function returns null;

Parameters:

witness - the witness point

Returns:

a list of simplices with the given point as their witness

constructEdges

protected UndirectedWeightedListGraph constructEdges()

Description copied from class: FlagComplexStream

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.

Specified by:

constructEdges in class FlagComplexStream

Returns:

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

getWitnessAndDistance

protected edu.stanford.math.primitivelib.autogen.pair.IntDoublePair getWitnessAndDistance(int... landmarkIndices)

contains

protected static boolean contains(int[] array,
               int value)

updateWitnessInformationInternalIndices

protected void updateWitnessInformationInternalIndices(int n_star,
                                           double e_ij,
                                           int... internalIndices)

updateWitnessInformation

protected void updateWitnessInformation(int n_star,
                            double e_ij,
                            int... externalIndices)

isWitness

protected boolean isWitness(int x,
                Simplex simplex)

isWitness

protected boolean isWitness(int x,
                int[] externalIndices)

getAllWitnesses

protected gnu.trove.TIntHashSet getAllWitnesses(double e_ij,
                                    int... externalIndices)