HypergraphGo

README

Hypergraph-Go

A production-quality Go library for hypergraph theory, supporting generic vertex types, advanced algorithms, and CLI tools.

🚀 Now includes HoTT (Homotopy Type Theory) kernel implementation with normalization by evaluation!

Overview

Hypergraphs generalize graphs by allowing edges (called hyperedges) to connect any number of vertices. This library provides a flexible, efficient, and idiomatic Go implementation of hypergraphs with rich operations, transforms, and algorithms.

Additionally, this project includes a cutting-edge HoTT kernel implementation featuring:

• Normalization by Evaluation (NbE) with closure-based semantic domain
• Definitional equality checking with optional η-rules for Π/Σ types
• De Bruijn index-based core AST with bidirectional type checking (in progress)
• Cubical type theory foundations for univalent mathematics

Latest Release

v1.2.0 - Phase 2 Complete: Normalization and Definitional Equality ✅

New HoTT Kernel Features:

• NbE skeleton integrated under internal/eval with semantic domain (Values, Closures, Neutrals)
• Definitional equality checker added at core.Conv with environment support
• Optional η-rules for functions (f ≡ \x. f x) and pairs (p ≡ (fst p, snd p)) behind feature flags
• Expanded test suite with 22 new NbE tests + 15 conversion tests
• Performance benchmarks showing ~108 ns/op for simple conversions
• WHNF + spine representation for stuck computations
• Reify/reflect infrastructure for Value ↔ Term conversion

Quality Improvements:

• All tests deterministic and CI-friendly
• No panics in kernel paths, graceful error handling
• Kernel boundary maintained (no Value types leak)
• Standard library only, no external dependencies

Roadmap Progress

HoTT Kernel Development Status

Phase	Status	Description
Phase 0	✅	Ground rules and interfaces
Phase 1	✅	Syntax, binding, pretty printing
Phase 2	✅	Normalization and definitional equality
Phase 3	🚧	Bidirectional type checking
Phase 4	⏳	Identity/Path types (cubical knob)
Phase 5	⏳	Inductives, recursors, positivity
Phase 6	⏳	Univalence
Phase 7	⏳	Higher Inductive Types (HITs)
Phase 8	⏳	Elaboration and tactics
Phase 9	⏳	Standard library seed
Phase 10	⏳	Performance, soundness, packaging

Current Milestone: M5 - Bidirectional checker (check.Synth/Check)
Next Target: Type checking for identity functions and composition with precise error spans

Quickstart

Install the module and try a minimal snippet:

go get github.com/watchthelight/hypergraphgo

package main

import (
    "fmt"
    "github.com/watchthelight/hypergraphgo/hypergraph"
)

func main() {
    hg := hypergraph.NewHypergraph[string]()
    _ = hg.AddEdge("E1", []string{"A", "B", "C"})
    fmt.Println("Vertices:", hg.Vertices())
    fmt.Println("Edges:", hg.Edges())
}

Run the examples:

go run ./examples/basic
go run ./examples/algorithms

Installation

go get github.com/watchthelight/hypergraphgo

Replace watchthelight and hypergraphgo with your GitHub username and repository name.

Install via APT (Cloudsmith)

curl -1sLf 'https://dl.cloudsmith.io/public/watchthelight/hypergraphgo/setup.deb.sh' | sudo -E bash
sudo apt install hypergraphgo

Usage

Basic usage

package main

import (
    "fmt"
    "github.com/watchthelight/hypergraphgo/hypergraph"
)

func main() {
    hg := hypergraph.NewHypergraph[string]()
    hg.AddVertex("A")
    hg.AddVertex("B")
    hg.AddEdge("E1", []string{"A", "B"})
    fmt.Println("Vertices:", hg.Vertices())
    fmt.Println("Edges:", hg.Edges())
}

CLI examples

hg info -file example.json
hg add-vertex -file example.json -v "A"
hg add-edge -file example.json -id E1 -members "A,B,C"
hg components -file example.json
hg dual -in example.json -out dual.json
hg section -in example.json -out section.json
hg save -out example.json
hg load -in example.json

Algorithms and Complexity

• Greedy hitting set: polynomial time heuristic.
• Minimal transversals enumeration: exponential, supports cutoffs.
• Greedy coloring: heuristic.
• Dual, 2-section, and line graph transforms.
• Connectivity and traversal via BFS/DFS.

Example

Build a small hypergraph, print degrees, components, dual, and 2-section graphs.

Versioning

Starting at v0.1.0 with semantic versioning.

Releasing

Create and push a new tag based on the VERSION file.

Linux/macOS/WSL:

./scripts/release.sh patch   # or minor | major | 1.2.3

Windows PowerShell:

./scripts/release.ps1 patch  # or minor | major | 1.2.3

This updates VERSION, creates tag vX.Y.Z, and pushes the tag to origin.

License

MIT License © 2025 watchthelight