hypergraph

Documentation

Overview

Package hypergraph provides a generic implementation of hypergraphs. A hypergraph is a generalization of a graph where edges can connect any number of vertices.

Concurrency: Hypergraph is NOT safe for concurrent use. Callers must synchronize access when using from multiple goroutines.

Index

• Variables
• type COO
• type Edge
• type Graph
  • func NewGraph[V cmp.Ordered]() *Graph[V]
  • func (g *Graph[V]) Edges() []struct{ ... }
  • func (g *Graph[V]) Vertices() []V
• type Hypergraph
  • func LoadJSON[V cmp.Ordered](r io.Reader) (*Hypergraph[V], error)
  • func NewHypergraph[V cmp.Ordered]() *Hypergraph[V]
  • func (h *Hypergraph[V]) AddEdge(id string, members []V) error
  • func (h *Hypergraph[V]) AddVertex(v V)
  • func (h *Hypergraph[V]) BFS(start V) []V
  • func (h *Hypergraph[V]) ConnectedComponents() [][]V
  • func (h *Hypergraph[V]) Copy() *Hypergraph[V]
  • func (h *Hypergraph[V]) DFS(start V) []V
  • func (h *Hypergraph[V]) Dual() *Hypergraph[string]
  • func (h *Hypergraph[V]) EdgeSize(id string) (int, bool)
  • func (h *Hypergraph[V]) Edges() []string
  • func (h *Hypergraph[V]) EnumerateMinimalTransversals(maxSolutions int, maxTime time.Duration) ([][]V, error)
  • func (h *Hypergraph[V]) GreedyColoring() map[V]int
  • func (h *Hypergraph[V]) GreedyHittingSet() []V
  • func (h *Hypergraph[V]) HasEdge(id string) bool
  • func (h *Hypergraph[V]) HasVertex(v V) bool
  • func (h *Hypergraph[V]) IncidenceMatrix() (vertexIndex map[V]int, edgeIndex map[string]int, coo COO)
  • func (h *Hypergraph[V]) IsEmpty() bool
  • func (h *Hypergraph[V]) LineGraph() *Graph[string]
  • func (h *Hypergraph[V]) NumEdges() int
  • func (h *Hypergraph[V]) NumVertices() int
  • func (h *Hypergraph[V]) RemoveEdge(id string)
  • func (h *Hypergraph[V]) RemoveVertex(v V)
  • func (h *Hypergraph[V]) SaveJSON(w io.Writer) error
  • func (h *Hypergraph[V]) TwoSection() *Graph[V]
  • func (h *Hypergraph[V]) VertexDegree(v V) int
  • func (h *Hypergraph[V]) Vertices() []V

Variables

var (
	// ErrDuplicateEdge is returned when adding an edge with an existing ID.
	ErrDuplicateEdge = errors.New("duplicate edge ID")
	// ErrUnknownEdge is returned when an operation references a missing edge.
	ErrUnknownEdge = errors.New("unknown edge ID")
	// ErrUnknownVertex is returned when an operation references a missing vertex.
	ErrUnknownVertex = errors.New("unknown vertex")
	// ErrCutoff indicates an algorithm terminated early due to a configured cutoff.
	ErrCutoff = errors.New("operation cutoff reached")
)

Types

type COO

type COO struct {
	Rows []int
	Cols []int
}

COO represents a sparse matrix in coordinate format.

type Edge

type Edge[V cmp.Ordered] struct {
	ID  string
	Set map[V]struct{}
}

Edge represents a hyperedge with an ID and a set of vertices.

type Graph

type Graph[V cmp.Ordered] struct {
	// contains filtered or unexported fields
}

Graph represents a simple undirected graph.

func NewGraph

func NewGraph[V cmp.Ordered]() *Graph[V]

NewGraph creates a new graph.

func (*Graph[V]) Edges

func (g *Graph[V]) Edges() []struct{ From, To V }

Edges returns all edges of the graph as pairs.

func (*Graph[V]) Vertices

func (g *Graph[V]) Vertices() []V

Vertices returns all vertices of the graph.

type Hypergraph

type Hypergraph[V cmp.Ordered] struct {
	// contains filtered or unexported fields
}

Hypergraph represents a hypergraph with generic vertex type V. V must satisfy cmp.Ordered to enable efficient sorting operations.

func LoadJSON

func LoadJSON[V cmp.Ordered](r io.Reader) (*Hypergraph[V], error)

LoadJSON loads the hypergraph from JSON.

func NewHypergraph

func NewHypergraph[V cmp.Ordered]() *Hypergraph[V]

NewHypergraph creates a new empty hypergraph.

func (*Hypergraph[V]) AddEdge

func (h *Hypergraph[V]) AddEdge(id string, members []V) error

AddEdge adds a hyperedge with the given ID and members.

func (*Hypergraph[V]) AddVertex

func (h *Hypergraph[V]) AddVertex(v V)

AddVertex adds a vertex to the hypergraph.

func (*Hypergraph[V]) BFS

func (h *Hypergraph[V]) BFS(start V) []V

