Math.Topology.CubeCmplx.DirCubeCmplx

Finite directed cubical complexes and associated algorithms for creating and transforming them.

Vertices

type T = Int8

A generic notation for coordinate values.

data Vertex

A vertex with lexicographic ordering.

Instances

Eq Vertex

Ord Vertex

Show Vertex

Arbitrary Vertex

NFData Vertex

Hashable Vertex

vertex :: [T] -> Maybe Vertex

Safe constructor for vertices.

coords :: Vertex -> Vector T

vertexUnsafe :: [T] -> Vertex

Unsafe constructor for vertices.

vertexVectorUnsafe :: Vector T -> Vertex

Unsafe constructor for vertices from vectors.

vertexToList :: Vertex -> [T]

Fetch coordinates for a vertex.

vertexPtWise :: (T -> T -> T) -> Vertex -> Vertex -> Vertex

vAdd :: Vertex -> Vertex -> Vertex

Add two vertices coordinate-wise.

vSub :: Vertex -> Vertex -> Vertex

Subtract two vertices coordinate-wise.

vSubUnsafe :: Vertex -> Vertex -> Vertex

Subtract two vertices coordinate-wise without bounds checking.

vMin :: Vertex -> Vertex -> Vertex

Coordinate-wise minimum.

vMax :: Vertex -> Vertex -> Vertex

Coordinate-wise maximum.

vGT :: Vertex -> Vertex -> Bool

Test whether vertex is greater than another in cubical partial ordering.

vLT :: Vertex -> Vertex -> Bool

Test whether vertex is less than another in cubical partial ordering.

vDim :: Vertex -> Int

Fetch ambient dimension of a vertex.

Vertex spans

data VertSpan

A cubical vertex span.

Instances

Eq VertSpan

Ord VertSpan

Show VertSpan

Arbitrary VertSpan

NFData VertSpan

vertSpan :: Vertex -> Vertex -> Maybe VertSpan

Safe constructor for vertex spans. Sanity checks for matching ambient coordinate systems.

vsFst :: VertSpan -> Vertex

vsSnd :: VertSpan -> Vertex

vsUnsafe :: Vertex -> Vertex -> VertSpan

Unsafe constructor for vertex spans.

vsVert :: Vertex -> VertSpan

View a vertex as a 0-dimensional vertex span.

vsFstList :: VertSpan -> [T]

Get coordinates for lower vertex in coordinate span.

vsSndList :: VertSpan -> [T]

Get coordinates for upper vertex in coordinate span.

vsCoords :: [T] -> [T] -> Maybe VertSpan

Safe constructor for vertex spans from coordinates.

vsCoordsUnsafe :: [T] -> [T] -> VertSpan

Unsafe constructor for vertex spans from coordinates.

vsDim :: VertSpan -> Int

Given a vertex span, determine the corresponding cubical dimension.

vsIsCell :: VertSpan -> Bool

Test whether a vertex span is a cubical cell.

vsFatten :: VertSpan -> VertSpan

Given a vertex span, extend it by one more unit in every direction in which it already extends.

vsCornerPairs :: VertSpan -> HashSet (CubeCell, Vertex)

Given a vertex span, efficiently determine all pairs of (cell,vertex) where the vertices are corner vertices of the span and the cells are the unique top-cells containing them.

vsCornerVerts :: VertSpan -> HashSet Vertex

Given a vertex span, efficiently determine its corner vertices.

vsBdry :: VertSpan -> [VertSpan]

Given a coordinate span, list all coordinate spans of its boundary.

Cells

data CubeCell

A cubical cell.

Instances

Eq CubeCell

Ord CubeCell

Lexicographically ordered by endpoints.

Show CubeCell

Show endpoints.

Arbitrary CubeCell

Random cubical cells.

NFData CubeCell

Hashable CubeCell

For storing cubical cells in unordered containers.

minVert :: CubeCell -> Vertex

Get the minimum vertex for a cubical cell.

maxVert :: CubeCell -> Vertex

Get the maximum vertex for a cubical cell.

cell :: [T] -> [T] -> Maybe CubeCell

Safe constructor for cubical cells from coordinates.

cellUnsafe :: [T] -> [T] -> CubeCell

Unsafe constructor for cubical cells from coordinates.

cellDim :: CubeCell -> Int

Get dimension of a cell.

cellVertsUnsafe :: Vertex -> Vertex -> CubeCell

Unsafe constructor for cubical cells from vertices.

cellVerts :: Vertex -> Vertex -> Maybe CubeCell

Safe constructor for cubical cells from vertices.

spanTopCells :: VertSpan -> [CubeCell]

Given a coordinate span, list its top-dimensional cubical cells.

vertToCell :: Vertex -> CubeCell

Treat a vertex as a cell.

inSpan :: CubeCell -> VertSpan -> Bool

Test whether a cubical cell belongs to a given vertex span.

isTopCell :: CubeCell -> CubeCmplx -> Bool

Test whether a cubical cell would be a top-cell if added to a complex

vInSpan :: Vertex -> VertSpan -> Bool

Test whether a vertex belongs to a given vertex span.

inBdry :: CubeCell -> VertSpan -> Bool

Test if a cubical cell is in the boundary of a cubical coordinate span. See also vsBdry and spanBdryCells

spanBdryCells :: VertSpan -> [[CubeCell]]

Given a coordinate span, provide a list of top-cells in each face.

Substructures

nCubes :: [CubeCell]

List of all possible generic n-cubes, presented as cells (memoized).

nCubeVerts :: Int -> [CubeCell]

Vertices of generic n-cube, as subcells (memoized).

