Documentation
¶
Index ¶
- type ComparableGraph
- func (g *ComparableGraph[Value]) AddEdge(from Value, to Value)
- func (g *ComparableGraph[Value]) AddNode(value Value)
- func (g *ComparableGraph[Value]) ContainsNode(key Value) bool
- func (g *ComparableGraph[Value]) DOTString(valueToString func(Value) string) (string, error)
- func (g *ComparableGraph[Value]) Graph() *Graph[Value, Value]
- func (g *ComparableGraph[Value]) InboundNodes(key Value) ([]Value, error)
- func (g *ComparableGraph[Value]) NumEdges() int
- func (g *ComparableGraph[Value]) NumNodes() int
- func (g *ComparableGraph[Value]) OutboundNodes(key Value) ([]Value, error)
- func (g *ComparableGraph[Value]) TopoSort(start Value) ([]Value, error)
- func (g *ComparableGraph[Value]) WalkEdges(f func(Value, Value) error) error
- func (g *ComparableGraph[Value]) WalkNodes(f func(Value, []Value, []Value) error) error
- type CycleError
- type Graph
- func (g *Graph[Key, Value]) AddEdge(from Value, to Value)
- func (g *Graph[Key, Value]) AddNode(value Value)
- func (g *Graph[Key, Value]) ContainsNode(key Key) bool
- func (g *Graph[Key, Value]) DOTString(valueToString func(Value) string) (string, error)
- func (g *Graph[Key, Value]) InboundNodes(key Key) ([]Value, error)
- func (g *Graph[Key, Value]) NumEdges() int
- func (g *Graph[Key, Value]) NumNodes() int
- func (g *Graph[Key, Value]) OutboundNodes(key Key) ([]Value, error)
- func (g *Graph[Key, Value]) TopoSort(start Key) ([]Value, error)
- func (g *Graph[Key, Value]) WalkEdges(f func(Value, Value) error) error
- func (g *Graph[Key, Value]) WalkNodes(f func(Value, []Value, []Value) error) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ComparableGraph ¶ added in v1.32.0
type ComparableGraph[Value comparable] struct { // contains filtered or unexported fields }
ComparableGraph is a Graph that uses comparable Values.
func NewComparableGraph ¶ added in v1.32.0
func NewComparableGraph[Value comparable]() *ComparableGraph[Value]
NewComparableGraph returns a new ComparableGraph for a comparable Value.
It is safe to initialize a ComparableGraph with &dag.ComparableGraph[value]{}.
Do not use interfaces as Values! If your Value type is an interface, use NewGraph.
func (*ComparableGraph[Value]) AddEdge ¶ added in v1.32.0
func (g *ComparableGraph[Value]) AddEdge(from Value, to Value)
AddEdge adds an edge.
func (*ComparableGraph[Value]) AddNode ¶ added in v1.32.0
func (g *ComparableGraph[Value]) AddNode(value Value)
AddNode adds a node.
func (*ComparableGraph[Value]) ContainsNode ¶ added in v1.32.0
func (g *ComparableGraph[Value]) ContainsNode(key Value) bool
ContainsNode returns true if the graph contains the given node.
func (*ComparableGraph[Value]) DOTString ¶ added in v1.32.0
func (g *ComparableGraph[Value]) DOTString(valueToString func(Value) string) (string, error)
DOTString returns a DOT representation of the graph.
valueToString is used to print out the label for each node.
func (*ComparableGraph[Value]) Graph ¶ added in v1.32.0
func (g *ComparableGraph[Value]) Graph() *Graph[Value, Value]
Graph returns the underlying Graph that backs the ComparableGraph.
Used for functions that need a Graph instead of a ComparableGraph.
func (*ComparableGraph[Value]) InboundNodes ¶ added in v1.32.0
func (g *ComparableGraph[Value]) InboundNodes(key Value) ([]Value, error)
InboundNodes returns the nodes that are inbound to the node for the key.
Returns error if there is no node for the key
func (*ComparableGraph[Value]) NumEdges ¶ added in v1.32.0
func (g *ComparableGraph[Value]) NumEdges() int
NumNodes returns the number of edges in the graph.
func (*ComparableGraph[Value]) NumNodes ¶ added in v1.32.0
func (g *ComparableGraph[Value]) NumNodes() int
NumNodes returns the number of nodes in the graph.
func (*ComparableGraph[Value]) OutboundNodes ¶ added in v1.32.0
func (g *ComparableGraph[Value]) OutboundNodes(key Value) ([]Value, error)
OutboundNodes returns the nodes that are outbound from the node for the key.
Returns error if there is no node for the key
func (*ComparableGraph[Value]) TopoSort ¶ added in v1.32.0
func (g *ComparableGraph[Value]) TopoSort(start Value) ([]Value, error)
TopoSort topologically sorts the nodes in the Graph starting at the given key.
Returns a *CycleError if there is a cycle in the graph.
func (*ComparableGraph[Value]) WalkEdges ¶ added in v1.32.0
func (g *ComparableGraph[Value]) WalkEdges(f func(Value, Value) error) error
WalkEdges visits each edge in the Graph starting at the source keys.
f is called for each directed edge. The first argument is the source node, the second is the destination node.
Returns a *CycleError if there is a cycle in the graph.
func (*ComparableGraph[Value]) WalkNodes ¶ added in v1.32.0
func (g *ComparableGraph[Value]) WalkNodes(f func(Value, []Value, []Value) error) error
WalkNodes visited each node in the Graph based on insertion order.
f is called for each node. The first argument is the key for the node, the second argument is all inbound edges, the third argument is all outbound edges.
type CycleError ¶
type CycleError[Key comparable] struct { Keys []Key }
CycleError is an error if the Graph had a cycle.
type Graph ¶
type Graph[Key comparable, Value any] struct { // contains filtered or unexported fields }
Graph is a directed acyclic graph structure.
func NewGraph ¶
func NewGraph[Key comparable, Value any](toKey func(Value) Key) *Graph[Key, Value]
NewGraph returns a new Graph for an any Value.
The toKey function must convert a Value to a unique comparable key type. It is up to the caller to make sure that the key is unique on a per-value basis.
This constructor must be used when initializing a Graph.
TODO FUTURE: It really stinks that we have to use the constructor. We have what amounts to silent errors now below with functions that don't return an error. We should figure out a way to do this properly, or perhaps just panic if we don't use the constructor.
func (*Graph[Key, Value]) AddEdge ¶
func (g *Graph[Key, Value]) AddEdge(from Value, to Value)
AddEdge adds an edge.
func (*Graph[Key, Value]) AddNode ¶
func (g *Graph[Key, Value]) AddNode(value Value)
AddNode adds a node.
func (*Graph[Key, Value]) ContainsNode ¶
ContainsNode returns true if the graph contains the given node.
func (*Graph[Key, Value]) DOTString ¶ added in v1.22.0
DOTString returns a DOT representation of the graph.
valueToString is used to print out the label for each node.
func (*Graph[Key, Value]) InboundNodes ¶ added in v1.32.0
InboundNodes returns the nodes that are inbound to the node for the key.
Returns error if there is no node for the key
func (*Graph[Key, Value]) NumEdges ¶ added in v1.23.0
NumNodes returns the number of edges in the graph.
func (*Graph[Key, Value]) NumNodes ¶ added in v1.23.0
NumNodes returns the number of nodes in the graph.
func (*Graph[Key, Value]) OutboundNodes ¶ added in v1.32.0
OutboundNodes returns the nodes that are outbound from the node for the key.
Returns error if there is no node for the key
func (*Graph[Key, Value]) TopoSort ¶
TopoSort topologically sorts the nodes in the Graph starting at the given key.
Returns a *CycleError if there is a cycle in the graph.
func (*Graph[Key, Value]) WalkEdges ¶ added in v1.23.0
WalkEdges visits each edge in the Graph starting at the source keys.
f is called for each directed edge. The first argument is the source node, the second is the destination node.
Returns a *CycleError if there is a cycle in the graph.
Source Files
Directories