Documentation
¶
Overview ¶
Package graph contains the graph data structure to represent dependency graphs. Nodes are fmt.Stringers, and are uniquely identified by their String() method. Edges don't have a public interface, but the various graph.*Edge methods work with them.
Contains utility functions for printing graphs that work with every implementation of graph.Interface.
Index ¶
- func PrintDepTree(graph Interface, start Node)
- func PrintFullDepTree(graph Interface)
- func WriteDot(graph Interface, writer io.Writer)
- func WriteGraph(graph Interface, writer io.Writer, syntax *syntax.Syntax)
- type Graph
- func (g *Graph) AddEdge(source, target string)
- func (g *Graph) AddEdgeAndNodes(source, target Node)
- func (g *Graph) AddNode(node Node, targetNames ...string)
- func (g *Graph) AddNodes(nodes ...Node)
- func (g *Graph) Copy() Interface
- func (g *Graph) FromScanner(scanner *bufio.Scanner, syntaxes ...*syntax.Syntax) (*Graph, error)
- func (g *Graph) GetDependants(node string) []Node
- func (g *Graph) GetDependencies(node string) []Node
- func (g *Graph) GetDependencyGraph(nodename string) *Graph
- func (g *Graph) GetNode(name string) Node
- func (g *Graph) GetNodes() []Node
- func (g *Graph) HasEdge(source, target string) bool
- func (g *Graph) RemoveEdge(source, target string) bool
- func (g *Graph) RemoveNode(name string) bool
- func (g *Graph) String() string
- type Interface
- type Node
- type Synced
- func (g *Synced) AddEdge(source, target string)
- func (g *Synced) AddEdgeAndNodes(source, target Node)
- func (g *Synced) AddNode(node Node, targetNames ...string)
- func (g *Synced) AddNodes(nodes ...Node)
- func (g *Synced) Copy() Interface
- func (g *Synced) FromScanner(scanner *bufio.Scanner, syntaxes ...*syntax.Syntax) (*Synced, error)
- func (g *Synced) GetDependants(node string) []Node
- func (g *Synced) GetDependencies(node string) []Node
- func (g *Synced) GetDependencyGraph(nodename string) *Graph
- func (g *Synced) GetNode(name string) Node
- func (g *Synced) GetNodes() []Node
- func (g *Synced) HasEdge(source, target string) bool
- func (g *Synced) RemoveEdge(source, target string) bool
- func (g *Synced) RemoveNode(name string) bool
- func (g *Synced) String() string
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func PrintDepTree ¶
PrintDepTree pretty prints the dependency tree of the specified startNode to stdout.
func PrintFullDepTree ¶
func PrintFullDepTree(graph Interface)
PrintFullDepTree prints the dependency tree of the whole graph to stdout.
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph represents the dependency graph in memory. Reades and writes at the same time are not concurrency-safe and therefore need to be synchronized. Checkout graph.Synced for a thread-safe version of Graph. It satisfies the graph.Interface and fmt.Stringer interfaces. The zero value is an uninitialized graph, use graph.New() to get an initialized Graph.
This implementation prefers fast node lookups and edge removals over dependency lookups.
func New ¶
New returns a freshly initialized, ready-to-use Graph. It takes an optional first parameter specifying the capacity of nodes that the Graph will contain, and an optional second uint specifying the number of edges it will hold.
func (*Graph) AddEdge ¶
AddEdge adds an edge from the source Node to the target Node to the graph.
This operation takes constant time, O(1).
func (*Graph) AddEdgeAndNodes ¶
AddEdgeAndNodes adds a new edge from source to target to the Graph. The nodes are added to the Graph if they were not present.
This operation takes constant time, O(1).
func (*Graph) AddNode ¶
AddNode adds the node with edges to the nodes with the given target names to this graph.
This operation takes constant time, O(1) (but proportional to the number of targetsNames).
func (*Graph) AddNodes ¶
AddNodes adds the given nodes to this graph.
This operation takes constant time, O(1) (but proportional to the number of new nodes).
func (*Graph) Copy ¶
Copy returns a deep copy of the Graph.
This operation takes time proportional to the sum of the number of nodes and the number of edges in g, O(n+e).
func (*Graph) FromScanner ¶
FromScanner reads data from the given scanner, building up the dependency tree.
func (*Graph) GetDependants ¶
GetDependants returns a slice containing all dependants of the Node with the given string. The Graph contains an edge from each item in dependants to the Node.
This operation takes time proportional to the number of nodes in g, O(n).
func (*Graph) GetDependencies ¶
GetDependencies returns a slice containing all dependencies of the Node with the given string. The Graph contains an edge from the Node to each item in the returned dependencies.
This operation takes time proportional to the number of nodes in g, O(n).
func (*Graph) GetDependencyGraph ¶
GetDependencyGraph builds the dependency graph for the node. Returns nil if no node with the given name was found in g.
This operation takes time proportional to product of the number of nodes and the number of edges in g, O(n*e).
func (*Graph) GetNode ¶
GetNode returns the Node with the specified name, or nil if the name couldn't be found in g.
This operation takes constant time, O(1).
func (*Graph) GetNodes ¶
GetNodes returns all Node objects saved in the Graph as a slice. If it is empty, an empty slice is returned.
This operation takes time proportional to the number of nodes in g, O(n).
func (*Graph) HasEdge ¶
HasEdge returns true if g has an edge from the source Node to the target Node, false otherwise.
This operation takes constant time, O(1).
func (*Graph) RemoveEdge ¶
RemoveEdge removes the edge from the source Node to the target Node. Returns false if the graph didn't have an edge from source to target, true otherwise.
This operation takes constant time, O(1).
func (*Graph) RemoveNode ¶
RemoveNode removes the Node with the given name including its edges from the graph. Returns false if the graph didn't have a matching Node, true otherwise.
This operation takes time proportional to the number of nodes in g, O(n).
type Interface ¶
type Interface interface {
// AddNode adds the node with edges to the nodes with the given target names to this graph.
AddNode(node Node, targetNames ...string)
// GetNode returns the Node with the specified name, or nil if the name couldn't be found in the graph.
GetNode(name string) Node
// GetNodes returns all Node objects saved in the graph as a slice. If the graph is empty, an empty slice is returned.
GetNodes() []Node
// RemoveNode removes the Node with the given name including its edges from the graph.
// Returns false if the graph didn't have a matching Node, true otherwise.
RemoveNode(name string) bool
// AddEdge adds an edge from the source Node to the target Node to the graph.
AddEdge(source, target string)
// HasEdge returns true if the graph has an edge from the source Node to the target Node, false otherwise.
HasEdge(source, target string) bool
// RemoveEdge removes the edge from the source Node to the target Node.
// Returns false if the graph didn't have an edge from source to target, true otherwise.
RemoveEdge(source, target string) bool
// GetDependencies returns a slice containing all dependencies of the Node with the given string.
GetDependencies(node string) []Node
// GetDependants returns a slice containing all dependants of the Node with the given string.
GetDependants(node string) []Node
// Copy returns a deep copy of the graph.
Copy() Interface
}
Interface defines a basic graph-like data structure. The stored data is accessed by the String() method, so every Node needs to implement fmt.Stringer.
type Node ¶
Node represents a single data point stored in a Graph. Its String() method should return a unique string identifier. The String() method call should be fast (ideally inline), as it will be called often!
type Synced ¶
Synced embeds a graph.Graph and synchronizes read and write access with an embedded sync.RWMutex, making it concurrency-safe. It satisfies the graph.Interface and fmt.Stringer interfaces. The zero value is an uninitialized graph, use graph.NewSynced() to get an initialized graph.Synced.
This implementation prefers fast node lookups and edge removals over dependency lookups.
func NewSynced ¶
NewSynced returns a freshly initialized, ready-to-use graph.Synced It takes an optional first parameter specifying the capacity of nodes that the Graph will contain, and an optional second uint specifying the number of edges it will hold.
func (*Synced) AddEdge ¶
AddEdge adds an edge from the source Node to the target Node to the graph.
This operation takes constant time, O(1).
func (*Synced) AddEdgeAndNodes ¶
AddEdgeAndNodes adds a new edge from source to target to the Graph. The nodes are added to the Graph if they were not present.
This operation takes constant time, O(1).
func (*Synced) AddNode ¶
AddNode adds the node with edges to the nodes with the given target names to this graph.
This operation takes constant time, O(1) (but proportional to the number of targetsNames).
func (*Synced) AddNodes ¶
AddNodes adds the given nodes to this graph.
This operation takes constant time, O(1) (but proportional to the number of new nodes).
func (*Synced) Copy ¶
Copy returns a deep copy of the graph.Synced.
This operation takes time proportional to the sum of the number of nodes and the number of edges in g, O(n+e).
func (*Synced) FromScanner ¶
FromScanner reads data from the given scanner, building up the dependency tree. This uses multiple workers to concurrently write the read edges.
func (*Synced) GetDependants ¶
GetDependants returns a slice containing all dependants of the Node with the given string. The graph.Synced contains an edge from each item in dependants to the Node.
This operation takes time proportional to the number of nodes in g, O(n).
func (*Synced) GetDependencies ¶
GetDependencies returns a slice containing all dependencies of the Node with the given string. The graph.Synced contains an edge from the Node to each item in the returned dependencies.
This operation takes time proportional to the number of nodes in g, O(n).
func (*Synced) GetDependencyGraph ¶
GetDependencyGraph builds the dependency graph for the node. Returns nil if no node with the given name was found in g. If read/write access to the dependency graph shall be thread-safe as well you need to embed it in a Synced!
This operation takes time proportional to the product of the number of nodes and the number of edges in g, O(n*e).
func (*Synced) GetNode ¶
GetNode returns the Node with the specified name, or nil if the name couldn't be found in g.
This operation takes constant time, O(1).
func (*Synced) GetNodes ¶
GetNodes returns all Node objects saved in the Graph as a slice. If it is empty, an empty slice is returned.
This operation takes time proportional to the number of nodes in g, O(n).
func (*Synced) HasEdge ¶
HasEdge returns true if g has an edge from the source Node to the target Node, false otherwise.
This operation takes constant time, O(1).
func (*Synced) RemoveEdge ¶
RemoveEdge removes the edge from the source Node to the target Node. Returns false if the graph didn't have an edge from source to target, true otherwise.
This operation takes constant time, O(1).
func (*Synced) RemoveNode ¶
RemoveNode removes the Node with the given name including its edges from the graph. Returns false if the graph didn't have a matching Node, true otherwise.
This operation takes time proportional to the number of nodes in g, O(n).
Source Files