package pgraph

import "github.com/purpleidea/mgmt/pgraph"

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

Index

Variables 

var ErrNotAcyclic = errors.New("not a dag")

ErrNotAcyclic specifies that a particular graph was not found to be a dag.

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 Edge 

type Edge interface {
	fmt.Stringer // String() string
}

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 NewGraph 

func NewGraph(name string) (*Graph, error)

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

func (g *Graph) AddEdgeGraphVertex(graph *Graph, vertex Vertex, edgeGenFn func(v1, v2 Vertex) Edge)

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 

func (g *Graph) AddEdgeVertexGraph(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge)

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 

func (g *Graph) AddGraph(graph *Graph)

AddGraph adds the set of edges and vertices of a graph to the existing graph.

func (*Graph) AddVertex 

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

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

func (*Graph) Adjacency 

func (g *Graph) Adjacency() map[Vertex]map[Vertex]Edge

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 

func (g *Graph) Copy() *Graph

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 

func (g *Graph) CopyWithFn(vertexCpFn func(Vertex) (Vertex, error)) (*Graph, error)

CopyWithFn makes a copy of the graph struct but lets you provide a function to copy the vertices. TODO: add tests

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(xe ...Edge)

DeleteEdge uses variadic input to delete all the listed edges from the graph.

func (*Graph) DeleteVertex 

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

DeleteVertex uses variadic input to delete all listed vertices from the graph.

func (*Graph) DeterministicTopologicalSort 

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

DeterministicTopologicalSort returns the sort of graph vertices in a stable topological sort order. It's slower than the TopologicalSort implementation, but guarantees that two identical graphs produce the same sort each time. TODO: add memoization, and cache invalidation to speed this up :)

func (*Graph) DisconnectedGraphs 

func (g *Graph) DisconnectedGraphs() ([]*Graph, error)

DisconnectedGraphs returns a list containing the N disconnected graphs.

func (*Graph) Edges 

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

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 

func (obj *Graph) ExecGraphviz(filename string) error

ExecGraphviz writes out the graphviz data and runs the correct graphviz filter command.

func (*Graph) FilterGraph 

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

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

func (*Graph) FilterGraphWithFn 

func (g *Graph) FilterGraphWithFn(fn func(Vertex) (bool, error)) (*Graph, error)

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

func (g *Graph) FindEdge(v1, v2 Vertex) Edge

FindEdge returns the edge from v1 -> v2 if it exists. Otherwise nil.

func (*Graph) GetName 

func (g *Graph) GetName() string

GetName returns the name of the graph.

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 

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

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 (obj *Graph) Graphviz() 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. Eg: (??? -> 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) Init 

func (g *Graph) Init() error

Init initializes the graph which populates all the internal structures.

func (*Graph) Logf 

func (g *Graph) Logf(logf func(format string, v ...interface{}))

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 

func (g *Graph) LookupEdge(e Edge) (Vertex, Vertex, bool)

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) 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) 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. Eg: (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) Reachability 

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

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

func (g *Graph) SetName(name string)

SetName sets the name of the graph.

func (*Graph) SetValue 

func (g *Graph) SetValue(key string, val interface{})

SetValue sets a value to be stored alongside the graph in a particular key.

func (*Graph) Sprint 

func (g *Graph) Sprint() string

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) 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. It is based on descriptions and code from wikipedia and rosetta code. TODO: add memoization, and cache invalidation to speed this up :)

func (*Graph) Value 

func (g *Graph) Value(key string) (interface{}, bool)

Value returns a value stored alongside the graph in a particular key.

func (*Graph) VertexMatchFn 

func (g *Graph) VertexMatchFn(fn func(Vertex) (bool, error)) (Vertex, error)

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 

func (g *Graph) VertexSwap(vs map[Vertex]Vertex) (*Graph, error)

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 

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

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 

func (g *Graph) VerticesChan() chan Vertex

VerticesChan returns a channel of all vertices in the graph.

func (*Graph) VerticesSorted 

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

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 

func (obj *Graphviz) Exec() error

Exec writes out the graphviz data and runs the correct graphviz filter command.

func (*Graphviz) Text 

func (obj *Graphviz) Text() string

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 

type SelfVertex struct {
	Name  string
	Graph *Graph // it's up to you to manage the cursor safety
}

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 

type Vertex interface {
	fmt.Stringer // String() string
}

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.

func Reverse 

func Reverse(vs []Vertex) []Vertex

Reverse reverses a list of vertices.

func Sort 

func Sort(vs []Vertex) []Vertex

Sort the list of vertices and return a copy without modifying the input.

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

func (vs VertexSlice) Sort()

Sort is a convenience method.

func (VertexSlice) Swap 

func (vs VertexSlice) Swap(i, j int)

Swap swaps two elements in the slice.

Source Files

graphsync.go graphviz.go pgraph.go selfvertex.go simpleedge.go subgraph.go

Version
v0.0.0-20250322185616-c50a578426f1 (latest)
Published
Mar 22, 2025
Platform
linux/amd64
Imports
10 packages
Last checked
4 days ago –

Tools for package owners.