Documentation
¶
Overview ¶
Package hypergraph provides a generic implementation of hypergraphs.
A hypergraph generalizes a graph by allowing edges (hyperedges) to connect any number of vertices, not just two. This enables modeling complex relationships in domains like databases, combinatorics, and constraint satisfaction problems.
Core Types ¶
The main type is Hypergraph, parameterized by vertex type V:
type Hypergraph[V cmp.Ordered] struct { ... }
Vertices can be any ordered type (int, string, etc.). Edges are identified by string IDs and contain sets of vertices.
Vertex and Edge Operations ¶
Basic operations for managing vertices and edges:
- Hypergraph.AddVertex, Hypergraph.RemoveVertex - vertex management
- Hypergraph.AddEdge, Hypergraph.RemoveEdge - edge management
- Hypergraph.HasVertex, Hypergraph.HasEdge - existence checks
- Hypergraph.Vertices, Hypergraph.Edges - enumeration
- Hypergraph.EdgeMembers, Hypergraph.EdgeSize - edge queries
- Hypergraph.VertexDegree - vertex degree (number of incident edges)
Graph Algorithms ¶
The package includes several algorithms for hypergraph analysis:
- Hypergraph.GreedyHittingSet - approximates minimum hitting set
- Hypergraph.EnumerateMinimalTransversals - enumerates all minimal transversals
- Hypergraph.GreedyColoring - computes a vertex coloring
- Hypergraph.ConnectedComponents - finds connected components
Transformations ¶
Hypergraphs can be transformed into related structures:
- Hypergraph.Dual - swaps vertices and edges
- Hypergraph.TwoSection - projects to ordinary graph
- Hypergraph.Primal - synonym for TwoSection
Serialization ¶
Hypergraphs can be serialized to and from JSON:
- Hypergraph.SaveJSON - writes to io.Writer
- LoadJSON - reads from io.Reader
Thread Safety ¶
Hypergraph is NOT safe for concurrent use. If multiple goroutines access a Hypergraph concurrently, and at least one modifies it, external synchronization is required.
Error Handling ¶
Operations that can fail return errors:
- ErrDuplicateEdge - returned by AddEdge if edge ID exists
- ErrCutoff - returned by EnumerateMinimalTransversals when limits reached
Example ¶
Basic usage creating a hypergraph and computing a hitting set:
h := hypergraph.NewHypergraph[string]()
h.AddVertex("A")
h.AddVertex("B")
h.AddVertex("C")
if err := h.AddEdge("E1", []string{"A", "B"}); err != nil {
log.Fatal(err)
}
if err := h.AddEdge("E2", []string{"B", "C"}); err != nil {
log.Fatal(err)
}
hittingSet := h.GreedyHittingSet()
fmt.Println("Hitting set:", hittingSet) // e.g., [B]
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
- type Hypergraph
- 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]) EdgeMembers(id string) []V
- 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]) Primal() *Graph[V]
- 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
Constants ¶
This section is empty.
Variables ¶
var ( // ErrDuplicateEdge is returned when adding an edge with an existing ID. ErrDuplicateEdge = errors.New("duplicate edge ID") // ErrCutoff indicates an algorithm terminated early due to a configured cutoff. ErrCutoff = errors.New("operation cutoff reached") )
Functions ¶
This section is empty.
Types ¶
type Graph ¶
Graph represents a simple undirected graph.
type Hypergraph ¶
Hypergraph represents a hypergraph with generic vertex type V. V must satisfy cmp.Ordered to enable efficient sorting operations.
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]) EdgeMembers ¶ added in v1.7.0
func (h *Hypergraph[V]) EdgeMembers(id string) []V
EdgeMembers returns the members of an edge.
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]) Primal ¶ added in v1.7.0
func (h *Hypergraph[V]) Primal() *Graph[V]
Primal returns the primal graph (synonym for TwoSection). The primal graph is an ordinary graph where vertices are connected if they belong to the same hyperedge.
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.
Source Files