pgraph

package
v0.0.0-...-b7948c7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 17, 2017 License: AGPL-3.0 Imports: 16 Imported by: 0

Documentation

Overview

Package pgraph represents the internal "pointer graph" that we use.

Package pgraph represents the internal "pointer graph" that we use.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func EdgeContains 

func EdgeContains(needle *Edge, haystack []*Edge) bool

EdgeContains is an "in array" function to test for an edge in a slice of edges.

func VertexContains 

func VertexContains(needle *Vertex, haystack []*Vertex) bool

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 NewEdge 

func NewEdge(name string) *Edge

NewEdge returns a new graph edge struct.

func (*Edge) Refresh 

func (obj *Edge) Refresh() bool

Refresh returns the pending refresh status of this edge.

func (*Edge) SetRefresh 

func (obj *Edge) SetRefresh(b bool)

SetRefresh sets the pending refresh status of this edge.

type Flags 

type Flags struct {
	Debug bool
}

Flags contains specific constants used by the graph.

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 NewGraph 

func NewGraph(name string) *Graph

NewGraph builds a new graph.

func (*Graph) AddEdge 

func (g *Graph) AddEdge(v1, v2 *Vertex, e *Edge)

AddEdge adds a directed edge to the graph from v1 to v2.

func (*Graph) AddVertex 

func (g *Graph) AddVertex(xv ...*Vertex)

AddVertex uses variadic input to add all listed vertices to the graph

func (*Graph) AssociateData 

func (g *Graph) AssociateData(data *resources.Data)

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 

func (g *Graph) BackPoke(v *Vertex)

BackPoke pokes the pre-requisites that are stale and need to run before I can run.

func (*Graph) Copy 

func (g *Graph) Copy() *Graph

Copy makes a copy of the graph struct

func (*Graph) DFS 

func (g *Graph) DFS(start *Vertex) []*Vertex

DFS returns a depth first search for the graph, starting at the input vertex.

func (*Graph) DeleteEdge 

func (g *Graph) DeleteEdge(e *Edge)

DeleteEdge deletes a particular edge from the graph. FIXME: add test cases

func (*Graph) DeleteVertex 

func (g *Graph) DeleteVertex(v *Vertex)

DeleteVertex deletes a particular vertex from the graph.

func (*Graph) ExecGraphviz 

func (g *Graph) ExecGraphviz(program, filename string) error

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 

func (g *Graph) FilterGraph(name string, vertices []*Vertex) *Graph

FilterGraph builds a new graph containing only vertices from the list.

func (*Graph) GetDisconnectedGraphs 

func (g *Graph) GetDisconnectedGraphs() chan *Graph

GetDisconnectedGraphs returns a channel containing the N disconnected graphs in our main graph. We can then process each of these in parallel.

func (*Graph) GetName 

func (g *Graph) GetName() string

GetName returns the name of the graph.

func (*Graph) GetVertexMatch 

func (g *Graph) GetVertexMatch(obj resources.Res) *Vertex

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 

func (g *Graph) GetVertices() []*Vertex

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 

func (g *Graph) GetVerticesChan() chan *Vertex

GetVerticesChan returns a channel of all vertices in the graph.

func (*Graph) GetVerticesSorted 

func (g *Graph) GetVerticesSorted() []*Vertex

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 

func (g *Graph) GraphEdges(v *Vertex) []*Edge

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 

func (g *Graph) GraphSync(oldGraph *Graph) (*Graph, error)

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 

func (g *Graph) GraphVertices(v *Vertex) []*Vertex

GraphVertices returns an array (slice) of all vertices that connect to vertex v. This is the union of IncomingGraphVertices and OutgoingGraphVertices.

func (*Graph) Graphviz 

func (g *Graph) Graphviz() (out string)

Graphviz outputs the graph in graphviz format. https://en.wikipedia.org/wiki/DOT_%28graph_description_language%29

func (*Graph) HasVertex 

func (g *Graph) HasVertex(v *Vertex) bool

HasVertex returns if the input vertex exists in the graph.

func (*Graph) InDegree 

func (g *Graph) InDegree() map[*Vertex]int

InDegree returns the count of vertices that point to me in one big lookup map.

func (*Graph) IncomingGraphEdges 

func (g *Graph) IncomingGraphEdges(v *Vertex) []*Edge

IncomingGraphEdges returns all of the edges that point to vertex v (??? -> v).

func (*Graph) IncomingGraphVertices 

func (g *Graph) IncomingGraphVertices(v *Vertex) []*Vertex

IncomingGraphVertices returns an array (slice) of all directed vertices to vertex v (??? -> v). OKTimestamp should probably use this.

func (*Graph) NumEdges 

func (g *Graph) NumEdges() int

NumEdges returns the number of edges in the graph.

func (*Graph) NumVertices 

func (g *Graph) NumVertices() int

NumVertices returns the number of vertices in the graph.

func (*Graph) OKTimestamp 

func (g *Graph) OKTimestamp(v *Vertex) bool

OKTimestamp returns true if this element can run right now?

func (*Graph) OutDegree 

func (g *Graph) OutDegree() map[*Vertex]int

OutDegree returns the count of vertices that point away in one big lookup map.

func (*Graph) OutgoingGraphEdges 

func (g *Graph) OutgoingGraphEdges(v *Vertex) []*Edge

OutgoingGraphEdges returns all of the edges that point from vertex v (v -> ???).

func (*Graph) OutgoingGraphVertices 

func (g *Graph) OutgoingGraphVertices(v *Vertex) []*Vertex

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) Poke 

func (g *Graph) Poke(v *Vertex) error

Poke tells nodes after me in the dependency graph that they need to refresh.

func (*Graph) Process 

func (g *Graph) Process(v *Vertex) error

Process is the primary function to execute for a particular vertex in the graph.

func (*Graph) Reachability 

func (g *Graph) Reachability(a, b *Vertex) []*Vertex

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 

func (g *Graph) RefreshPending(v *Vertex) bool

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 

func (g *Graph) SetDownstreamRefresh(v *Vertex, b bool)

SetDownstreamRefresh sets the refresh value to any downstream vertices.

func (*Graph) SetName 

func (g *Graph) SetName(name string)

SetName sets the name of the graph.

func (*Graph) SetUpstreamRefresh 

func (g *Graph) SetUpstreamRefresh(v *Vertex, b bool)

SetUpstreamRefresh sets the refresh value to any upstream vertices.

func (*Graph) Start 

func (g *Graph) Start(first bool)

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) String 

func (g *Graph) String() string

String makes the graph pretty print.

func (*Graph) TopologicalSort 

func (g *Graph) TopologicalSort() ([]*Vertex, error)

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!

func (*Graph) Worker 

func (g *Graph) Worker(v *Vertex) error

Worker is the common run frontend of the vertex. It handles all of the retry and retry delay common code, and ultimately returns the final status of this vertex execution.

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 

type Vertex struct {
	resources.Res // anonymous field
	// contains filtered or unexported fields
}

Vertex is the primary vertex struct in this library.

func NewVertex 

func NewVertex(r resources.Res) *Vertex

NewVertex returns a new graph vertex struct with a contained resource.

func Reverse 

func Reverse(vs []*Vertex) []*Vertex

Reverse reverses a list of vertices.

func (*Vertex) GetTimestamp 

func (v *Vertex) GetTimestamp() int64

GetTimestamp returns the timestamp of a vertex

func (*Vertex) String 

func (v *Vertex) String() string

String returns the canonical form for a vertex

func (*Vertex) UpdateTimestamp 

func (v *Vertex) UpdateTimestamp() int64

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)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.