dag

Documentation

Overview

Package dag implements a Directed Acyclic Graph for Package dependencies.

Index

• type DAG
  • func NewMapDag() DAG
• type MapDag
  • func (d *MapDag) AddEdge(from string, to Node) (bool, error)
  • func (d *MapDag) AddEdges(edges map[string][]Node) ([]Node, error)
  • func (d *MapDag) AddNode(node Node) error
  • func (d *MapDag) AddNodes(nodes ...Node) error
  • func (d *MapDag) AddOrUpdateNodes(nodes ...Node)
  • func (d *MapDag) GetNode(identifier string) (Node, error)
  • func (d *MapDag) Init(nodes []Node) ([]Node, error)
  • func (d *MapDag) NodeExists(identifier string) bool
  • func (d *MapDag) NodeNeighbors(identifier string) ([]Node, error)
  • func (d *MapDag) Sort() ([]string, error)
  • func (d *MapDag) TraceNode(identifier string) (map[string]Node, error)
• type NewDAGFn
• type Node

Types

type DAG

type DAG interface {
	Init(nodes []Node) ([]Node, error)
	AddNode(Node) error
	AddNodes(...Node) error
	AddOrUpdateNodes(...Node)
	GetNode(identifier string) (Node, error)
	AddEdge(from string, to Node) (bool, error)
	AddEdges(edges map[string][]Node) ([]Node, error)
	NodeExists(identifier string) bool
	NodeNeighbors(identifier string) ([]Node, error)
	TraceNode(identifier string) (map[string]Node, error)
	Sort() ([]string, error)
}

DAG is a Directed Acyclic Graph.

func NewMapDag

func NewMapDag() DAG

NewMapDag creates a new MapDag.

type MapDag

type MapDag struct {
	// contains filtered or unexported fields
}

MapDag is a directed acyclic graph implementation that uses a map for its underlying data structure.

func (*MapDag) AddEdge

func (d *MapDag) AddEdge(from string, to Node) (bool, error)

AddEdge adds an edge to the graph.

func (*MapDag) AddEdges

func (d *MapDag) AddEdges(edges map[string][]Node) ([]Node, error)

AddEdges adds edges to the graph.

func (*MapDag) AddNode

func (d *MapDag) AddNode(node Node) error

AddNode adds a node to the graph.

func (*MapDag) AddNodes

func (d *MapDag) AddNodes(nodes ...Node) error

AddNodes adds nodes to the graph.

func (*MapDag) AddOrUpdateNodes

func (d *MapDag) AddOrUpdateNodes(nodes ...Node)

AddOrUpdateNodes adds new nodes or updates the existing ones with the same identifier.

func (*MapDag) GetNode

func (d *MapDag) GetNode(identifier string) (Node, error)

GetNode returns a node in the dag.

func (*MapDag) Init

func (d *MapDag) Init(nodes []Node) ([]Node, error)

Init initializes a MapDag and implies missing destination nodes. Any implied nodes are returned. Any existing nodes are cleared.

func (*MapDag) NodeExists

func (d *MapDag) NodeExists(identifier string) bool

NodeExists checks whether a node exists.

func (*MapDag) NodeNeighbors

func (d *MapDag) NodeNeighbors(identifier string) ([]Node, error)

NodeNeighbors returns a node's neighbors.

func (*MapDag) Sort

func (d *MapDag) Sort() ([]string, error)

Sort performs topological sort on the graph.

func (*MapDag) TraceNode

func (d *MapDag) TraceNode(identifier string) (map[string]Node, error)

TraceNode returns a node's neighbors and all transitive neighbors using depth first search.

type NewDAGFn

type NewDAGFn func() DAG

NewDAGFn is a function that returns a DAG.

type Node

type Node interface {
	Identifier() string
	Neighbors() []Node

	// Node implementations should be careful to establish uniqueness of
	// neighbors in their AddNeighbors method or risk counting a neighbor
	// multiple times.
	AddNeighbors(...Node) error
}

Node is a node in DAG.