graph

Documentation

Index

• type Cycle
• type Edge
  • func (e *Edge[T]) From() graph.Node
  • func (e *Edge[T]) ReversedEdge() graph.Edge
  • func (e *Edge[T]) To() graph.Node
• type EmptyCallbacks
• type Graph
  • func MakeTestGraph(spec [][]int) *Graph[int]
  • func NewGraph[T any]() *Graph[T]
  • func (g *Graph[T]) AddFromToEdge(fromId string, toIds ...string) error
  • func (g *Graph[T]) AddNode(node *Node[T])
  • func (g *Graph[T]) AllNodes() []*Node[T]
  • func (g *Graph[T]) Edge(uid, vid int64) graph.Edge
  • func (g *Graph[T]) From(id int64) graph.Nodes
  • func (g *Graph[T]) FromId(id string) []*Node[T]
  • func (g *Graph[T]) Get(id string) *Node[T]
  • func (g *Graph[T]) GetNodesWithoutParents() []*Node[T]
  • func (g *Graph[T]) Has(nodeId string) bool
  • func (g *Graph[T]) HasEdgeBetween(xid, yid int64) bool
  • func (g *Graph[T]) HasEdgeFromTo(uid, vid int64) bool
  • func (g *Graph[T]) Load(ids []string, parser NodeParser[T], callbacks LoadCallbacks[T]) error
  • func (g *Graph[T]) Node(id int64) graph.Node
  • func (g *Graph[T]) Nodes() graph.Nodes
  • func (g *Graph[T]) RemoveCycles(nodes []*Node[T]) []Cycle
  • func (g *Graph[T]) RemoveCyclesStartingFromNode(node *Node[T]) []Cycle
  • func (g *Graph[T]) RemoveElementaryCycles() []Cycle
  • func (g *Graph[T]) RemoveFromToEdge(fromId string, toId string)
  • func (g *Graph[T]) To(id int64) graph.Nodes
  • func (g *Graph[T]) ToId(id string) []*Node[T]
• type LoadCallbacks
• type Node
  • func MakeNode[T any](id string, data T) *Node[T]
  • func (n *Node[T]) AddErrors(err ...error)
  • func (n *Node[T]) ID() int64
• type NodeParser
• type NodeParserBuilder
• type Nodes
  • func NewNodesIterator[T any](nodes []*Node[T]) *Nodes[T]
  • func (n *Nodes[T]) Len() int
  • func (n *Nodes[T]) Next() bool
  • func (n *Nodes[T]) Node() graph.Node
  • func (n *Nodes[T]) Reset()
• type StdErrCallbacks
  • func NewStdErrCallbacks[T any](display func(node *Node[T]) string) *StdErrCallbacks[T]
• type TestCallbacks
• type TestParser
  • func (t *TestParser) Deps(n *Node[[]int]) ([]*Node[[]int], error)
  • func (t *TestParser) Node(id string) (*Node[[]int], error)

Types

type Cycle

type Cycle struct {
	Cause [2]string
	Stack []string
}

type Edge

type Edge[T any] struct {
	// contains filtered or unexported fields
}

func (*Edge[T]) From

func (e *Edge[T]) From() graph.Node

func (*Edge[T]) ReversedEdge

func (e *Edge[T]) ReversedEdge() graph.Edge

func (*Edge[T]) To

func (e *Edge[T]) To() graph.Node

type EmptyCallbacks

type EmptyCallbacks[T any] struct{}

type Graph

type Graph[T any] struct {
	// contains filtered or unexported fields
}

func MakeTestGraph

func MakeTestGraph(spec [][]int) *Graph[int]

func NewGraph

func NewGraph[T any]() *Graph[T]

func (*Graph[T]) AddFromToEdge

func (g *Graph[T]) AddFromToEdge(fromId string, toIds ...string) error

func (*Graph[T]) AddNode

func (g *Graph[T]) AddNode(node *Node[T])

func (*Graph[T]) AllNodes

func (g *Graph[T]) AllNodes() []*Node[T]

func (*Graph[T]) Edge

func (g *Graph[T]) Edge(uid, vid int64) graph.Edge

func (*Graph[T]) From

func (g *Graph[T]) From(id int64) graph.Nodes

func (*Graph[T]) FromId

func (g *Graph[T]) FromId(id string) []*Node[T]

