The highest tagged major version is
Documentation
¶
Index ¶
- Variables
- type CheckFn
- type DepMap
- type DependencyInfo
- type Graph
- func (g *Graph[T, V]) AddNode(node T)
- func (g *Graph[T, V]) AddProvides(provides T, depInfo *alpm.Depend, node T)
- func (g *Graph[T, V]) DependOn(child, parent T) error
- func (g *Graph[T, V]) Dependencies(child T) NodeSet[T]
- func (g *Graph[T, V]) Dependents(parent T) NodeSet[T]
- func (g *Graph[T, V]) DependsOn(child, parent T) bool
- func (g *Graph[T, V]) Exists(node T) bool
- func (g *Graph[T, V]) ForEach(f CheckFn[T, V]) error
- func (g *Graph[T, V]) GetNodeInfo(node T) *NodeInfo[V]
- func (g *Graph[T, V]) GetProviderInfo(provides T) *DependencyInfo[T]
- func (g *Graph[T, V]) HasDependent(parent, dependent T) bool
- func (g *Graph[T, V]) HasProvides(provides T) bool
- func (g *Graph[T, V]) ImmediateDependencies(node T) NodeSet[T]
- func (g *Graph[T, V]) ImmediateDependents(node T) NodeSet[T]
- func (g *Graph[T, V]) Len() int
- func (g *Graph[T, V]) Prune(node T) []T
- func (g *Graph[T, V]) SetNodeInfo(node T, nodeInfo *NodeInfo[V])
- func (g *Graph[T, V]) String() string
- func (g *Graph[T, V]) TopoSortedLayers(checkFn CheckFn[T, V]) []map[T]V
- type NodeInfo
- type NodeSet
- type ProvidesMap
Constants ¶
This section is empty.
Variables ¶
var ( // ErrSelfReferential is returned when attempting to create an edge where a node depends on itself. ErrSelfReferential = errors.New(" self-referential dependencies not allowed") // ErrConflictingAlias is reserved for when a "provides" alias is defined more than once. // Note: current Graph APIs overwrite provides entries; this error is not currently returned. ErrConflictingAlias = errors.New(" alias already defined") // ErrCircular is returned when attempting to create an edge that would introduce a cycle. ErrCircular = errors.New(" circular dependencies not allowed") )
Functions ¶
This section is empty.
Types ¶
type CheckFn ¶
type CheckFn[T comparable, V any] func(T, V) error
CheckFn is a callback used by traversal helpers. It receives the node id plus the node's value.
type DepMap ¶
type DepMap[T comparable] map[T]NodeSet[T]
DepMap maps a node to a set of nodes. In Graph this is used for adjacency: - dependencies: node -> its direct dependencies - dependents: node -> its direct dependents
type DependencyInfo ¶
type DependencyInfo[T comparable] struct { Provider T alpm.Depend }
DependencyInfo describes which node provides a given dependency/satisfier, along with the original dependency metadata (alpm.Depend).
type Graph ¶
type Graph[T comparable, V any] struct { // contains filtered or unexported fields }
Graph is a directed dependency graph.
Edge direction: - An edge is added with DependOn(child, parent), meaning "child depends on parent". - Internally, dependencies maps child -> parents (direct dependencies). - Internally, dependents maps parent -> children (direct dependents).
func (*Graph[T, V]) AddNode ¶
func (g *Graph[T, V]) AddNode(node T)
AddNode adds node to the graph. It is safe to call multiple times.
func (*Graph[T, V]) AddProvides ¶ added in v12.6.0
AddProvides registers that node provides the given provides key.
Note: despite the "Add" name, this is a single mapping; calling it again with the same provides key overwrites the previous entry.
func (*Graph[T, V]) DependOn ¶
DependOn adds an edge meaning "child depends on parent".
This ensures both nodes exist in the graph and rejects: - self edges (ErrSelfReferential) - edges that would introduce a cycle (ErrCircular)
func (*Graph[T, V]) Dependencies ¶
Dependencies returns all transitive dependencies of child (excluding child itself). The returned set is nil if child is not present in the graph.
func (*Graph[T, V]) Dependents ¶
Dependents returns all transitive dependents of parent (excluding parent itself). The returned set is nil if parent is not present in the graph.
func (*Graph[T, V]) ForEach ¶
ForEach calls f for every node in the graph.
The value passed to f is the node's NodeInfo.Value if set via SetNodeInfo; otherwise it is the zero value of V.
func (*Graph[T, V]) GetNodeInfo ¶
GetNodeInfo returns metadata/value for node, or nil if none was set.
func (*Graph[T, V]) GetProviderInfo ¶ added in v12.6.0
func (g *Graph[T, V]) GetProviderInfo(provides T) *DependencyInfo[T]
GetProviderInfo returns the dependency info for a provider.
func (*Graph[T, V]) HasDependent ¶
HasDependent reports whether parent has dependent as a (transitive) dependent.
func (*Graph[T, V]) HasProvides ¶ added in v12.6.0
HasProvides reports whether the given provides key is registered.
func (*Graph[T, V]) ImmediateDependencies ¶
ImmediateDependencies returns the direct dependencies of node. The returned set is nil if node has no direct dependencies (or is not present).
func (*Graph[T, V]) ImmediateDependents ¶ added in v12.6.0
ImmediateDependents returns the direct dependents of node. The returned set is nil if node has no direct dependents (or is not present).
func (*Graph[T, V]) Prune ¶
func (g *Graph[T, V]) Prune(node T) []T
Prune removes the node, its dependencies if there are no other dependents and its dependents
It returns the list of nodes that were removed (including node). The returned order is based on recursive traversal and is not guaranteed to be stable.
func (*Graph[T, V]) SetNodeInfo ¶
SetNodeInfo sets metadata and value for node. Node does not need to already exist in the graph.
func (*Graph[T, V]) String ¶
String renders the graph in GraphViz DOT format.
Nodes are emitted as `"node"` entries with optional color metadata from NodeInfo. Edges are emitted in the direction: dependent -> dependency (child -> parent).
func (*Graph[T, V]) TopoSortedLayers ¶ added in v12.6.0
TopoSortedLayers returns a slice of all of the graph nodes in topological sort order with their node info.
The returned slice is layered: each element is a "layer" of nodes that have no remaining dependencies at that stage of the process.
Practical meaning with this graph's edge direction (DependOn(child, parent)): - Earlier layers contain nodes with fewer/zero dependencies (i.e. dependencies-first order). - A node appears only after all of its dependencies have appeared in earlier layers.
If checkFn is non-nil, it is called once per node when it is emitted in a layer. Returning an error causes TopoSortedLayers to return nil.
type NodeInfo ¶
NodeInfo carries optional rendering metadata (Color/Background) plus the node's value.
type NodeSet ¶
type NodeSet[T comparable] map[T]bool
NodeSet is a set of nodes represented as a map for O(1) membership checks. The boolean value is not meaningful; presence of the key indicates membership.
type ProvidesMap ¶
type ProvidesMap[T comparable] map[T]*DependencyInfo[T]
ProvidesMap maps a "provides" key (an alias/satisfier name) to information about the node that provides it.
Source Files