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.

Index

• Variables
• type COO
• type Edge
• type Graph
  • func NewGraph[V comparable]() *Graph[V]
  • func (g *Graph[V]) Edges() []struct{ ... }
  • func (g *Graph[V]) Vertices() []V
• type Hypergraph
  • func LoadJSON[V comparable](r io.Reader) (*Hypergraph[V], error)
  • func NewHypergraph[V comparable]() *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 comparable] struct {
	ID  string
	Set map[V]struct{}
}

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

type Graph

type Graph[V comparable] struct {
	// contains filtered or unexported fields
}

Graph represents a simple undirected graph.

func NewGraph

func NewGraph[V comparable]() *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 comparable] struct {
	// contains filtered or unexported fields
}

Hypergraph represents a hypergraph with generic vertex type V.

func LoadJSON

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

LoadJSON loads the hypergraph from JSON.

func NewHypergraph

func NewHypergraph[V comparable]() *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 with cutoffs.

func (*Hypergraph[V]) GreedyColoring

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

GreedyColoring returns a greedy coloring.

func (*Hypergraph[V]) GreedyHittingSet

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

GreedyHittingSet returns a greedy hitting set.

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.