Struct Complex 

pub struct Complex<T: ComplexElement> {
    pub attachment_lattice: Lattice<usize>,
    pub elements: HashMap<usize, T>,
    pub next_id: usize,
}

A generic topological complex that can work with any type implementing ComplexElement.

This structure provides a unified framework for working with various types of cell complexes (simplicial, cubical, etc.) while maintaining the essential topological and algebraic properties needed for homological computations.

Mathematical Foundation

A cell complex K is a topological space built by attaching cells of various dimensions according to specific rules:

1. Closure Property: If σ ∈ K, then all faces of σ are also in K
2. Face Relations: Form a partial order where τ ≤ σ means “τ is a face of σ”
3. Dimension Stratification: K = K⁰ ∪ K¹ ∪ K² ∪ … where Kⁱ contains all i-cells
4. Chain Complex Structure: Boundary operators ∂ᵢ: Cᵢ → Cᵢ₋₁ with ∂² = 0

Implementation Architecture

This implementation uses a dual-structure approach:

┌─────────────────┐    ┌──────────────────┐
│ attachment_     │    │ elements:        │
│ lattice:        │◄──►│ HashMap<usize,T> │
│ Lattice<usize>  │    │                  │  
└─────────────────┘    └──────────────────┘
       ▲                        ▲
       │ IDs only               │ Full elements
       ▼                        ▼
  Fast operations           Rich operations

• Elements HashMap: Stores actual elements indexed by unique IDs
• Attachment Lattice: Tracks face relationships using IDs for efficiency
• ID Management: Automatic assignment with deduplication support

Key Properties

Closure Property Enforcement

The Complex::join_element method ensures closure: adding any element automatically includes all its faces. This maintains the fundamental property that distinguishes complexes from arbitrary cell collections.

Efficient Face Queries

Face relationships are stored in a Lattice<usize> structure, enabling:

• O(1) face/coface lookups after preprocessing
• Efficient upset/downset computations
• Support for meet/join operations on cells

Deduplication

Elements with identical mathematical content are automatically deduplicated using ComplexElement::same_content, preventing redundant storage and maintaining well-defined structure.

Usage Patterns

Basic Construction

use harness_space::complexes::{Complex, Simplex};

let mut complex = Complex::new();
let triangle = Simplex::new(2, vec![0, 1, 2]);
let added = complex.join_element(triangle);

// Automatically includes all faces: 1 triangle + 3 edges + 3 vertices
assert_eq!(complex.elements_of_dimension(2).len(), 1);
assert_eq!(complex.elements_of_dimension(1).len(), 3);
assert_eq!(complex.elements_of_dimension(0).len(), 3);

Homology Computation

use harness_algebra::algebras::boolean::Boolean;
use harness_space::{
  complexes::{Simplex, SimplicialComplex},
  prelude::*,
};

let mut complex = SimplicialComplex::new();

// Create a circle (1-dimensional hole)
let edge1 = Simplex::new(1, vec![0, 1]);
let edge2 = Simplex::new(1, vec![1, 2]);
let edge3 = Simplex::new(1, vec![2, 0]);
complex.join_element(edge1);
complex.join_element(edge2);
complex.join_element(edge3);

let h1 = complex.homology::<Boolean>(1);
assert_eq!(h1.betti_number, 1); // One 1D hole

Working with Face Relations

use harness_space::{
  complexes::{Simplex, SimplicialComplex},
  prelude::*,
};

let mut complex = SimplicialComplex::new();
let triangle = Simplex::new(2, vec![0, 1, 2]);
let added = complex.join_element(triangle);

// Query face relationships
let faces = complex.faces(&added); // Direct faces only
let cofaces = complex.cofaces(&added); // Direct cofaces only
let downset = complex.downset(added); // All faces (transitive)

Performance Characteristics

• Element Access: O(1) by ID, O(n) by content search
• Face Queries: O(1) for direct faces, O(k) for k-dimensional queries
• Adding Elements: O(f) where f is the number of faces to add
• Homology: O(n³) where n is the number of elements in relevant dimensions

Type Parameters

• T: The element type, must implement ComplexElement

Examples

See the extensive test suite for examples including:

• Construction of standard complexes (simplicial, cubical)
• Homology computations for various topological spaces
• Integration with poset and topology interfaces

Fields

attachment_lattice: Lattice<usize>

The attachment relationships between elements, represented as a lattice of element IDs.

