Documentation
¶
Overview ¶
Package pgraph represents the internal "pointer graph" that we use.
Index ¶
- Variables
- 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) CopyWithFn(vertexCpFn func(Vertex) (Vertex, error)) (*Graph, error)
- func (g *Graph) DFS(start Vertex) []Vertex
- func (g *Graph) DeleteEdge(xe ...Edge)
- func (g *Graph) DeleteVertex(xv ...Vertex)
- func (g *Graph) DisconnectedGraphs() ([]*Graph, error)
- func (g *Graph) Edges() []Edge
- func (obj *Graph) ExecGraphviz(filename string) error
- func (g *Graph) FilterGraph(vertices []Vertex) (*Graph, error)
- func (g *Graph) FilterGraphWithFn(fn func(Vertex) (bool, error)) (*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 (obj *Graph) Graphviz() 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) LookupEdge(e Edge) (Vertex, Vertex, bool)
- 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) VertexSwap(vs map[Vertex]Vertex) (*Graph, error)
- func (g *Graph) Vertices() []Vertex
- func (g *Graph) VerticesChan() chan Vertex
- func (g *Graph) VerticesSorted() []Vertex
- type Graphviz
- type GraphvizOpts
- type Graphvizable
- type SelfVertex
- type SimpleEdge
- type Vertex
- type VertexSlice
Constants ¶
This section is empty.
Variables ¶
var ErrNotAcyclic = errors.New("not a dag")
ErrNotAcyclic specifies that a particular graph was not found to be a dag.
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) Copy ¶
Copy makes a copy of the graph struct. This doesn't copy the individual vertices or edges, those pointers remain untouched. This lets you modify the structure of the graph without changing the original. If you also want to copy the nodes, please use CopyWithFn instead.
func (*Graph) CopyWithFn ¶
CopyWithFn makes a copy of the graph struct but lets you provide a function to copy the vertices. TODO: add tests
func (*Graph) DeleteEdge ¶
DeleteEdge uses variadic input to delete all the listed edges from the graph.
func (*Graph) DeleteVertex ¶
DeleteVertex uses variadic input to delete all listed vertices 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) FilterGraphWithFn ¶
FilterGraphWithFn builds a new graph containing only vertices which match. It uses a user defined function to match. That function must return true on match, and an error if anything goes wrong.
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) LookupEdge ¶
LookupEdge takes an edge and tries to find the vertex pair that connects it. If it finds a match, then it returns the pair and true. Otherwise it returns false.
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) VertexSwap ¶
VertexSwap swaps vertices in a graph. It returns a new graph with the same structure but with replacements done according to the translation map passed in. If a vertex is not found in the graph, then it is not substituted. TODO: add tests
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 Graphviz ¶
type Graphviz struct {
// Name is the display name of the graph. If specified it overrides an
// amalgamation of any graph names shown.
Name string
// Graphs is a collection of graphs to print together and the associated
// options that should be used to format them during display.
Graphs map[*Graph]*GraphvizOpts
// Filter is the graphviz program to run. The default is "dot".
Filter string
// Filename is the output location for the graph.
Filename string
// Hostname is used as a suffix to the filename when specified.
Hostname string
}
Graphviz adds some visualization features for pgraph.
func (*Graphviz) Exec ¶
Exec writes out the graphviz data and runs the correct graphviz filter command.
func (*Graphviz) Text ¶
Text outputs the graph in graphviz format. https://en.wikipedia.org/wiki/DOT_%28graph_description_language%29
type GraphvizOpts ¶
type GraphvizOpts struct {
// Style represents the node style string.
Style string
// Font represents the node font to use.
// TODO: implement me
Font string
}
GraphvizOpts specifies some formatting for each graph.
type Graphvizable ¶
type Graphvizable interface {
// ExecGraphviz runs graphviz and stores the result at this absolute
// path. It (awkwardly) can be used by someone expecting either a
// filename, or a directory. The filename scenario should be used if you
// are expecting a single .dot output file. The directory scenario
// should be used if you are expecting a series of .dot graphs.
// Directories must end with a trailing slash. A filename passed will
// get this location overwritten if there is something already there. If
// the string is empty, it might create a file in a temporary directory
// somewhere.
ExecGraphviz(filename string) error
}
Graphvizable is a simple interface to handle the common signature for this useful graphviz exec method that is used in debugging. Expect that this signature might change if the authors find a different variant more useful.
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