dag

Documentation

Index

• type ComparableGraph
  • func NewComparableGraph[Value comparable]() *ComparableGraph[Value]
  • 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
  • func (c *CycleError[Key]) Error() string
• type Graph
  • func NewGraph[Key comparable, Value any](toKey func(Value) Key) *Graph[Key, Value]
  • 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

Types

type ComparableGraph

type ComparableGraph[Value comparable] struct {
	// contains filtered or unexported fields
}

ComparableGraph is a Graph that uses comparable Values.

func NewComparableGraph

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

func (g *ComparableGraph[Value]) AddEdge(from Value, to Value)

AddEdge adds an edge.

func (*ComparableGraph[Value]) AddNode

func (g *ComparableGraph[Value]) AddNode(value Value)

AddNode adds a node.

func (*ComparableGraph[Value]) ContainsNode

func (g *ComparableGraph[Value]) ContainsNode(key Value) bool

ContainsNode returns true if the graph contains the given node.

func (*ComparableGraph[Value]) DOTString

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.

https://graphviz.org/doc/info/lang.html

func (*ComparableGraph[Value]) Graph

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

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

func (g *ComparableGraph[Value]) NumEdges() int

NumNodes returns the number of edges in the graph.

func (*ComparableGraph[Value]) NumNodes

func (g *ComparableGraph[Value]) NumNodes() int

NumNodes returns the number of nodes in the graph.

func (*ComparableGraph[Value]) OutboundNodes

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

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

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

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.

func (*CycleError[Key]) Error

func (c *CycleError[Key]) Error() string

Error implements error.

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

func (g *Graph[Key, Value]) ContainsNode(key Key) bool

ContainsNode returns true if the graph contains the given node.

func (*Graph[Key, Value]) DOTString

func (g *Graph[Key, 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.

https://graphviz.org/doc/info/lang.html

func (*Graph[Key, Value]) InboundNodes

func (g *Graph[Key, Value]) InboundNodes(key Key) ([]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 (*Graph[Key, Value]) NumEdges

func (g *Graph[Key, Value]) NumEdges() int

NumNodes returns the number of edges in the graph.

func (*Graph[Key, Value]) NumNodes

func (g *Graph[Key, Value]) NumNodes() int

NumNodes returns the number of nodes in the graph.

func (*Graph[Key, Value]) OutboundNodes

func (g *Graph[Key, Value]) OutboundNodes(key Key) ([]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 (*Graph[Key, Value]) TopoSort

func (g *Graph[Key, Value]) TopoSort(start Key) ([]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 (*Graph[Key, Value]) WalkEdges

func (g *Graph[Key, 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 (*Graph[Key, Value]) WalkNodes

func (g *Graph[Key, 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.