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 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 New() *Graph
  • func (g *Graph) AddEdge(from object.ObjMetadata, to object.ObjMetadata)
  • func (g *Graph) AddVertex(v object.ObjMetadata)
  • func (g *Graph) GetEdges() []Edge
  • func (g *Graph) GetVertices() 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 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 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) GetEdges

func (g *Graph) GetEdges() []Edge

GetEdges returns a sorted slice of directed graph edges (vertex pairs).

func (*Graph) GetVertices

func (g *Graph) GetVertices() object.ObjMetadataSet

GetVertices returns a sorted set of unique vertices in the graph.

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)