This lattice encodes the face relation: if element a is a face of element b, then attachment_lattice.leq(a.id(), b.id()) returns Some(true).

Using IDs rather than full elements provides:

• Memory efficiency: IDs are much smaller than full elements
• Performance: Integer comparisons are faster than element comparisons
• Flexibility: Lattice operations independent of element type

elements: HashMap<usize, T>

A map storing all elements in the complex, keyed by their assigned ID.

This provides:

• Fast lookup: O(1) access to elements by ID
• Rich operations: Access to full element data and methods
• Content queries: Iteration over elements by dimension, type, etc.

next_id: usize

The counter for the next available unique element identifier.

This ensures that:

• Each element gets a unique ID when added
• IDs are assigned sequentially for predictable behavior
• The complex can manage arbitrary numbers of elements

Implementations

impl<T: ComplexElement> Complex<T>

pub fn new() -> Self

Creates a new, empty complex.

The empty complex contains no elements and has trivial homology:

• H₀ = 0 (no connected components)
• Hₖ = 0 for all k > 0 (no higher-dimensional features)

Examples

use harness_space::{
  complexes::{Complex, Simplex},
  prelude::*,
};

let complex: Complex<Simplex> = Complex::new();
assert!(complex.is_empty());
assert_eq!(complex.max_dimension(), 0);

pub fn join_element(&mut self, element: T) -> T

Adds an element to the complex along with all its faces.

This is the fundamental operation for building complexes. It ensures the closure property by recursively adding all faces of the given element. If an element with equivalent mathematical content already exists, returns the existing element without modification.

Mathematical Foundation

In topology, a complex must satisfy the closure property:

If σ ∈ K, then ∂σ ⊆ K

This method enforces this property by:

1. Computing all faces of the input element via ComplexElement::faces
2. Recursively adding each face (which adds their faces, etc.)
3. Establishing face relationships in the attachment lattice
4. Deduplicating based on mathematical content

Algorithm

join_element(σ):
  1. Check if equivalent element already exists → return existing
  2. Assign ID to σ (reuse existing ID if valid, else assign next_id)
  3. For each face τ in faces(σ):
       added_τ ← join_element(τ)  // Recursive call
       Add relation: added_τ ≤ σ to lattice
  4. Store σ in elements map
  5. Return σ with assigned ID

ID Assignment Strategy

• No ID: Assigns next_id and increments counter
• Has unused ID: Preserves existing ID if not taken
• Has conflicting ID: Assigns new ID to avoid conflicts

Deduplication Logic

Uses ComplexElement::same_content to check for existing equivalent elements. This ensures that mathematically identical elements (regardless of ID) are not duplicated in the complex.

Face Relationship Management

Establishes face_id ≤ element_id relationships in the attachment lattice for all direct faces. Transitive relationships are computed automatically by the lattice structure.

Return Value

Returns the element as it exists in the complex (with assigned ID). This may be:

• The input element with a newly assigned ID
• An existing equivalent element if content matches

Performance Notes

• Time: O(f) where f is the total number of faces to add (including recursive)
• Space: O(n) additional storage where n is the number of new elements
• Deduplication: O(k) check where k is the number of existing elements

Examples

Basic Usage

use harness_space::complexes::{Complex, Simplex};

let mut complex = Complex::new();
let triangle = Simplex::new(2, vec![0, 1, 2]);

let added = complex.join_element(triangle);
assert!(added.id().is_some());

// Complex now contains triangle + 3 edges + 3 vertices
assert_eq!(complex.elements_of_dimension(2).len(), 1);
assert_eq!(complex.elements_of_dimension(1).len(), 3);
assert_eq!(complex.elements_of_dimension(0).len(), 3);

Deduplication

let edge1 = Simplex::new(1, vec![0, 1]);
let edge2 = Simplex::new(1, vec![0, 1]); // Same content

let added1 = complex.join_element(edge1);
let added2 = complex.join_element(edge2);

// Returns same element (by ID)
assert_eq!(added1.id(), added2.id());
assert_eq!(complex.elements_of_dimension(1).len(), 1);

Building Complex Structures

let mut complex = Complex::new();

// Add multiple triangles sharing edges
let triangle1 = Simplex::new(2, vec![0, 1, 2]);
let triangle2 = Simplex::new(2, vec![1, 2, 3]);

complex.join_element(triangle1);
complex.join_element(triangle2);