FromId returns the nodes to which id can reach.

func (*Graph[T]) Get

func (g *Graph[T]) Get(id string) *Node[T]

func (*Graph[T]) GetNodesWithoutParents

func (g *Graph[T]) GetNodesWithoutParents() []*Node[T]

func (*Graph[T]) Has

func (g *Graph[T]) Has(nodeId string) bool

func (*Graph[T]) HasEdgeBetween

func (g *Graph[T]) HasEdgeBetween(xid, yid int64) bool

func (*Graph[T]) HasEdgeFromTo

func (g *Graph[T]) HasEdgeFromTo(uid, vid int64) bool

func (*Graph[T]) Load

func (g *Graph[T]) Load(ids []string, parser NodeParser[T], callbacks LoadCallbacks[T]) error

func (*Graph[T]) Node

func (g *Graph[T]) Node(id int64) graph.Node

func (*Graph[T]) Nodes

func (g *Graph[T]) Nodes() graph.Nodes

func (*Graph[T]) RemoveCycles

func (g *Graph[T]) RemoveCycles(nodes []*Node[T]) []Cycle

RemoveCycles removes all cycles in the graph, giving preference to cycles that start from the provided nodes.

func (*Graph[T]) RemoveCyclesStartingFromNode

func (g *Graph[T]) RemoveCyclesStartingFromNode(node *Node[T]) []Cycle

RemoveCyclesStartingFromNode removes cycles that appear in order while performing a depth first search from a certain node. Note that this may not remove all cycles in the graph.

func (*Graph[T]) RemoveElementaryCycles

func (g *Graph[T]) RemoveElementaryCycles() []Cycle

RemoveElementaryCycles removes all the elementary cycles in the graph. The result of this can be non-deterministic.

func (*Graph[T]) RemoveFromToEdge

func (g *Graph[T]) RemoveFromToEdge(fromId string, toId string)

func (*Graph[T]) To

func (g *Graph[T]) To(id int64) graph.Nodes

func (*Graph[T]) ToId

func (g *Graph[T]) ToId(id string) []*Node[T]

ToId returns the nodes from which id is reachable.

type LoadCallbacks

type LoadCallbacks[T any] interface {
	// contains filtered or unexported methods
}

type Node

type Node[T any] struct {
	// Id identifies the node with a string. This is typically the absolute path
	//  of a file in dep-tree.
	Id string
	// Errors This node might hold some errors that are worth rendering to the user.
	//  For example, if the node is a file, maybe it failed to be parsed.
	Errors []error
	// Data is a generic implementation-defined data bucket. Implementations can put
	//  whatever they want here.
	Data T
}

func MakeNode

func MakeNode[T any](id string, data T) *Node[T]

func (*Node[T]) AddErrors

func (n *Node[T]) AddErrors(err ...error)

func (*Node[T]) ID

func (n *Node[T]) ID() int64

type NodeParser

type NodeParser[T any] interface {
	Node(id string) (*Node[T], error)
	Deps(node *Node[T]) ([]*Node[T], error)
}

type NodeParserBuilder

type NodeParserBuilder[T any] func([]string) (NodeParser[T], error)

type Nodes

type Nodes[T any] struct {
	// contains filtered or unexported fields
}

func NewNodesIterator

func NewNodesIterator[T any](nodes []*Node[T]) *Nodes[T]

func (*Nodes[T]) Len

func (n *Nodes[T]) Len() int

func (*Nodes[T]) Next

func (n *Nodes[T]) Next() bool

func (*Nodes[T]) Node

func (n *Nodes[T]) Node() graph.Node

func (*Nodes[T]) Reset

func (n *Nodes[T]) Reset()

type StdErrCallbacks

type StdErrCallbacks[T any] struct {
	// contains filtered or unexported fields
}

func NewStdErrCallbacks

func NewStdErrCallbacks[T any](
	display func(node *Node[T]) string,
) *StdErrCallbacks[T]

type TestCallbacks

type TestCallbacks[T any] struct {
	// contains filtered or unexported fields
}

type TestParser

type TestParser struct {
	Spec [][]int
}

func (*TestParser) Deps

func (t *TestParser) Deps(n *Node[[]int]) ([]*Node[[]int], error)

func (*TestParser) Node

func (t *TestParser) Node(id string) (*Node[[]int], error)