mirror of
https://github.com/openfaas/faasd.git
synced 2025-06-09 00:16:46 +00:00
5b92e7793d
Graph logic moves into depgraph package and makes internal fields inaccessible. Completes feedback from @LucasRoesler from previous PR where the dependency graph was added for 0.9.1 Signed-off-by: Alex Ellis (OpenFaaS Ltd) <alexellis2@gmail.com>
107 lines
2.2 KiB
Go
107 lines
2.2 KiB
Go
package depgraph
|
|
|
|
import "log"
|
|
|
|
// Node represents a node in a Graph with
|
|
// 0 to many edges
|
|
type Node struct {
|
|
Name string
|
|
Edges []*Node
|
|
}
|
|
|
|
// Graph is a collection of nodes
|
|
type Graph struct {
|
|
nodes []*Node
|
|
}
|
|
|
|
func NewDepgraph() *Graph {
|
|
return &Graph{
|
|
nodes: []*Node{},
|
|
}
|
|
}
|
|
|
|
// Nodes returns the nodes within the graph
|
|
func (g *Graph) Nodes() []*Node {
|
|
return g.nodes
|
|
}
|
|
|
|
// Contains returns true if the target Node is found
|
|
// in its list
|
|
func (g *Graph) Contains(target *Node) bool {
|
|
for _, g := range g.nodes {
|
|
if g.Name == target.Name {
|
|
return true
|
|
}
|
|
}
|
|
|
|
return false
|
|
}
|
|
|
|
// Add places a Node into the current Graph
|
|
func (g *Graph) Add(target *Node) {
|
|
g.nodes = append(g.nodes, target)
|
|
}
|
|
|
|
// Remove deletes a target Node reference from the
|
|
// list of nodes in the graph
|
|
func (g *Graph) Remove(target *Node) {
|
|
var found *int
|
|
for i, n := range g.nodes {
|
|
if n == target {
|
|
found = &i
|
|
break
|
|
}
|
|
}
|
|
|
|
if found != nil {
|
|
g.nodes = append(g.nodes[:*found], g.nodes[*found+1:]...)
|
|
}
|
|
}
|
|
|
|
// Resolve retruns a list of node names in order of their dependencies.
|
|
// A use case may be for determining the correct order to install
|
|
// software packages, or to start services.
|
|
// Based upon the algorithm described by Ferry Boender in the following article
|
|
// https://www.electricmonk.nl/log/2008/08/07/dependency-resolving-algorithm/
|
|
func (g *Graph) Resolve() []string {
|
|
resolved := &Graph{}
|
|
unresolved := &Graph{}
|
|
for _, node := range g.nodes {
|
|
resolve(node, resolved, unresolved)
|
|
}
|
|
|
|
order := []string{}
|
|
|
|
for _, node := range resolved.Nodes() {
|
|
order = append(order, node.Name)
|
|
}
|
|
|
|
return order
|
|
}
|
|
|
|
// resolve mutates the resolved graph for a given starting
|
|
// node. The unresolved graph is used to detect a circular graph
|
|
// error and will throw a panic. This can be caught with a resolve
|
|
// in a go routine.
|
|
func resolve(node *Node, resolved, unresolved *Graph) {
|
|
unresolved.Add(node)
|
|
|
|
for _, edge := range node.Edges {
|
|
|
|
if !resolved.Contains(edge) && unresolved.Contains(edge) {
|
|
log.Panicf("edge: %s may be a circular dependency", edge.Name)
|
|
}
|
|
|
|
resolve(edge, resolved, unresolved)
|
|
}
|
|
|
|
for _, r := range resolved.nodes {
|
|
if r.Name == node.Name {
|
|
return
|
|
}
|
|
}
|
|
|
|
resolved.Add(node)
|
|
unresolved.Remove(node)
|
|
}
|