// Shared edge [1,2] is not duplicated
assert_eq!(complex.elements_of_dimension(2).len(), 2); // 2 triangles
assert_eq!(complex.elements_of_dimension(1).len(), 5); // 5 unique edges
assert_eq!(complex.elements_of_dimension(0).len(), 4); // 4 vertices

pub fn get_element(&self, id: usize) -> Option<&T>

Retrieves an element by its unique ID.

Returns None if no element with the given ID exists in the complex. This is the primary method for accessing elements when you have their ID.

Performance

O(1) HashMap lookup.

Examples

let simplex = Simplex::new(1, vec![0, 1]);
let added = complex.join_element(simplex);
let id = added.id().unwrap();

let retrieved = complex.get_element(id).unwrap();
assert!(added.same_content(retrieved));

pub fn elements_of_dimension(&self, dimension: usize) -> Vec<T>

Returns all elements of a specific dimension.

This is useful for:

• Constructing basis sets for homology computations
• Analyzing the dimensional structure of the complex
• Iterating over elements by type (vertices, edges, faces, etc.)

Performance

O(n) where n is the total number of elements, as it must check the dimension of every element.

Examples

let vertices = complex.elements_of_dimension(0); // All 0-cells
let edges = complex.elements_of_dimension(1); // All 1-cells
let faces = complex.elements_of_dimension(2); // All 2-cells

assert_eq!(vertices.len(), 3);
assert_eq!(edges.len(), 3);
assert_eq!(faces.len(), 1);

pub fn max_dimension(&self) -> usize

Returns the maximum dimension of any element in the complex.

For an empty complex, returns 0. This is useful for determining the “dimension” of the complex as a topological space.

Examples

assert_eq!(complex.max_dimension(), 0); // Empty complex

let triangle = Simplex::new(2, vec![0, 1, 2]);
complex.join_element(triangle);
assert_eq!(complex.max_dimension(), 2); // 2D complex

pub fn faces(&self, element: &T) -> Vec<T>

Returns the direct faces of an element within this complex.

This differs from ComplexElement::faces in that it returns elements that actually exist in the complex (with assigned IDs) rather than abstract face descriptions.

Relationship to Lattice Operations

This is equivalent to finding the immediate predecessors of the element in the face lattice, but returns the full element objects rather than just IDs.

Examples

let triangle = Simplex::new(2, vec![0, 1, 2]);
let added_triangle = complex.join_element(triangle);

let faces = complex.faces(&added_triangle);
assert_eq!(faces.len(), 3); // Three edges
assert!(faces.iter().all(|face| face.dimension() == 1));
assert!(faces.iter().all(|face| face.id().is_some()));

pub fn cofaces(&self, element: &T) -> Vec<T>

Returns the direct cofaces of an element within this complex.

Cofaces are elements that have the given element as a face. This is the “upward” direction in the face lattice.

Examples

let cofaces = complex.cofaces(&edge);
assert_eq!(cofaces.len(), 1); // Edge is face of triangle
assert!(cofaces[0].same_content(&added_triangle));

pub fn homology<F: Field + Copy>(&self, k: usize) -> Homology<F>

Computes the k-dimensional homology of the complex over a field F.

Homology measures the “holes” in a topological space at different dimensions:

• H₀: Connected components (0-dimensional holes)
• H₁: Loops/cycles (1-dimensional holes)
• H₂: Voids/cavities (2-dimensional holes)
• Hₖ: k-dimensional holes (higher-dimensional features)

Mathematical Foundation

Homology is defined as the quotient of cycles by boundaries:

Hₖ(K) = Zₖ(K) / Bₖ(K) = ker(∂ₖ) / im(∂ₖ₊₁)

Where:

• Zₖ(K) = ker(∂ₖ): k-cycles (chains with no boundary)
• Bₖ(K) = im(∂ₖ₊₁): k-boundaries (boundaries of (k+1)-chains)
• ∂ₖ: Boundary operator from k-chains to (k-1)-chains

The key insight is that “holes” are cycles that are not boundaries of higher-dimensional chains.

Algorithm

1. Compute Cycles: Find kernel of boundary operator ∂ₖ: Cₖ → Cₖ₋₁
2. Compute Boundaries: Find image of boundary operator ∂ₖ₊₁: Cₖ₊₁ → Cₖ
3. Quotient Space: Compute basis for quotient space Zₖ/Bₖ
4. Return Homology: Package result with Betti number and generators

