Documentation
¶
Overview ¶
Package structures provides a few generic data structures.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Digraph ¶
type Digraph[Node comparable] map[Node]Set[Node]
func (Digraph[Node]) AddEdge ¶
func (g Digraph[Node]) AddEdge(from, to Node)
AddEdge adds an edge from the first node to the second node. If the edge was already in the graph, nothing changes.
func (Digraph[Node]) AddNode ¶
func (g Digraph[Node]) AddNode(n Node)
AddNode adds the node to the graph. If the node was already in the graph, nothing changes.
func (Digraph[Node]) ComputeTransitiveClosure ¶
func (g Digraph[Node]) ComputeTransitiveClosure() TransitiveClosure[Node]
ComputeTransitiveClosure adds edges between every pair of nodes which are transitively connected by some path of directed edges. This is just the transitive closure of the relation expressed by the digraph. Iff the digraph isn't a DAG (i.e. iff it has cycles), then each node in the cycle will have an edge directed to itself.
type MapDigraph ¶
type MapDigraph[Node comparable] interface { ~map[Node]Set[Node] }
type Set ¶
type Set[Node comparable] map[Node]struct{}
type TransitiveClosure ¶
type TransitiveClosure[Node comparable] Digraph[Node]
func (TransitiveClosure[Node]) HasEdge ¶
func (g TransitiveClosure[Node]) HasEdge(from, to Node) bool
HasEdge checks whether an edge exists from the first node to the second node.
func (TransitiveClosure[Node]) IdentifyCycles ¶
func (g TransitiveClosure[Node]) IdentifyCycles() [][]Node
IdentifyCycles builds a sorted list of cycles in the transitive closure, where each cycle is a list of nodes sorted lexigoraphically by the node's string representation.
func (TransitiveClosure[Node]) Invert ¶
func (g TransitiveClosure[Node]) Invert() TransitiveClosure[Node]
Invert converts a digraph of children pointing to parents into a new digraph of parents pointing to children.
Source Files