BFS performs breadth-first search starting from a vertex, returning reachable vertices.

func (*Hypergraph[V]) ConnectedComponents

func (h *Hypergraph[V]) ConnectedComponents() [][]V

ConnectedComponents returns the connected components as slices of vertices.

func (*Hypergraph[V]) Copy

func (h *Hypergraph[V]) Copy() *Hypergraph[V]

Copy returns a deep copy of the hypergraph.

func (*Hypergraph[V]) DFS

func (h *Hypergraph[V]) DFS(start V) []V

DFS performs depth-first search starting from a vertex, returning reachable vertices.

func (*Hypergraph[V]) Dual

func (h *Hypergraph[V]) Dual() *Hypergraph[string]

Dual returns the dual hypergraph where vertices become edges and vice versa.

func (*Hypergraph[V]) EdgeSize

func (h *Hypergraph[V]) EdgeSize(id string) (int, bool)

EdgeSize returns the size of an edge.

func (*Hypergraph[V]) Edges

func (h *Hypergraph[V]) Edges() []string

Edges returns a slice of all edge IDs.

func (*Hypergraph[V]) EnumerateMinimalTransversals

func (h *Hypergraph[V]) EnumerateMinimalTransversals(maxSolutions int, maxTime time.Duration) ([][]V, error)

EnumerateMinimalTransversals enumerates minimal transversals using backtracking.

A transversal (or hitting set) intersects every hyperedge. A minimal transversal has no proper subset that is also a transversal. This function enumerates all minimal transversals up to the specified limits.

Parameters:

• maxSolutions: stop after finding this many transversals
• maxTime: stop after this duration

Returns ErrCutoff if either limit is reached before complete enumeration. Time complexity: exponential in worst case (NP-hard problem).

func (*Hypergraph[V]) GreedyColoring

func (h *Hypergraph[V]) GreedyColoring() map[V]int

GreedyColoring computes a vertex coloring using a greedy algorithm.

A valid coloring assigns colors (integers) to vertices such that no two vertices sharing a hyperedge have the same color. The greedy algorithm processes vertices in sorted order, assigning the smallest available color.

Returns a map from vertex to color (0-indexed integers). Time complexity: O(|V| * |E|).

func (*Hypergraph[V]) GreedyHittingSet

func (h *Hypergraph[V]) GreedyHittingSet() []V

GreedyHittingSet computes a hitting set using a greedy algorithm.

A hitting set is a subset of vertices that intersects every hyperedge. The greedy algorithm iteratively selects the vertex with maximum degree (number of remaining uncovered edges) until all edges are covered.

Time complexity: O(|V| * |E|) where |V| is vertices and |E| is edges. This is a polynomial-time approximation; the optimal hitting set problem is NP-hard.

func (*Hypergraph[V]) HasEdge

func (h *Hypergraph[V]) HasEdge(id string) bool

HasEdge checks if an edge exists.

func (*Hypergraph[V]) HasVertex

func (h *Hypergraph[V]) HasVertex(v V) bool

HasVertex checks if a vertex exists.

func (*Hypergraph[V]) IncidenceMatrix

func (h *Hypergraph[V]) IncidenceMatrix() (vertexIndex map[V]int, edgeIndex map[string]int, coo COO)

IncidenceMatrix returns the incidence matrix in COO format with stable vertex and edge indices.

func (*Hypergraph[V]) IsEmpty

func (h *Hypergraph[V]) IsEmpty() bool

IsEmpty checks if the hypergraph has no vertices or edges.

func (*Hypergraph[V]) LineGraph

func (h *Hypergraph[V]) LineGraph() *Graph[string]

LineGraph returns the line graph where vertices are edges, connected if they share a vertex.

func (*Hypergraph[V]) NumEdges

func (h *Hypergraph[V]) NumEdges() int

NumEdges returns the number of edges.

func (*Hypergraph[V]) NumVertices

func (h *Hypergraph[V]) NumVertices() int

NumVertices returns the number of vertices.

func (*Hypergraph[V]) RemoveEdge

func (h *Hypergraph[V]) RemoveEdge(id string)

RemoveEdge removes a hyperedge.

func (*Hypergraph[V]) RemoveVertex

func (h *Hypergraph[V]) RemoveVertex(v V)

RemoveVertex removes a vertex and all incident edges.

func (*Hypergraph[V]) SaveJSON

func (h *Hypergraph[V]) SaveJSON(w io.Writer) error

SaveJSON saves the hypergraph to JSON. Vertices and edge members are sorted for stable output; JSON map key order is not guaranteed.

func (*Hypergraph[V]) TwoSection

func (h *Hypergraph[V]) TwoSection() *Graph[V]

TwoSection returns the 2-section graph where vertices are connected if they share an edge.

func (*Hypergraph[V]) VertexDegree

func (h *Hypergraph[V]) VertexDegree(v V) int

VertexDegree returns the degree of a vertex.

func (*Hypergraph[V]) Vertices

func (h *Hypergraph[V]) Vertices() []V

Vertices returns a slice of all vertices.