Special Cases

• k = 0: H₀ measures connected components. Z₀ = C₀ (all 0-chains are cycles)
• Empty Complex: All homology groups are trivial (Hₖ = 0)
• No k-elements: Returns trivial homology for that dimension

Field Dependency

The choice of coefficient field F affects the result:

• ℤ/2ℤ (Boolean): Ignores orientation, counts mod 2
• ℚ (Rationals): Full torsion-free homology
• ℤ/pℤ (Prime fields): Reveals p-torsion in homology

Performance

• Time: O(n³) where n is the number of k-dimensional elements
• Space: O(n²) for storing boundary matrices
• Bottleneck: Matrix kernel and image computations

Return Value

Returns a Homology object containing:

• dimension: The dimension k being computed
• betti_number: The rank of Hₖ (number of independent k-dimensional holes)
• homology_generators: Basis vectors representing the homology classes

Examples

Circle (1-dimensional hole)

use harness_algebra::algebras::boolean::Boolean;
use harness_space::complexes::{Complex, Simplex};

let mut complex = Complex::new();

// Create a triangle boundary (3 edges forming a cycle)
let edge1 = Simplex::new(1, vec![0, 1]);
let edge2 = Simplex::new(1, vec![1, 2]);
let edge3 = Simplex::new(1, vec![2, 0]);
complex.join_element(edge1);
complex.join_element(edge2);
complex.join_element(edge3);

let h0 = complex.homology::<Boolean>(0);
let h1 = complex.homology::<Boolean>(1);

assert_eq!(h0.betti_number, 1); // One connected component
assert_eq!(h1.betti_number, 1); // One 1-dimensional hole

Filled Triangle (no holes)

let triangle = Simplex::new(2, vec![0, 1, 2]);
complex.join_element(triangle);

let h0 = complex.homology::<Boolean>(0);
let h1 = complex.homology::<Boolean>(1);

assert_eq!(h0.betti_number, 1); // One connected component
assert_eq!(h1.betti_number, 0); // No 1D holes (filled)

Sphere Surface (2-dimensional hole)

// Tetrahedron boundary (4 triangular faces)
let face1 = Simplex::new(2, vec![0, 1, 2]);
let face2 = Simplex::new(2, vec![0, 1, 3]);
let face3 = Simplex::new(2, vec![0, 2, 3]);
let face4 = Simplex::new(2, vec![1, 2, 3]);
complex.join_element(face1);
complex.join_element(face2);
complex.join_element(face3);
complex.join_element(face4);

let h2 = complex.homology::<Boolean>(2);
assert_eq!(h2.betti_number, 1); // One 2-dimensional hole (sphere interior)

pub fn get_boundary_matrix<F: Field + Copy>( &self, k: usize, ) -> DynamicDenseMatrix<F, RowMajor>

where T: ComplexElement,

Constructs the boundary matrix ∂ₖ: Cₖ → Cₖ₋₁ for the k-th boundary operator.

The boundary matrix is the matrix representation of the linear map that takes k-dimensional chains to their (k-1)-dimensional boundaries. This is the fundamental building block for homology computations.

Mathematical Definition

For a k-dimensional element σ, its boundary ∂σ is a formal sum of (k-1)-dimensional faces with appropriate orientation coefficients:

∂ₖ(σ) = Σᵢ aᵢ τᵢ

where τᵢ are the faces of σ and aᵢ ∈ F are the orientation coefficients.

Matrix Structure

The resulting matrix has:

• Rows: Indexed by (k-1)-dimensional elements (codomain basis)
• Columns: Indexed by k-dimensional elements (domain basis)
• Entry (i,j): Coefficient of codomain element i in ∂(domain element j)

Element Ordering

Both domain and codomain elements are sorted using their natural ordering (from Ord implementation). This ensures:

• Deterministic matrix construction
• Consistent results across runs
• Predictable basis element correspondence

Boundary Operator Properties

The matrix satisfies the fundamental property ∂² = 0, meaning that boundary_matrix(k+1) * boundary_matrix(k) = 0. This is essential for the chain complex structure and homology computations.

Special Cases

• k = 0: Returns empty matrix (0-dimensional elements have no boundary)
• No k-elements: Returns matrix with correct row count but no columns
• No (k-1)-elements: Returns matrix with correct column count but no rows

Implementation Details

This method uses the ComplexElement::boundary_with_orientations method to get the oriented boundary of each element, then constructs the matrix by mapping faces to their positions in the codomain basis.

