comptop

package module
v0.2.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 8, 2021 License: MIT Imports: 8 Imported by: 0

README

go-comptop GitHub Go Report Card

A computational topology package for gophers.

Features

Simplices; simplicial complexes; simplicial chains; chain, cycle, boundary and homology groups; sets of simplices; methods for computing boundaries, Euler characteristics, Euler integrals, and Betti numbers, and more (with even more to come)!

Contributing

Contributions are welcome!

Examples:

Computing paths around holes in a network (computing a basis for the first homology group):
Scenario:

Suppose we have a torus interconnect network topology.

Problem:

We want to find a path around both holes in the network.

Solution:

We can compute a basis for the first homology group of the network.

package main

import (
        "fmt"
        "github.com/raphaelreyna/go-comptop"
        "github.com/raphaelreyna/go-comptop/spaces"
)

func main() {
        c := &comptop.Complex{}
        c.NewSimplices(spaces.Torus...)

        fmt.Println(c.ChainGroup(1).HomologyGroup().MinimalBasis())
}

We get the following output which correctly gives two cycles (chains), one around each hole:

[
	Chain{
		Simplex{"dim": 1, "index": 0, "base": [0 1]},
		Simplex{"dim": 1, "index": 5, "base": [1 2]},
		Simplex{"dim": 1, "index": 9, "base": [0 2]},
	},
	Chain{
		Simplex{"dim": 1, "index": 1, "base": [0 3]},
		Simplex{"dim": 1, "index": 12, "base": [3 6]},
		Simplex{"dim": 1, "index": 21, "base": [0 6]},
	},
]
Counting requests to load-balanced services with poor observability:
Scenario:

Suppose we have a backend with the network topology shown below.

  • Services 0, 1, 2 are load balanced and accessed by 3.
  • Services 6 and 7 are load balanced and accessed by 5.
  • Services 8 and 9 are load balanced and accessed by 10.

Let's assume we are using a load balancing scheme where requests are multicast to some random number of randomly selected instances.

Services 4 and 10 are the only public facing services. Services forward client API keys with requests to internal services.

The services in red (0, 1, 2, 5, 6, 7, 9) are the only ones logging API keys, but without timestamps. Logs are rotated daily.

We can query the services in red for the number of times it logged a clients API key today.

Problem:

Suppose that client Alice made 3 requests today:

  • A request to 4 which sent a request to 3, which load balanced to 0 and 1.
  • A request to 10 which load balanced to 9 then 10.
  • A request to 4 which load balanced to 3, which load balanced to 0, 1 and 2.

We don't know that Alice made 3 requests or the path thos requests took. All we can do is query the services and get back the results (a heightmap) shown below.

How many requests did client Alice make today?

Solution:

We can integrate the height map over the network with respect to the Euler characteristic. This gives us an estimate on the number of requests Alice made.

package main

import (
  "fmt"
  "github.com/raphaelreyna/go-comptop"
)

func main() {
	c := &comptop.Complex{}
  
	loggingNetwork := []comptop.Base{
		{0, 1, 2},
		{5, 6, 7},
		{5, 9},
	}
	c.NewSimplices(loggingNetwork...)

	heightMap := map[comptop.Index]int{
		0: 2, 1: 2, 2: 1,
		5: 1, 6: 0, 7: 0,
		9: 1,
	}

	f := comptop.CF(func(idx comptop.Index) int {
		return heightMap[idx]
	})

	fmt.Println(c.EulerIntegral(0, 2, f))
}

We correctly get 3 as the answer.

(See work by Y. Baryshnikov and R.Ghrist 'Target Enumeration via Euler Characteristic Integrals' for more info / theory)

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Base 

type Base []Index

Base is a collection of indices for 0-dimensional simplices.

func (Base) Len added in v0.2.1 

func (b Base) Len() int

func (Base) Less added in v0.2.1 

func (b Base) Less(i, j int) bool

func (Base) Swap added in v0.2.1 