nCubeCells :: Int -> [CubeCell]

Subcells of a generic n-cube (memoized).

nCubeProperCells :: Int -> [CubeCell]

Proper subcells of a generic n-cube (mostly memoized).

nCubeBdry :: Int -> [CubeCell]

List of cells in boundary of a generic n-cube (memoized).

nCubeKSkels :: Int -> Int -> [CubeCell]

List top-cells in k-skeleta of generic n-cube (memoized).

verts :: CubeCell -> [Vertex]

Given a (nongeneric) cubical cell, list its vertices.

subCells :: CubeCell -> [CubeCell]

Given a (nongeneric) cubical cell, get all cubical subcells.

properSubCells :: CubeCell -> [CubeCell]

Given a (nongeneric) cubical cell, get all proper cubical subcells.

bdry :: CubeCell -> [CubeCell]

Given a (nongeneric) cubical cell of dim n in ambient dim n, get its boundary.

kSkel :: Int -> CubeCell -> [CubeCell]

Given a (nongeneric) cubical cell, get top-cells of its k-skeleton.

isSubCell :: CubeCell -> CubeCell -> Bool

Test if the former cubical cell is a subcell of the latter.

isPropSubCell :: CubeCell -> CubeCell -> Bool

Test if the former cubical cell is a proper subcell of the latter.

opFaceUnsafe :: CubeCell -> CubeCell -> CubeCell

Given a face f in some n-cube, get its opposite face (memoized).

Translation

genToNonGen :: CubeCell -> CubeCell -> CubeCell

Given a (nongeneric) cell c and a generic cell g representing a subcell of a generic cell of dimension dim c, return the translation of g into the nongeneric coordinates of c.

nonGenToGen :: CubeCell -> CubeCell -> CubeCell

Given a subcell s of a (nongeneric) cell c, express s as a subcell of a generic cell of the same dimension as c.

Directed Cubical Complexes

data CubeCmplx

A cubical complex consists of a set of top-cells.

Instances

Eq CubeCmplx

Show CubeCmplx

Arbitrary CubeCmplx

A random cubical complex will be a vertex span with a random subset of top-cells removed. Not ideal since every cell will have the same dimension.

NFData CubeCmplx

cells :: CubeCmplx -> HashSet CubeCell

cmplxEmpty :: CubeCmplx

An empty complex.

cmplxNull :: CubeCmplx -> Bool

Detect if complex is empty.

cmplxSize :: CubeCmplx -> Int

Get the size of a cubical complex.

cmplxApply :: CubeCmplx -> (CubeCell -> HashSet CubeCell) -> CubeCmplx

Given a function producing a set of cubical cells from any cubical cell, apply it to a cubical complex to yield a new complex.

cmplxVertOp :: CubeCmplx -> Vertex -> (Vertex -> Vertex -> Vertex) -> CubeCmplx

Given a complex and a vertex of the same ambient dimension, translate every cell of the complex by the vertex via the given operation. Typical operation is to add (1,...,1) to force nonzero coordinates without affecting the topology.

vsCmplx :: VertSpan -> CubeCmplx

Basic means of constructing cubical complexes via vertex spans.

cmplxDelCell :: CubeCmplx -> CubeCell -> CubeCmplx

Given a single cell to delete from a complex, delete it if present.

cmplxDelCells :: CubeCmplx -> HashSet CubeCell -> CubeCmplx

Given a set of cells to delete from a complex, delete them if present.

cmplxDelVsInt :: CubeCmplx -> VertSpan -> CubeCmplx

Given a vertex span and a complex, delete all top-cells belonging to the span and replace them with the boundaries of these top-cells that belong to the span's boundary. This punches a hole in the complex.

cmplxAddCells :: CubeCmplx -> HashSet CubeCell -> CubeCmplx

Given a set of cells to insert into a complex, insert them all.

cmplxUnions :: [CubeCmplx] -> CubeCmplx

Union a list of complexes.

cmplxFilter :: (CubeCell -> Bool) -> CubeCmplx -> CubeCmplx

Filter the top-cells of a complex on some predicate.

cmplxHullUnsafe :: CubeCmplx -> VertSpan

Given a non-empty complex, determine the minimal vertex span containing it. The resulting span need not have the same dimension as the ambient space.

cmplxFilterSpan :: CubeCmplx -> VertSpan -> CubeCmplx

Given a complex cx and a vertex span vs, filter the complex down to the subcomplex of all top-cells of cx contained in vs.

cmplxFilterSpans :: CubeCmplx -> [VertSpan] -> [(CubeCmplx, VertSpan)]

Given a complex and a list of vertex spans, determine the list of subcomplexes of top-cells supported on these spans, paired up with the spans so that the original boundaries are known.

cellNhd :: CubeCmplx -> CubeCell -> CubeCmplx

Given a cell c in a cubical complex, get a subcomplex that includes all all top-cells that could be adjacent to c (including c). Handy for reducing search problems.

Example complexes

swissFlag :: (CubeCmplx, [VertSpan])

Standard example of finite directed cubical complex: two classes of paths expected in path category.

sqPairFwd :: (CubeCmplx, [VertSpan])

Standard example: four classes of paths expected in path category.

sqPairBack :: (CubeCmplx, [VertSpan])

Standard example: three classes of paths expected in path category.

torus3d :: (CubeCmplx, [VertSpan])

Standard example: two classes of paths expected in path category.

genusTwo3d :: (CubeCmplx, [VertSpan])

Standard example: four classes of paths expected in path category.

Utilities

lazyProd :: [[a]] -> [[a]]

Space-efficient cartesian product of list of finite domains