Documentation
¶
Overview ¶
Package graph provides a typed, generic directed or acyclic graph with multiple edge kinds. Each kind declares whether edges are directed and acyclic through its type; cycles are rejected on insert. Graph is a pure data structure with no locks, goroutines, or I/O; synchronization belongs in a store that places the graph.
Index ¶
- type Edge
- type ErrCycle
- type ErrDuplicateEdge
- type ErrDuplicateNode
- type ErrUnknownNode
- type ErrUnknownRelation
- type Graph
- func (g *Graph[N, E]) AddEdge(kind E, from N, to N) error
- func (g *Graph[N, E]) AddNode(node N) error
- func (g *Graph[N, E]) DeclareRelation(kind E, edge Edge) error
- func (g *Graph[N, E]) Frontier(kind E, done func(node N) bool) []N
- func (g *Graph[N, E]) Has(node N) bool
- func (g *Graph[N, E]) HasEdge(kind E, from N, to N) bool
- func (g *Graph[N, E]) In(kind E, node N) []N
- func (g *Graph[N, E]) Len() int
- func (g *Graph[N, E]) Nodes() []N
- func (g *Graph[N, E]) Out(kind E, node N) []N
- func (g *Graph[N, E]) Reaches(kind E, from N, to N) bool
- func (g *Graph[N, E]) TopologicalOrder(kind E) []N
- func (g *Graph[N, E]) UpwardRank(kind E, weight func(node N) float64, skip func(node N) bool) map[N]float64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ErrCycle ¶
type ErrCycle struct {
Kind interface{}
From interface{}
To interface{}
Reason string
}
ErrCycle indicates that adding an edge would create a cycle in an acyclic relation.
type ErrDuplicateEdge ¶
type ErrDuplicateEdge struct {
Kind interface{}
From interface{}
To interface{}
}
ErrDuplicateEdge indicates that the edge already exists.
func (ErrDuplicateEdge) Error ¶
func (err ErrDuplicateEdge) Error() string
type ErrDuplicateNode ¶
type ErrDuplicateNode struct {
Node interface{}
}
ErrDuplicateNode indicates that the node is already in the graph.
func (ErrDuplicateNode) Error ¶
func (err ErrDuplicateNode) Error() string
type ErrUnknownNode ¶
type ErrUnknownNode struct {
Node interface{}
}
ErrUnknownNode indicates that the node is not in the graph.
func (ErrUnknownNode) Error ¶
func (err ErrUnknownNode) Error() string
type ErrUnknownRelation ¶
type ErrUnknownRelation struct {
Kind interface{}
}
ErrUnknownRelation indicates that the edge kind is not declared.
func (ErrUnknownRelation) Error ¶
func (err ErrUnknownRelation) Error() string
type Graph ¶
type Graph[N comparable, E comparable] struct { // contains filtered or unexported fields }
Graph[N, E] is a typed, generic directed or acyclic graph where N is the node type and E is the edge kind type. Nodes carry payloads of type N; edge kinds declare their properties (directed, acyclic) through Edge.
func (*Graph[N, E]) AddEdge ¶
AddEdge adds a directed edge from `from` to `to` with the given kind. It returns an error if:
- the edge kind is not declared
- either endpoint is not in the graph
- the edge already exists
- the edge is not directed and both directions already exist
- the edge would create a cycle in an acyclic relation
func (*Graph[N, E]) AddNode ¶
AddNode adds a node to the graph. It returns ErrDuplicateNode if the node already exists.
func (*Graph[N, E]) DeclareRelation ¶
DeclareRelation declares an edge kind with its properties. It must be called before any edges of that kind are added.
func (*Graph[N, E]) Frontier ¶
Frontier computes the ready set (frontier) of the graph: nodes that are not done and whose predecessors are all done. Nodes are returned in insertion order.
func (*Graph[N, E]) HasEdge ¶
HasEdge reports whether a directed edge exists from `from` to `to` with the given kind.
func (*Graph[N, E]) In ¶
func (g *Graph[N, E]) In(kind E, node N) []N
In returns the predecessors of node for the given edge kind, in insertion order.
func (*Graph[N, E]) Nodes ¶
func (g *Graph[N, E]) Nodes() []N
Nodes returns all nodes in the graph in insertion order.
func (*Graph[N, E]) Out ¶
func (g *Graph[N, E]) Out(kind E, node N) []N
Out returns the successors of node for the given edge kind, in insertion order.
func (*Graph[N, E]) Reaches ¶
Reaches reports whether there is a directed path from `from` to `to` for the given edge kind.
func (*Graph[N, E]) TopologicalOrder ¶
func (g *Graph[N, E]) TopologicalOrder(kind E) []N
TopologicalOrder returns the nodes of the graph in topological order for the given edge kind, using insertion order as a tie-breaker. It returns nil if the edge kind is unknown or if a cycle exists (which should not happen if the graph enforces acyclicity).
func (*Graph[N, E]) UpwardRank ¶
func (g *Graph[N, E]) UpwardRank(kind E, weight func(node N) float64, skip func(node N) bool) map[N]float64
UpwardRank computes the longest path to a sink for each node under the given edge kind, scaled by the node weight, and with nodes skipped by the skip predicate excluded. This is useful for critical-path and HEFT-style scheduling. The weight function should return non-negative values; negative weights are treated as 0.
Source Files