func (b Base) Swap(i, j int)

type BoundaryGroup 

type BoundaryGroup struct {
	// contains filtered or unexported fields
}

func (*BoundaryGroup) Basis 

func (bg *BoundaryGroup) Basis() []*Chain

func (*BoundaryGroup) ChainGroup 

func (bg *BoundaryGroup) ChainGroup() *ChainGroup

func (*BoundaryGroup) Rank 

func (bg *BoundaryGroup) Rank() int

type BoundaryMap 

type BoundaryMap struct {
	// contains filtered or unexported fields
}

BoundaryMap is the bonudary map between chain groups of dimensions p and p-1.

func (*BoundaryMap) BoundaryMatrix 

func (bm *BoundaryMap) BoundaryMatrix() mat.Matrix

BoundaryMatrix returns the matrix representation of the boundary map.

func (*BoundaryMap) BpLow 

func (bm *BoundaryMap) BpLow() int

BpLow returns the number of non-zero rows in the Smith normal form of the boundary matrix. The value returned by BpLow coincides with the rank of the image of the boundary matrix, which is the same as the rank of the boundary group B_{p-1} < Z_{p-1} < C_{p-1}.

func (*BoundaryMap) SmithNormal 

func (bm *BoundaryMap) SmithNormal() mat.Matrix

SmithNormal returns the Smith normal form of the boundary matrix.

func (*BoundaryMap) SmithNormalDiagonalLength 

func (bm *BoundaryMap) SmithNormalDiagonalLength() int

SmithNormalDiagonalLength returns the number of non-zero elements on the diagonal of the Smith normal form of the boundary matrix.

func (*BoundaryMap) U 

func (bm *BoundaryMap) U() mat.Matrix

U returns the the left-side matrix in the Smith normal factorization of the boundaty matrix.

func (*BoundaryMap) UInverse 

func (bm *BoundaryMap) UInverse() mat.Matrix

UInverse returns the inverse of the left-side matrix in the Smith normal factorization of the boundaty matrix.

func (*BoundaryMap) V 

func (bm *BoundaryMap) V() mat.Matrix

V returns the the right-side matrix in the Smith normal factorization of the boundaty matrix.

func (*BoundaryMap) Zp 

func (bm *BoundaryMap) Zp() int

Zp returns the number of 0-columns in the Smith normal form of the boundary matrix. The value returned by Zp coincides with the rank of the kernel of the boundary matrix, which is the same as the rank of the cycle group Z_p < C_p.

type CF 

type CF func(Index) int

CF represents the group of constructible functions on the vertex set of a complex.

More info: https://en.wikipedia.org/wiki/Constructible_function

type Chain 

type Chain struct {
	// contains filtered or unexported fields
}

Chain is an element of a ChainGroup. Chains are formal sums over the p-dimensional Simplices of a Complex with coefficients in Z_2 = Z/2Z. This means that adding a Chain to itself results in an empty Chain (the zero element of the ChainGroup).

More info: https://en.wikipedia.org/wiki/Simplicial_homology#Chains

func (*Chain) Add 

func (c *Chain) Add(a *Chain) *Chain

Add returns the results of adding Chain c to Chain a. Since Chain is an element of a boolean group, if c == a then the resulting Chain is empty.

func (*Chain) AddSimplex 

func (c *Chain) AddSimplex(s *Simplex) *Chain

AddSimplex is a convenience method for adding the Chain containing only the Simplex s to the Chain c.

func (*Chain) Boundary 

func (c *Chain) Boundary() *Chain

Boundary is a group homomorphism from a p-dimensional ChainGroup to a (p-1)-dimensional ChainGroup. In particular, Boundary returns the Chain of simplices that make up the boundary/faces of c. For example: If c represents an edge, then the boundary is the chain consisting of the 2 vertices that it connects; if c is a filled in triangle, the boundary is the chain of the 3 edges that make up the triangle.

More info: https://en.wikipedia.org/wiki/Simplicial_homology#Boundaries_and_cycles

