Documentation
¶
Overview ¶
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 Edge
- type Graph
- func (g *Graph) AddEdge(v1, v2 Vertex, e Edge)
- func (g *Graph) AddEdgeGraphVertex(graph *Graph, vertex Vertex, edgeGenFn func(v1, v2 Vertex) Edge)
- func (g *Graph) AddEdgeGraphVertexLight(graph *Graph, vertex Vertex, edgeGenFn func(v1, v2 Vertex) Edge)
- func (g *Graph) AddEdgeVertexGraph(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge)
- func (g *Graph) AddEdgeVertexGraphLight(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge)
- func (g *Graph) AddGraph(graph *Graph)
- func (g *Graph) AddVertex(xv ...Vertex)
- func (g *Graph) Adjacency() map[Vertex]map[Vertex]Edge
- 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) DisconnectedGraphs() ([]*Graph, error)
- func (g *Graph) Edges() []Edge
- func (g *Graph) ExecGraphviz(program, filename, hostname string) error
- func (g *Graph) FilterGraph(name string, vertices []Vertex) (*Graph, error)
- func (g *Graph) FindEdge(v1, v2 Vertex) Edge
- func (g *Graph) GetName() string
- func (g *Graph) GraphCmp(graph *Graph, vertexCmpFn func(Vertex, Vertex) (bool, error), ...) error
- func (g *Graph) GraphEdges(v Vertex) []Edge
- func (obj *Graph) GraphSync(newGraph *Graph, vertexCmpFn func(Vertex, Vertex) (bool, error), ...) 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) Init() error
- func (g *Graph) Logf(logf func(format string, v ...interface{}))
- func (g *Graph) NumEdges() int
- func (g *Graph) NumVertices() int
- func (g *Graph) OutDegree() map[Vertex]int
- func (g *Graph) OutgoingGraphEdges(v Vertex) []Edge
- func (g *Graph) OutgoingGraphVertices(v Vertex) []Vertex
- func (g *Graph) Reachability(a, b Vertex) ([]Vertex, error)
- func (g *Graph) SetName(name string)
- func (g *Graph) SetValue(key string, val interface{})
- func (g *Graph) Sprint() string
- func (g *Graph) String() string
- func (g *Graph) TopologicalSort() ([]Vertex, error)
- func (g *Graph) Value(key string) (interface{}, bool)
- func (g *Graph) VertexMatchFn(fn func(Vertex) (bool, error)) (Vertex, error)
- func (g *Graph) Vertices() []Vertex
- func (g *Graph) VerticesChan() chan Vertex
- func (g *Graph) VerticesSorted() []Vertex
- type SelfVertex
- type SimpleEdge
- 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 Edge ¶
Edge is the primary edge struct in this library. It can be anything that implements Stringer. The string output must be stable and unique in a graph.
type Graph ¶
type Graph struct {
Name string
// 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) AddEdgeGraphVertex ¶
AddEdgeGraphVertex adds a directed edge to the vertex from a graph. This is useful for flattening the relationship between a subgraph and an existing graph, without having to run the subgraph recursively. It adds the maximum number of edges, creating a relationship from every vertex.
func (*Graph) AddEdgeGraphVertexLight ¶
func (g *Graph) AddEdgeGraphVertexLight(graph *Graph, vertex Vertex, edgeGenFn func(v1, v2 Vertex) Edge)
AddEdgeGraphVertexLight adds a directed edge to the vertex from a graph. This is useful for flattening the relationship between a subgraph and an existing graph, without having to run the subgraph recursively. It adds the minimum number of edges, creating a relationship from the vertices with outdegree equal to zero.
func (*Graph) AddEdgeVertexGraph ¶
AddEdgeVertexGraph adds a directed edge to the graph from a vertex. This is useful for flattening the relationship between a subgraph and an existing graph, without having to run the subgraph recursively. It adds the maximum number of edges, creating a relationship to every vertex.
func (*Graph) AddEdgeVertexGraphLight ¶
func (g *Graph) AddEdgeVertexGraphLight(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge)
AddEdgeVertexGraphLight adds a directed edge to the graph from a vertex. This is useful for flattening the relationship between a subgraph and an existing graph, without having to run the subgraph recursively. It adds the minimum number of edges, creating a relationship to the vertices with indegree equal to zero.
func (*Graph) AddGraph ¶
AddGraph adds the set of edges and vertices of a graph to the existing graph.
func (*Graph) Adjacency ¶
Adjacency returns the adjacency map representing this graph. This is useful for users who which to operate on the raw data structure more efficiently. This works because maps are reference types so we can edit this at will.
func (*Graph) DeleteEdge ¶
DeleteEdge deletes a particular edge from the graph.
func (*Graph) DeleteVertex ¶
DeleteVertex deletes a particular vertex from the graph.
func (*Graph) DisconnectedGraphs ¶
DisconnectedGraphs returns a list containing the N disconnected graphs.
func (*Graph) Edges ¶
Edges returns a randomly sorted slice of all edges in the graph. The order is random, because the map implementation is intentionally so!
func (*Graph) ExecGraphviz ¶
ExecGraphviz writes out the graphviz data and runs the correct graphviz filter command.
func (*Graph) FilterGraph ¶
FilterGraph builds a new graph containing only vertices from the list.
func (*Graph) GraphCmp ¶
func (g *Graph) GraphCmp(graph *Graph, vertexCmpFn func(Vertex, Vertex) (bool, error), edgeCmpFn func(Edge, Edge) (bool, error)) error
GraphCmp compares the topology of this graph to another and returns nil if they're equal. It uses a user defined function to compare topologically equivalent vertices, and edges. FIXME: add more test cases
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) GraphSync ¶
func (obj *Graph) GraphSync(newGraph *Graph, vertexCmpFn func(Vertex, Vertex) (bool, error), vertexAddFn func(Vertex) error, vertexRemoveFn func(Vertex) error, edgeCmpFn func(Edge, Edge) (bool, error)) error
GraphSync updates the Graph so that it matches the newGraph. It leaves identical elements alone so that they don't need to be refreshed. It tries to mutate existing elements into new ones, if they support this. This updates the Graph on success only. If it fails, then the graph won't have been modified. FIXME: should we do this with copies of the vertex resources?
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. Eg: (??? -> v).
func (*Graph) IncomingGraphVertices ¶
IncomingGraphVertices returns an array (slice) of all directed vertices to vertex v (??? -> v). OKTimestamp should probably use this.
func (*Graph) Logf ¶
Logf logs a printed representation of the graph with the logf of your choice. This is helpful to ensure each line of logged output has the prefix you want.
func (*Graph) NumVertices ¶
NumVertices returns the number of vertices in the graph.
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. Eg: (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) 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) SetValue ¶
SetValue sets a value to be stored alongside the graph in a particular key.
func (*Graph) Sprint ¶
Sprint prints a full graph in textual form out to a string. To log this you might want to use Logf, which will keep everything aligned with whatever your logging prefix is. This function returns the result in a deterministic order.
func (*Graph) TopologicalSort ¶
TopologicalSort returns the sort of graph vertices in that order. It is based on descriptions and code from wikipedia and rosetta code. TODO: add memoization, and cache invalidation to speed this up :)
func (*Graph) VertexMatchFn ¶
VertexMatchFn searches for a vertex in the graph and returns the vertex if one matches. It uses a user defined function to match. That function must return true on match, and an error if anything goes wrong.
func (*Graph) Vertices ¶
Vertices returns a randomly sorted slice of all vertices in the graph. The order is random, because the map implementation is intentionally so!
func (*Graph) VerticesChan ¶
VerticesChan returns a channel of all vertices in the graph.
func (*Graph) VerticesSorted ¶
VerticesSorted 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.
type SelfVertex ¶
SelfVertex is a vertex that stores a graph pointer to the graph that it's on. This is useful if you want to pass around a graph with a vertex cursor on it.
func (*SelfVertex) String ¶
func (obj *SelfVertex) String() string
String is a required method of the Vertex interface that we must fulfill.
type SimpleEdge ¶
type SimpleEdge struct {
Name string
}
SimpleEdge is a simple edge struct that you can use instead of building one.
func (*SimpleEdge) String ¶
func (obj *SimpleEdge) String() string
String is a required method of the Edge interface that we must fulfill.
type Vertex ¶
Vertex is the primary vertex struct in this library. It can be anything that implements Stringer. The string output must be stable and unique in a graph.
type VertexSlice ¶
type VertexSlice []Vertex
VertexSlice is a linear list of vertices. It can be sorted.
func (VertexSlice) Len ¶
func (vs VertexSlice) Len() int
Len returns the length of the slice of vertices.
func (VertexSlice) Less ¶
func (vs VertexSlice) Less(i, j int) bool
Less returns the smaller element in the sort order.
func (VertexSlice) Swap ¶
func (vs VertexSlice) Swap(i, j int)
Swap swaps two elements in the slice.
Source Files