Performance

• Time: O(nf) where n is the number of k-elements and f is the average number of faces
• Space: O(nm) where m is the number of (k-1)-elements
• Optimized: Only computes non-zero entries

Examples

Triangle Boundary Matrix

use harness_algebra::algebras::boolean::Boolean;
use harness_space::complexes::{Complex, Simplex};

let mut complex = Complex::new();
let triangle = Simplex::new(2, vec![0, 1, 2]);
complex.join_element(triangle);

// Get boundary matrix ∂₂: C₂ → C₁ (triangles → edges)
let boundary_2 = complex.get_boundary_matrix::<Boolean>(2);

// Should be 3×1 matrix (3 edges, 1 triangle)
assert_eq!(boundary_2.num_rows(), 3); // 3 edges
assert_eq!(boundary_2.num_cols(), 1); // 1 triangle

Edge Boundary Matrix

let edge = Simplex::new(1, vec![0, 1]);
complex.join_element(edge);

// Get boundary matrix ∂₁: C₁ → C₀ (edges → vertices)
let boundary_1 = complex.get_boundary_matrix::<Boolean>(1);

// Should be 2×1 matrix (2 vertices, 1 edge)
assert_eq!(boundary_1.num_rows(), 2); // 2 vertices
assert_eq!(boundary_1.num_cols(), 1); // 1 edge

Trait Implementations

impl<T: Clone + ComplexElement> Clone for Complex<T>

fn clone(&self) -> Complex<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: ComplexElement> Collection for Complex<T>

Implementation of Collection for complexes.

Provides basic set-theoretic operations for checking element membership and complex emptiness. Note that containment is based on ID equality, so elements must have been added to the complex to be considered contained.

type Item = T

The type of elements stored in the collection.

fn contains(&self, point: &Self::Item) -> bool

Checks if an item is present in the collection.

fn is_empty(&self) -> bool

Determines if the collection is empty.

impl<T: Debug + ComplexElement> Debug for Complex<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: ComplexElement> Default for Complex<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: ComplexElement> Poset for Complex<T>

Implementation of Poset for complexes.

Defines the face relation as the partial order: σ ≤ τ means “σ is a face of τ”. This implementation delegates to the attachment lattice for efficiency while providing the full element objects in the interface.

The face relation satisfies all poset axioms:

• Reflexivity: σ ≤ σ (every element is a face of itself)
• Antisymmetry: σ ≤ τ and τ ≤ σ implies σ = τ
• Transitivity: σ ≤ τ and τ ≤ ρ implies σ ≤ ρ

fn leq(&self, a: &Self::Item, b: &Self::Item) -> Option<bool>

Tests if one item is less than or equal to another according to the partial order.

fn upset(&self, a: Self::Item) -> HashSet<Self::Item>

Computes the upset of an item a.

fn downset(&self, a: Self::Item) -> HashSet<Self::Item>

Computes the downset of an item a.

fn minimal_elements(&self) -> HashSet<Self::Item>

Finds all minimal elements of the poset.

fn maximal_elements(&self) -> HashSet<Self::Item>

Finds all maximal elements of the poset.

fn join(&self, a: Self::Item, b: Self::Item) -> Option<Self::Item>

Computes the join (least upper bound) of two items a and b, if it exists.

fn meet(&self, a: Self::Item, b: Self::Item) -> Option<Self::Item>

Computes the meet (greatest lower bound) of two items a and b, if it exists.

fn successors(&self, a: Self::Item) -> HashSet<Self::Item>

Finds all direct successors (covers) of an item a.

fn predecessors(&self, a: Self::Item) -> HashSet<Self::Item>

Finds all direct predecessors of an item a.

impl<T: ComplexElement> Topology for Complex<T>

Implementation of Topology for complexes.

Provides topological operations that integrate with the broader framework:

• Neighborhood: Returns cofaces (elements containing the given element)
• Boundary: Computes oriented boundary using element-specific operators

The boundary implementation is crucial for homology computations as it provides the chain complex structure with proper orientation handling.

fn neighborhood(&self, item: &Self::Item) -> Vec<Self::Item>

Returns the neighborhood of a given item in the topological space.

fn boundary<R: Ring + Copy>(&self, item: &Self::Item) -> Chain<'_, Self, R>

Computes the boundary of a given item in the topological space, represented as a formal chain.