func (*Chain) ChainGroup 

func (c *Chain) ChainGroup() *ChainGroup

func (*Chain) Dim 

func (c *Chain) Dim() Dim

Dim is the dimension od the simplices in the chain. (all simplices in a chain have the same dimension)

func (*Chain) Equals 

func (c *Chain) Equals(a *Chain) bool

Equals returns true is c is equal to a.

func (*Chain) EulerChar 

func (c *Chain) EulerChar() int

EulerChar returns the Euler characteristic of c. For chains, this value coincides with the number of connected components in the chain.

More info: https://en.wikipedia.org/wiki/Euler_characteristic

func (*Chain) Intersection 

func (c *Chain) Intersection(a *Chain) *Chain

Intersection returns the intersection of chains c and a.

func (*Chain) IsZero 

func (c *Chain) IsZero() bool

func (*Chain) Len 

func (c *Chain) Len() int

Len is used to satisfy the sort.Interface interface

func (*Chain) Less 

func (c *Chain) Less(i, j int) bool

Less is used to satisfy the sort.Interface interface

func (*Chain) Simplices 

func (c *Chain) Simplices() []*Simplex

Simplices returns a copy of the simplices that make up c.

func (*Chain) String 

func (c *Chain) String() string

func (*Chain) Swap 

func (c *Chain) Swap(i, j int)

Swap is used to satisfy the sort.Interface interface

func (*Chain) Vector 

func (c *Chain) Vector() Vector

Vector returns the vector representation of c. A Chain c is represented as a Vector v by assigning v_i = 1 if c contains the i^th simplex in the basis of the ChainGroup; v_i = 0 otherwise.

type ChainGroup 

type ChainGroup struct {
	// contains filtered or unexported fields
}

ChainGroup represents a group in the chain complex of a Complex. The elements of a chain group are the chains in a Complex c, consisting of p-dimensional simplices in c. In other words, a ChainGroup represents all possible combinations of the p-dimensional simplices of a Complex. Since ChainGroup represents a group, chains witihn a ChainGroup can be added together to obtain a new Chain in the ChainGroup. Every ChainGroup is a boolean group which means that the sum of Chain with itself is an empty Chain.

More info: https://en.wikipedia.org/wiki/Chain_complex

func (*ChainGroup) Add 

func (cg *ChainGroup) Add(a, b *Simplex) *Chain

Add returns the Chain which is a result of adding the Chain containing only a and the Chain containing only b.

func (*ChainGroup) BoundaryGroup 

func (cg *ChainGroup) BoundaryGroup() *BoundaryGroup

BoundaryGroup B_p is a subgroup of the CycleGroup Z_p of the same dimension p. A boundary group B_p consists of all cycles in the cycle group Z_p which are the boundary of a chain in C_{p+1}.

func (*ChainGroup) BoundaryMap 

func (cg *ChainGroup) BoundaryMap() *BoundaryMap

func (*ChainGroup) ChainFromVector 

func (cg *ChainGroup) ChainFromVector(v Vector) *Chain

ChainFromVector returns the Chain represented by v.

func (*ChainGroup) CycleGroup 

func (cg *ChainGroup) CycleGroup() *CycleGroup

func (*ChainGroup) Dim 

func (cg *ChainGroup) Dim() Dim

Dim is the dimension of the simplices that make up the ChainGroup.

func (*ChainGroup) HomologyGroup 

func (cg *ChainGroup) HomologyGroup() *HomologyGroup

func (*ChainGroup) IsElement 

func (cg *ChainGroup) IsElement(c *Chain) bool

IsElement returns true if c is a Chain in the ChainGroup; returns false otherwise.

func (*ChainGroup) IsZero 

func (cg *ChainGroup) IsZero(c *Chain) bool

IsZero returns true if c is the zero element of the ChainGroup.

func (*ChainGroup) NewChainFromSimplices 

func (cg *ChainGroup) NewChainFromSimplices(s ...*Simplex) *Chain

