Documentation ¶
Overview ¶
Package pgraph represents the internal "pointer graph" that we use.
Package pgraph represents the internal "pointer graph" that we use.
Index ¶
- func EdgeContains(needle *Edge, haystack []*Edge) bool
- func VertexContains(needle *Vertex, haystack []*Vertex) bool
- type AutoGrouper
- type Edge
- type Flags
- type Graph
- func (g *Graph) AddEdge(v1, v2 *Vertex, e *Edge)
- func (g *Graph) AddVertex(xv ...*Vertex)
- func (g *Graph) AssociateData(data *resources.Data)
- func (g *Graph) AutoEdges()
- func (g *Graph) AutoGroup()
- func (g *Graph) BackPoke(v *Vertex)
- func (g *Graph) Copy() *Graph
- func (g *Graph) DFS(start *Vertex) []*Vertex
- func (g *Graph) DeleteEdge(e *Edge)
- func (g *Graph) DeleteVertex(v *Vertex)
- func (g *Graph) ExecGraphviz(program, filename string) error
- func (g *Graph) Exit()
- func (g *Graph) FilterGraph(name string, vertices []*Vertex) *Graph
- func (g *Graph) GetDisconnectedGraphs() chan *Graph
- func (g *Graph) GetName() string
- func (g *Graph) GetVertexMatch(obj resources.Res) *Vertex
- func (g *Graph) GetVertices() []*Vertex
- func (g *Graph) GetVerticesChan() chan *Vertex
- func (g *Graph) GetVerticesSorted() []*Vertex
- func (g *Graph) GraphEdges(v *Vertex) []*Edge
- func (g *Graph) GraphMetas() []*resources.MetaParams
- func (g *Graph) GraphSync(oldGraph *Graph) (*Graph, error)
- func (g *Graph) GraphVertices(v *Vertex) []*Vertex
- func (g *Graph) Graphviz() (out string)
- func (g *Graph) HasVertex(v *Vertex) bool
- func (g *Graph) InDegree() map[*Vertex]int
- func (g *Graph) IncomingGraphEdges(v *Vertex) []*Edge
- func (g *Graph) IncomingGraphVertices(v *Vertex) []*Vertex
- func (g *Graph) NumEdges() int
- func (g *Graph) NumVertices() int
- func (g *Graph) OKTimestamp(v *Vertex) bool
- func (g *Graph) OutDegree() map[*Vertex]int
- func (g *Graph) OutgoingGraphEdges(v *Vertex) []*Edge
- func (g *Graph) OutgoingGraphVertices(v *Vertex) []*Vertex
- func (g *Graph) Pause()
- func (g *Graph) Poke(v *Vertex) error
- func (g *Graph) Process(v *Vertex) error
- func (g *Graph) Reachability(a, b *Vertex) []*Vertex
- func (g *Graph) RefreshPending(v *Vertex) bool
- func (g *Graph) SetDownstreamRefresh(v *Vertex, b bool)
- func (g *Graph) SetName(name string)
- func (g *Graph) SetUpstreamRefresh(v *Vertex, b bool)
- func (g *Graph) Start(first bool)
- func (g *Graph) String() string
- func (g *Graph) TopologicalSort() ([]*Vertex, error)
- func (g *Graph) VertexMerge(v1, v2 *Vertex, vertexMergeFn func(*Vertex, *Vertex) (*Vertex, error), ...) error
- func (g *Graph) Worker(v *Vertex) error
- type SentinelErr
- type Vertex
- type VertexSlice
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func EdgeContains ¶
EdgeContains is an "in array" function to test for an edge in a slice of edges.
func VertexContains ¶
VertexContains is an "in array" function to test for a vertex in a slice of vertices.
Types ¶
type AutoGrouper ¶
type AutoGrouper interface {
// contains filtered or unexported methods
}
AutoGrouper is the required interface to implement for an autogroup algorithm
type Edge ¶
type Edge struct { Name string Notify bool // should we send a refresh notification along this edge? // contains filtered or unexported fields }
Edge is the primary edge struct in this library.
func (*Edge) SetRefresh ¶
SetRefresh sets the pending refresh status of this edge.
type Graph ¶
type Graph struct { Name string Adjacency map[*Vertex]map[*Vertex]*Edge // *Vertex -> *Vertex (edge) Flags Flags // contains filtered or unexported fields }
Graph is the graph structure in this library. The graph abstract data type (ADT) is defined as follows: * the directed graph arrows point from left to right ( -> ) * the arrows point away from their dependencies (eg: arrows mean "before") * IOW, you might see package -> file -> service (where package runs first) * This is also the direction that the notify should happen in...
func (*Graph) AssociateData ¶
AssociateData associates some data with the object in the graph in question.
func (*Graph) AutoEdges ¶
func (g *Graph) AutoEdges()
AutoEdges adds the automatic edges to the graph.
func (*Graph) AutoGroup ¶
func (g *Graph) AutoGroup()
AutoGroup runs the auto grouping on the graph and prints out log messages
func (*Graph) BackPoke ¶
BackPoke pokes the pre-requisites that are stale and need to run before I can run.
func (*Graph) DeleteEdge ¶
DeleteEdge deletes a particular edge from the graph. FIXME: add test cases
func (*Graph) DeleteVertex ¶
DeleteVertex deletes a particular vertex from the graph.
func (*Graph) ExecGraphviz ¶
ExecGraphviz writes out the graphviz data and runs the correct graphviz filter command.
func (*Graph) Exit ¶
func (g *Graph) Exit()
Exit sends exit events to the graph in a topological sort order.
func (*Graph) FilterGraph ¶
FilterGraph builds a new graph containing only vertices from the list.
func (*Graph) GetDisconnectedGraphs ¶
GetDisconnectedGraphs returns a channel containing the N disconnected graphs in our main graph. We can then process each of these in parallel.
func (*Graph) GetVertexMatch ¶
GetVertexMatch searches for an equivalent resource in the graph and returns the vertex it is found in, or nil if not found.
func (*Graph) GetVertices ¶
GetVertices returns a randomly sorted slice of all vertices in the graph The order is random, because the map implementation is intentionally so!
func (*Graph) GetVerticesChan ¶
GetVerticesChan returns a channel of all vertices in the graph.
func (*Graph) GetVerticesSorted ¶
GetVerticesSorted returns a sorted slice of all vertices in the graph The order is sorted by String() to avoid the non-determinism in the map type
func (*Graph) GraphEdges ¶
GraphEdges returns an array (slice) of all edges that connect to vertex v. This is the union of IncomingGraphEdges and OutgoingGraphEdges.
func (*Graph) GraphMetas ¶
func (g *Graph) GraphMetas() []*resources.MetaParams
GraphMetas returns a list of pointers to each of the resource MetaParams.
func (*Graph) GraphSync ¶
GraphSync updates the oldGraph so that it matches the newGraph receiver. It leaves identical elements alone so that they don't need to be refreshed. FIXME: add test cases
func (*Graph) GraphVertices ¶
GraphVertices returns an array (slice) of all vertices that connect to vertex v. This is the union of IncomingGraphVertices and OutgoingGraphVertices.
func (*Graph) Graphviz ¶
Graphviz outputs the graph in graphviz format. https://en.wikipedia.org/wiki/DOT_%28graph_description_language%29
func (*Graph) InDegree ¶
InDegree returns the count of vertices that point to me in one big lookup map.
func (*Graph) IncomingGraphEdges ¶
IncomingGraphEdges returns all of the edges that point to vertex v (??? -> v).
func (*Graph) IncomingGraphVertices ¶
IncomingGraphVertices returns an array (slice) of all directed vertices to vertex v (??? -> v). OKTimestamp should probably use this.
func (*Graph) NumVertices ¶
NumVertices returns the number of vertices in the graph.
func (*Graph) OKTimestamp ¶
OKTimestamp returns true if this element can run right now?
func (*Graph) OutDegree ¶
OutDegree returns the count of vertices that point away in one big lookup map.
func (*Graph) OutgoingGraphEdges ¶
OutgoingGraphEdges returns all of the edges that point from vertex v (v -> ???).
func (*Graph) OutgoingGraphVertices ¶
OutgoingGraphVertices returns an array (slice) of all vertices that vertex v points to (v -> ???). Poke should probably use this.
func (*Graph) Pause ¶
func (g *Graph) Pause()
Pause sends pause events to the graph in a topological sort order.
func (*Graph) Process ¶
Process is the primary function to execute for a particular vertex in the graph.
func (*Graph) Reachability ¶
Reachability finds the shortest path in a DAG from a to b, and returns the slice of vertices that matched this particular path including both a and b. It returns nil if a or b is nil, and returns empty list if no path is found. Since there could be more than one possible result for this operation, we arbitrarily choose one of the shortest possible. As a result, this should actually return a tree if we cared about correctness. This operates by a recursive algorithm; a more efficient version is likely. If you don't give this function a DAG, you might cause infinite recursion!
func (*Graph) RefreshPending ¶
RefreshPending determines if any previous nodes have a refresh pending here. If this is true, it means I am expected to apply a refresh when I next run.
func (*Graph) SetDownstreamRefresh ¶
SetDownstreamRefresh sets the refresh value to any downstream vertices.
func (*Graph) SetUpstreamRefresh ¶
SetUpstreamRefresh sets the refresh value to any upstream vertices.
func (*Graph) Start ¶
Start is a main kick to start the graph. It goes through in reverse topological sort order so that events can't hit un-started vertices.
func (*Graph) TopologicalSort ¶
TopologicalSort returns the sort of graph vertices in that order. based on descriptions and code from wikipedia and rosetta code TODO: add memoization, and cache invalidation to speed this up :)
func (*Graph) VertexMerge ¶
func (g *Graph) VertexMerge(v1, v2 *Vertex, vertexMergeFn func(*Vertex, *Vertex) (*Vertex, error), edgeMergeFn func(*Edge, *Edge) *Edge) error
VertexMerge merges v2 into v1 by reattaching the edges where appropriate, and then by deleting v2 from the graph. Since more than one edge between two vertices is not allowed, duplicate edges are merged as well. an edge merge function can be provided if you'd like to control how you merge the edges!
type SentinelErr ¶
type SentinelErr struct {
// contains filtered or unexported fields
}
SentinelErr is a sentinal as an error type that wraps an arbitrary error.
func (*SentinelErr) Error ¶
func (obj *SentinelErr) Error() string
Error is the required method to fulfill the error type.
type Vertex ¶
Vertex is the primary vertex struct in this library.
func (*Vertex) GetTimestamp ¶
GetTimestamp returns the timestamp of a vertex
func (*Vertex) UpdateTimestamp ¶
UpdateTimestamp updates the timestamp on a vertex and returns the new value
type VertexSlice ¶
type VertexSlice []*Vertex
VertexSlice is a linear list of vertices. It can be sorted.
func (VertexSlice) Len ¶
func (vs VertexSlice) Len() int
func (VertexSlice) Less ¶
func (vs VertexSlice) Less(i, j int) bool
func (VertexSlice) Swap ¶
func (vs VertexSlice) Swap(i, j int)