52 lines
979 B
Go
52 lines
979 B
Go
|
package workflow
|
||
|
|
|
||
|
|
// Splits a flat map representing a graph's parent > children relationships
|
||
|
|
// into an ordered slice of levels.
|
||
|
|
func SplitFlatTreeIntoGroups(flatTree map[string][]string) [][]string {
|
||
|
|
type TreeNode struct {
|
||
|
|
name string
|
||
|
|
level int
|
||
|
|
}
|
||
|
|
|
||
|
|
nodes := map[string]TreeNode{}
|
||
|
|
|
||
|
|
deepestLevel := 0
|
||
|
|
next := []string{""}
|
||
|
|
|
||
|
|
for len(next) > 0 {
|
||
|
|
current := next[0]
|
||
|
|
next = next[1:]
|
||
|
|
children := flatTree[current]
|
||
|
|
|
||
|
|
currentNode, found := nodes[current]
|
||
|
|
|
||
|
|
// The negative value represents the graph root.
|
||
|
|
currentLevel := -1
|
||
|
|
|
||
|
|
if found {
|
||
|
|
currentLevel = currentNode.level
|
||
|
|
}
|
||
|
|
|
||
|
|
for _, child := range children {
|
||
|
|
nodes[child] = TreeNode{
|
||
|
|
name: child,
|
||
|
|
level: currentLevel + 1,
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if deepestLevel < currentLevel {
|
||
|
|
deepestLevel = currentLevel
|
||
|
|
}
|
||
|
|
|
||
|
|
next = append(next, children...)
|
||
|
|
}
|
||
|
|
|
||
|
|
levels := make([][]string, deepestLevel+1)
|
||
|
|
|
||
|
|
for _, node := range nodes {
|
||
|
|
levels[node.level] = append(levels[node.level], node.name)
|
||
|
|
}
|
||
|
|
|
||
|
|
return levels
|
||
|
|
}
|