graph

Documentation

Overview

This package provides a object sorting functionality based on the explicit "depends-on" annotation, and implicit object dependencies like namespaces and CRD's.

This package provides a graph data struture and graph functionality using ObjMetadata as vertices in the graph.

Index

• func HydrateSetList(idSetList []object.ObjMetadataSet, objs object.UnstructuredSet) []object.UnstructuredSet
• func ReverseSetList(setList []object.UnstructuredSet)
• func ReverseSortObjs(objs object.UnstructuredSet) ([]object.UnstructuredSet, error)
• func SortObjs(objs object.UnstructuredSet) ([]object.UnstructuredSet, error)
• type CyclicDependencyError
  • func (cde CyclicDependencyError) Error() string
• type DuplicateDependencyError
  • func (dde DuplicateDependencyError) Error() string
• type Edge
• type ExternalDependencyError
  • func (ede ExternalDependencyError) Error() string
• type Graph
  • func DependencyGraph(objs object.UnstructuredSet) (*Graph, error)
  • func New() *Graph
  • func (g *Graph) AddEdge(from object.ObjMetadata, to object.ObjMetadata)
  • func (g *Graph) AddVertex(v object.ObjMetadata)
  • func (g *Graph) Dependencies(from object.ObjMetadata) object.ObjMetadataSet
  • func (g *Graph) Dependents(to object.ObjMetadata) object.ObjMetadataSet
  • func (g *Graph) Size() int
  • func (g *Graph) Sort() ([]object.ObjMetadataSet, error)
• type SortableEdges
  • func (a SortableEdges) Len() int
  • func (a SortableEdges) Less(i, j int) bool
  • func (a SortableEdges) Swap(i, j int)

Functions

func HydrateSetList

func HydrateSetList(idSetList []object.ObjMetadataSet, objs object.UnstructuredSet) []object.UnstructuredSet

HydrateSetList takes a list of sets of ids and a set of objects and returns a list of set of objects. The output set list will be the same order as the input set list, but with IDs converted into Objects. Any IDs that do not match objects in the provided object set will be skipped (filtered) in the output.

func ReverseSetList

func ReverseSetList(setList []object.UnstructuredSet)

ReverseSetList deep reverses of a list of object lists

func ReverseSortObjs

func ReverseSortObjs(objs object.UnstructuredSet) ([]object.UnstructuredSet, error)

ReverseSortObjs is the same as SortObjs but using reverse ordering.

func SortObjs

func SortObjs(objs object.UnstructuredSet) ([]object.UnstructuredSet, error)

SortObjs returns a slice of the sets of objects to apply (in order). Each of the objects in an apply set is applied together. The order of the returned applied sets is a topological ordering of the sets to apply. Returns an single empty apply set if there are no objects to apply.

Types

type CyclicDependencyError

type CyclicDependencyError struct {
	Edges []Edge
}

CyclicDependencyError represents a cycle in the graph, making topological sort impossible.

func (CyclicDependencyError) Error

func (cde CyclicDependencyError) Error() string

type DuplicateDependencyError

type DuplicateDependencyError struct {
	Edge Edge
}

DuplicateDependencyError represents an invalid depends-on annotation with duplicate references.

func (DuplicateDependencyError) Error

func (dde DuplicateDependencyError) Error() string

type Edge

type Edge struct {
	From object.ObjMetadata
	To   object.ObjMetadata
}

Edge encapsulates a pair of vertices describing a directed edge.

type ExternalDependencyError

type ExternalDependencyError struct {
	Edge Edge
}

ExternalDependencyError represents an invalid graph edge caused by an object that is not in the object set.

func (ExternalDependencyError) Error

func (ede ExternalDependencyError) Error() string

type Graph

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

Graph is contains a directed set of edges, implemented as an adjacency list (map key is "from" vertex, slice are "to" vertices).

func DependencyGraph

func DependencyGraph(objs object.UnstructuredSet) (*Graph, error)

DependencyGraph returns a new graph, populated with the supplied objects as vetices and edges built from their dependencies.

func New

func New() *Graph

New returns a pointer to an empty Graph data structure.

func (*Graph) AddEdge

func (g *Graph) AddEdge(from object.ObjMetadata, to object.ObjMetadata)

AddEdge adds a edge from one ObjMetadata vertex to another. The direction of the edge is "from" -> "to".

func (*Graph) AddVertex

func (g *Graph) AddVertex(v object.ObjMetadata)

AddVertex adds an ObjMetadata vertex to the graph, with an initial empty set of edges from added vertex.

func (*Graph) Dependencies

func (g *Graph) Dependencies(from object.ObjMetadata) object.ObjMetadataSet

Dependencies returns the objects that this object depends on.

func (*Graph) Dependents

func (g *Graph) Dependents(to object.ObjMetadata) object.ObjMetadataSet

Dependents returns the objects that depend on this object.

func (*Graph) Size

func (g *Graph) Size() int

Size returns the number of vertices in the graph.

func (*Graph) Sort

func (g *Graph) Sort() ([]object.ObjMetadataSet, error)

Sort returns the ordered set of vertices after a topological sort.

type SortableEdges

type SortableEdges []Edge

SortableEdges sorts a list of edges alphanumerically by From and then To.

func (SortableEdges) Len

func (a SortableEdges) Len() int

func (SortableEdges) Less

func (a SortableEdges) Less(i, j int) bool

func (SortableEdges) Swap

func (a SortableEdges) Swap(i, j int)