func (*ChainGroup) Rank 

func (cg *ChainGroup) Rank() int

Rank is the number of simplices that make up the ChainGroup.

func (*ChainGroup) Simplex 

func (cg *ChainGroup) Simplex(idx Index) *Simplex

Simplex returns the Simplex with index idx from the ChainGroups set of simplices.

func (*ChainGroup) Simplices 

func (cg *ChainGroup) Simplices() []*Simplex

Simplices returns the simplices that make up the ChainGroup.

func (*ChainGroup) Singleton 

func (cg *ChainGroup) Singleton(s *Simplex) *Chain

Singleton returns the Chain consisting of only s.

func (*ChainGroup) String 

func (cg *ChainGroup) String() string

func (*ChainGroup) Zero 

func (cg *ChainGroup) Zero() *Chain

Zero returns the zero element of the ChainGroup.

type ChainGroups 

type ChainGroups map[Dim]*ChainGroup

type Complex 

type Complex struct {
	// contains filtered or unexported fields
}

Complex represents an abstract simplicial complex. More info: https://en.wikipedia.org/wiki/Abstract_simplicial_complex

func ComplexFromOBJFile added in v0.2.0 

func ComplexFromOBJFile(path string) (*Complex, error)

ComplexFromOBJFile reads in the .obj file at path and builds a *Complex out of the face data in the file.

func (*Complex) BettiNumbers 

func (c *Complex) BettiNumbers() []int

BettiNumbers gives the sequence of Betti numbers B_0 to B_p where p is the dimension of the complex. The Betti number B_d can be thought of as the number of d-dimensional holes in the Complex; except for B_0, which is the number of connected components.

func (*Complex) ChainGroup 

func (c *Complex) ChainGroup(d Dim) *ChainGroup

ChainGroup returns the free abelian group of d-chains in the Complex.

More info: https://en.wikipedia.org/wiki/Free_abelian_group

func (*Complex) EulerChar 

func (c *Complex) EulerChar() int

EulerChar returns the Euler characteristic of the Complex.

More info: https://en.wikipedia.org/wiki/Euler_characteristic

func (*Complex) EulerIntegral 

func (c *Complex) EulerIntegral(a, b int, f CF) int

EulerIntegral computes the integral of f for s-values ranging from a to b over the Complex, using the Euler characteristic as its measure. For better stability, this method uses upper excursion sets rather than level sets.

We compute the Euler integral as: 

  /-\             _b_                  _b_
  |	              \                    \
  | f(x) d'\/  =  /__ s * '\/({f=s}) = /__ '\/({f>s})
  |        /\,    s=a      /\,         s=a  /\,
\-/ c

where {f=s} is a level set and {f>s} is an upper excursion set.

More info: https://en.wikipedia.org/wiki/Euler_calculus

func (*Complex) GetSimplex 

func (c *Complex) GetSimplex(base ...Index) *Simplex

GetSimplex returns the Simplex consisting of 0-simplices with base indices.

func (*Complex) GetSimplexByIndex 

func (c *Complex) GetSimplexByIndex(idx Index, d Dim) *Simplex

GetSimplexByIndex returns the Simplex of dimension d with Index idx.

func (*Complex) GetdSimplices 

func (c *Complex) GetdSimplices(d Dim) []*Simplex

func (*Complex) LevelSet 

func (c *Complex) LevelSet(f CF, s int) *Complex

LevelSet returns a sub-Complex of c; if smplx is a Simplex in Complex c, then smplx is in the level set if f(v) = s for each vertex v in smplx.

func (*Complex) LowerExcursionSet 

func (c *Complex) LowerExcursionSet(f CF, s int) *Complex

LowerExcursionSet returns a sub-Complex of c; if smplx is a Simplex in Complex c, then smplx is in the upper excursion set if f(v) < s for each vertex v in smplx.

func (*Complex) NewSimplex 

func (c *Complex) NewSimplex(base ...Index) *Simplex

