/usr/share/gocode/src/github.com/ctdk/goiardi/digraph/util.go is in golang-github-ctdk-goiardi-dev 0.11.2-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | package digraph
// DepthFirstWalk performs a depth-first traversal of the nodes
// that can be reached from the initial input set. The callback is
// invoked for each visited node, and may return false to prevent
// vising any children of the current node
func DepthFirstWalk(node Node, cb func(n Node) bool) {
frontier := []Node{node}
seen := make(map[Node]struct{})
for len(frontier) > 0 {
// Pop the current node
n := len(frontier)
current := frontier[n-1]
frontier = frontier[:n-1]
// Check for potential cycle
if _, ok := seen[current]; ok {
continue
}
seen[current] = struct{}{}
// Visit with the callback
if !cb(current) {
continue
}
// Add any new edges to visit, in reverse order
edges := current.Edges()
for i := len(edges) - 1; i >= 0; i-- {
frontier = append(frontier, edges[i].Tail())
}
}
}
// FilterDegree returns only the nodes with the desired
// degree. This can be used with OutDegree or InDegree
func FilterDegree(degree int, degrees map[Node]int) []Node {
var matching []Node
for n, d := range degrees {
if d == degree {
matching = append(matching, n)
}
}
return matching
}
// InDegree is used to compute the in-degree of nodes
func InDegree(nodes []Node) map[Node]int {
degree := make(map[Node]int, len(nodes))
for _, n := range nodes {
if _, ok := degree[n]; !ok {
degree[n] = 0
}
for _, e := range n.Edges() {
degree[e.Tail()]++
}
}
return degree
}
// OutDegree is used to compute the in-degree of nodes
func OutDegree(nodes []Node) map[Node]int {
degree := make(map[Node]int, len(nodes))
for _, n := range nodes {
degree[n] = len(n.Edges())
}
return degree
}
// Sinks is used to get the nodes with out-degree of 0
func Sinks(nodes []Node) []Node {
return FilterDegree(0, OutDegree(nodes))
}
// Sources is used to get the nodes with in-degree of 0
func Sources(nodes []Node) []Node {
return FilterDegree(0, InDegree(nodes))
}
// Unreachable starts at a given start node, performs
// a DFS from there, and returns the set of unreachable nodes.
func Unreachable(start Node, nodes []Node) []Node {
// DFS from the start ndoe
frontier := []Node{start}
seen := make(map[Node]struct{})
for len(frontier) > 0 {
// Pop the current node
n := len(frontier)
current := frontier[n-1]
frontier = frontier[:n-1]
// Check for potential cycle
if _, ok := seen[current]; ok {
continue
}
seen[current] = struct{}{}
// Add any new edges to visit, in reverse order
edges := current.Edges()
for i := len(edges) - 1; i >= 0; i-- {
frontier = append(frontier, edges[i].Tail())
}
}
// Check for any unseen nodes
var unseen []Node
for _, node := range nodes {
if _, ok := seen[node]; !ok {
unseen = append(unseen, node)
}
}
return unseen
}
|