Documentation
¶
Index ¶
- Variables
- type CoffmanGrahamSorter
- type DFSSorter
- type DirectedGraph
- func (g *DirectedGraph) AddEdge(from Node, to Node)
- func (g DirectedGraph) AddNode(node Node)
- func (g DirectedGraph) AddNodes(nodes ...Node)
- func (g *DirectedGraph) AdjacencyMatrix() map[Node]map[Node]bool
- func (g *DirectedGraph) CoffmanGrahamSort(width int) ([][]Node, error)
- func (g *DirectedGraph) Copy() *DirectedGraph
- func (g *DirectedGraph) DFSSort() ([]Node, error)
- func (g *DirectedGraph) DOTGraph() string
- func (g *DirectedGraph) EdgeCount() int
- func (g *DirectedGraph) EdgeExists(from Node, to Node) bool
- func (g *DirectedGraph) HasEdges(node Node) bool
- func (g *DirectedGraph) HasIncomingEdges(node Node) bool
- func (g *DirectedGraph) HasOutgoingEdges(node Node) bool
- func (g *DirectedGraph) IncomingEdgeCount(node Node) int
- func (g *DirectedGraph) IncomingEdges(node Node) []Node
- func (g *DirectedGraph) IsolatedNodes() []Node
- func (g DirectedGraph) NodeCount() int
- func (g DirectedGraph) NodeExists(node Node) bool
- func (g DirectedGraph) Nodes() []Node
- func (g *DirectedGraph) OutgoingEdgeCount(node Node) int
- func (g *DirectedGraph) OutgoingEdges(node Node) []Node
- func (g *DirectedGraph) RemoveEdge(from Node, to Node)
- func (g DirectedGraph) RemoveNode(node Node)
- func (g DirectedGraph) RemoveNodes(nodes ...Node)
- func (g *DirectedGraph) RemoveTransitives()
- func (g *DirectedGraph) RootNodes() []Node
- type Node
Constants ¶
This section is empty.
Variables ¶
var (
ErrCyclicGraph = errors.New("The graph cannot be cyclic")
)
Errors relating to the DFSSorter.
var (
ErrDependencyOrder = errors.New("The topological dependency order is incorrect")
)
Errors relating to the CoffmanGrahamSorter.
Functions ¶
This section is empty.
Types ¶
type CoffmanGrahamSorter ¶
type CoffmanGrahamSorter struct {
// contains filtered or unexported fields
}
CoffmanGrahamSorter sorts a graph's nodes into a sequence of levels, arranging so that a node which comes after another in the order is assigned to a lower level, and that a level never exceeds the width. See https://en.wikipedia.org/wiki/Coffman–Graham_algorithm
func NewCoffmanGrahamSorter ¶
func NewCoffmanGrahamSorter(graph *DirectedGraph, width int) *CoffmanGrahamSorter
NewCoffmanGrahamSorter returns a new Coffman-Graham sorter.
func (*CoffmanGrahamSorter) Sort ¶
func (s *CoffmanGrahamSorter) Sort() ([][]Node, error)
Sort returns the sorted nodes.
type DFSSorter ¶
type DFSSorter struct {
// contains filtered or unexported fields
}
DFSSorter topologically sorts a directed graph's nodes based on the directed edges between them using the Depth-first search algorithm.
func NewDFSSorter ¶
func NewDFSSorter(graph *DirectedGraph) *DFSSorter
NewDFSSorter returns a new DFS sorter.
type DirectedGraph ¶
type DirectedGraph struct {
// contains filtered or unexported fields
}
DirectedGraph is a graph supporting directed edges between nodes.
func NewDirectedGraph ¶
func NewDirectedGraph() *DirectedGraph
NewDirectedGraph creates a graph of nodes with directed edges.
func (*DirectedGraph) AddEdge ¶
func (g *DirectedGraph) AddEdge(from Node, to Node)
AddEdge adds the edge to the graph.
func (DirectedGraph) AddNode ¶
func (g DirectedGraph) AddNode(node Node)
AddNode inserts the specified node into the graph. A node can be any value, e.g. int, string, pointer to a struct, map etc. Duplicate nodes are ignored.
func (DirectedGraph) AddNodes ¶
func (g DirectedGraph) AddNodes(nodes ...Node)
AddNodes inserts the specified nodes into the graph. A node can be any value, e.g. int, string, pointer to a struct, map etc. Duplicate nodes are ignored.
func (*DirectedGraph) AdjacencyMatrix ¶
func (g *DirectedGraph) AdjacencyMatrix() map[Node]map[Node]bool
AdjacencyMatrix returns a matrix indicating whether pairs of nodes are adjacent or not within the graph.
func (*DirectedGraph) CoffmanGrahamSort ¶
func (g *DirectedGraph) CoffmanGrahamSort(width int) ([][]Node, error)
CoffmanGrahamSort sorts the graph's nodes into a sequence of levels, arranging so that a node which comes after another in the order is assigned to a lower level, and that a level never exceeds the specified width.
func (*DirectedGraph) Copy ¶
func (g *DirectedGraph) Copy() *DirectedGraph
Copy returns a clone of the directed graph.
func (*DirectedGraph) DFSSort ¶
func (g *DirectedGraph) DFSSort() ([]Node, error)
DFSSort returns the graph's nodes in topological order based on the directed edges between them using the Depth-first search algorithm.
func (*DirectedGraph) DOTGraph ¶
func (g *DirectedGraph) DOTGraph() string
DOTGraph returns a textual representation of the graph in the DOT graph description language.
func (*DirectedGraph) EdgeCount ¶
func (g *DirectedGraph) EdgeCount() int
EdgeCount returns the number of direced edges between nodes.
func (*DirectedGraph) EdgeExists ¶
func (g *DirectedGraph) EdgeExists(from Node, to Node) bool
EdgeExists checks whether the edge exists within the graph.
func (*DirectedGraph) HasEdges ¶
func (g *DirectedGraph) HasEdges(node Node) bool
HasEdges determines whether the graph contains any edges to or from the node.
func (*DirectedGraph) HasIncomingEdges ¶
func (g *DirectedGraph) HasIncomingEdges(node Node) bool
HasIncomingEdges checks whether the graph contains any directed edges pointing to the node.
func (*DirectedGraph) HasOutgoingEdges ¶
func (g *DirectedGraph) HasOutgoingEdges(node Node) bool
HasOutgoingEdges checks whether the graph contains any directed edges pointing from the node.
func (*DirectedGraph) IncomingEdgeCount ¶
func (g *DirectedGraph) IncomingEdgeCount(node Node) int
IncomingEdgeCount returns the number of edges pointing from the specified node (indegree).
func (*DirectedGraph) IncomingEdges ¶
func (g *DirectedGraph) IncomingEdges(node Node) []Node
IncomingEdges returns the nodes belonging to directed edges pointing towards the specified node.
func (*DirectedGraph) IsolatedNodes ¶
func (g *DirectedGraph) IsolatedNodes() []Node
IsolatedNodes finds independent nodes in the graph, i.e. those without edges.
func (DirectedGraph) NodeCount ¶
func (g DirectedGraph) NodeCount() int
NodeCount returns the number of nodes.
func (DirectedGraph) NodeExists ¶
NodeExists determines whether the specified node exists within the graph.
func (DirectedGraph) Nodes ¶
func (g DirectedGraph) Nodes() []Node
Nodes returns the graph's nodes. The slice is mutable for performance reasons but should not be mutated.
func (*DirectedGraph) OutgoingEdgeCount ¶
func (g *DirectedGraph) OutgoingEdgeCount(node Node) int
OutgoingEdgeCount returns the number of edges pointing from the specified node (outdegree).
func (*DirectedGraph) OutgoingEdges ¶
func (g *DirectedGraph) OutgoingEdges(node Node) []Node
OutgoingEdges returns the nodes belonging to directed edges pointing from the specified node.
func (*DirectedGraph) RemoveEdge ¶
func (g *DirectedGraph) RemoveEdge(from Node, to Node)
RemoveEdge removes the edge from the graph.
func (DirectedGraph) RemoveNode ¶
func (g DirectedGraph) RemoveNode(node Node)
RemoveNode removes the specified nodes from the graph. If the node does not exist within the graph the call will fail silently.
func (DirectedGraph) RemoveNodes ¶
func (g DirectedGraph) RemoveNodes(nodes ...Node)
RemoveNodes removes the specified nodes from the graph. If a node does not exist within the graph the call will fail silently.
func (*DirectedGraph) RemoveTransitives ¶
func (g *DirectedGraph) RemoveTransitives()
RemoveTransitives removes any transitive edges so that as fewest possible edges exist while matching the reachability of the original graph.
func (*DirectedGraph) RootNodes ¶
func (g *DirectedGraph) RootNodes() []Node
RootNodes finds the entry-point nodes to the graph, i.e. those without incoming edges.
Source Files
Directories