NewSimplex adds a Simplex to c. All lower dimensional faces of the new Simplex are computed and automatically added to c.

func (*Complex) NewSimplexWithData 

func (c *Complex) NewSimplexWithData(dp DataProvider, base ...Index) *Simplex

NewSimplex adds a Simplex to c while using dp to attach data to each newly created Simplex. All lower dimensional faces of the new Simplex are computed and automatically added to c.

func (*Complex) NewSimplices 

func (c *Complex) NewSimplices(bases ...Base) *SimplicialSet

NewSimplex adds multiple simplices to c. All lower dimensional faces of each new Simplex are computed and automatically added to c.

func (*Complex) NewSimplicesWithData 

func (c *Complex) NewSimplicesWithData(dp DataProvider, bases ...Base) *SimplicialSet

NewSimplex adds multiple simplices to c, using dp to attach data to each newly created Simplex. All lower dimensional faces of each new Simplex are computed and automatically added to c.

func (*Complex) PrincipleSimplices 

func (c *Complex) PrincipleSimplices() *SimplicialSet

PrincipleSimplices returns the set of principle simplices in the Complex. A Simplex is principle if it's not the face of any other Simplex (has no cofaces).

func (*Complex) ReducedBettiNumbers 

func (c *Complex) ReducedBettiNumbers() []int

ReducedBettiNumbers gives the sequence of reduced Betti numbers B_0 to B_p where p is the dimension of the complex. The Betti number B_d can be thought of as the number of d-dimensional holes in the Complex.

func (*Complex) String 

func (c *Complex) String() string

func (*Complex) UpperExcursionSet 

func (c *Complex) UpperExcursionSet(f CF, s int) *Complex

UpperExcursionSet returns a sub-Complex of c; if smplx is a Simplex in Complex c, then smplx is in the upper excursion set if f(v) > s for each vertex v in smplx.

type CycleGroup 

type CycleGroup struct {
	// contains filtered or unexported fields
}

CycleGroup Z_p is a subgroup of the ChainGroup C_p of the same dimension p. A cycle group Z_p consists of all chains in in the chain group C_p with a zero / empty boundary (ie cycles).

func (*CycleGroup) Basis 

func (cg *CycleGroup) Basis() []*Chain

func (*CycleGroup) ChainGroup 

func (cg *CycleGroup) ChainGroup() *ChainGroup

func (*CycleGroup) Rank 

func (cg *CycleGroup) Rank() int

type DataProvider 

type DataProvider func(Dim, Index, Base) interface{}

DataProvider is used to attach user-defined data to simplices.

type Dim 

type Dim uint

type HomologyGroup 

type HomologyGroup struct {
	// contains filtered or unexported fields
}

HomologyGroup H_p is the quotient of Z_p and B_p: H_p = Z_p / B_p

func (*HomologyGroup) Basis 

func (hg *HomologyGroup) Basis() []*Chain

func (*HomologyGroup) MinimalBasis 

func (hg *HomologyGroup) MinimalBasis() []*Chain

MinimalBasis computes a basis for the homology group that is minimal with respect to Hamming weight + length of the interesection of the chains in the basis. The idea is to **try** to find the smallest cycles that cycle around the holes in the most linearly independent way.

type Index 

type Index uint

Index is used to establiish a total order amongst simplices of the same dimension. Index is also used to uniquely identify simplicies up to dimension.

type Simplex 

type Simplex struct {
	Data interface{}
	// contains filtered or unexported fields
}

Simplex is a p-dimensional polytope which is the convex hull of its p+1 0-dimensional simplices (points/vertices). Every Simplex should be part of a Complex; every Simplex in a Complex is considered to live in the same topological space. Simplex is uniquely identified in its Complex by its dimension ((*Simplex).Dim) and Index ((*Simplex).Index). Simplex can encapsulate user-defined data in its Data field.

More info: https://encyclopediaofmath.org/wiki/Simplex_(abstract)

func (*Simplex) AllCofaces 

func (s *Simplex) AllCofaces() *SimplicialSet

AllCofaces returns the set of simplices of any dimension that have s as a face.

func (*Simplex) Base 

func (s *Simplex) Base() Base

Base returns a copy of the base set of s.

func (*Simplex) Boundary 

func (s *Simplex) Boundary() *Chain

Boundary computes the boundary of s as a Chain in a ChainGroup of the Complex of s.

func (*Simplex) Cofaces 

func (s *Simplex) Cofaces(d Dim) *SimplicialSet

Cofaces returns the set of simplices of dimension d that have s as a face.

func (*Simplex) Complex 

func (s *Simplex) Complex() *Complex

Complex returns the Complex that s belongs to.

func (*Simplex) Dim 

func (s *Simplex) Dim() Dim

Dim returns the dimension of s, which is defined to be 1 + (# of points/0-simplices in s).

func (*Simplex) Equals 

func (s *Simplex) Equals(f *Simplex) bool

Equal returns true if s and f are equal; returns false otherwise.

func (*Simplex) EulerChar 

func (s *Simplex) EulerChar() int

EulerChar returns the Euler characteristic of s. This function is always equal to 1 for every Simplex.

More info: https://en.wikipedia.org/wiki/Euler_characteristic

func (*Simplex) Faces 

func (s *Simplex) Faces(d Dim) *SimplicialSet

Faces returns the set of d dimensional faces of s.

func (*Simplex) HasFace 

func (s *Simplex) HasFace(f *Simplex) bool

HasFace returns true if s has f as a face.

func (*Simplex) Index 

func (s *Simplex) Index() Index

Index returns the Index of s, which uniquely identifies it in the basis of its corresponding ChainGroup.

func (*Simplex) Intersection 

func (s *Simplex) Intersection(g *Simplex) *Simplex

Intersection returns the intersection of simplices s and g.

func (*Simplex) String 

func (s *Simplex) String() string

type SimplicialSet 

type SimplicialSet struct {
	// contains filtered or unexported fields
}

SimplicialSet is a set containing simplices. Note: SimplicialSet is not a category theoretical simplicial set.

func NewSimplicialSet 

func NewSimplicialSet(smplxs ...*Simplex) *SimplicialSet

NewSimplicialSet returns the SimplicialSet containing the provided simplices.

func (*SimplicialSet) Add 

func (ss *SimplicialSet) Add(smplxs ...*Simplex)

Add appends the provided simplices to the SimplicialSet.

func (*SimplicialSet) Card 

func (ss *SimplicialSet) Card() int

Card returns the cardinality (number of elements in the set) of the SimplicialSet.

func (*SimplicialSet) EulerChar 

func (ss *SimplicialSet) EulerChar() int

EulerChar returns the Euler characteristic of the SimplicialSet.

More info: https://en.wikipedia.org/wiki/Euler_characteristic

func (*SimplicialSet) RankedSlices 

func (ss *SimplicialSet) RankedSlices() map[Dim][]*Simplex

RankedSlices returns the slices in the set organized by their dimension.

func (*SimplicialSet) Rem 

func (ss *SimplicialSet) Rem(smplxs ...*Simplex)

Rem removes the provided elements from the SimplicialSet.

func (*SimplicialSet) Slice 

func (ss *SimplicialSet) Slice() []*Simplex

Slice returns the simplices in the set as a []*Simplex slice.

func (*SimplicialSet) Union 

func (ss *SimplicialSet) Union(sets ...*SimplicialSet) *SimplicialSet

Union returns the union of ss with the provided sets.

type Vector 

type Vector mat.Matrix

Vector is a vector representation of the elements of a ChainGroup of rank p where p = length of the vector. All elements/entries are expected to be 0 or 1. A 1 in the i_th position indicates that the p-dimensional Simplex with index i is part of the chain.

func NewVector 

func NewVector(els ...int) Vector

NewVector returns a vector with elements/entries els.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.