-
Notifications
You must be signed in to change notification settings - Fork 1
/
graph.go
94 lines (75 loc) · 1.86 KB
/
graph.go
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
package lib
import (
"sync"
)
func createEdge(x, y *ChangingResource) Edge {
if x.GetAction() == "create" {
return Edge{a: x, b: y}
}
return Edge{a: y, b: x}
}
type Edge struct {
a *ChangingResource
b *ChangingResource
}
func (e Edge) isValid() bool {
sameType := e.a.GetType() == e.b.GetType()
differentActions := e.a.GetAction() != e.b.GetAction()
return sameType && differentActions
}
func isValidSet(set []Edge) bool {
for _, edge := range set {
if !edge.isValid() {
return false
}
}
return true
}
func validEdgeCombinationsFor(nodes []*ChangingResource) [][]Edge {
if len(nodes)%2 != 0 {
nodes = append(nodes, nil)
}
channel := make(chan []Edge)
waitGroup := &sync.WaitGroup{}
waitGroup.Add(1)
go func() {
waitGroup.Wait()
close(channel)
}()
find(nodes, []Edge{}, channel, waitGroup)
var results [][]Edge
for edgeSet := range channel {
results = append(results, edgeSet)
}
return results
}
func find(nodes []*ChangingResource, current []Edge, channel chan []Edge, waitGroup *sync.WaitGroup) {
defer waitGroup.Done()
if !isValidSet(current) {
return
}
if len(nodes) < 2 {
if isValidSet(current) {
channel <- current
}
return
}
nodeA := nodes[0]
remNodes := make([]*ChangingResource, len(nodes)-1)
copy(remNodes, nodes[1:])
for i := 0; i < len(remNodes); i++ {
nodeB := remNodes[i]
newCurrentCurrent := make([]Edge, len(current))
copy(newCurrentCurrent, current)
if nodeA != nil && nodeB != nil {
newCurrentCurrent = append(newCurrentCurrent, createEdge(nodeA, nodeB))
}
nextSetFirstPart := make([]*ChangingResource, i)
nextSetSecondPart := make([]*ChangingResource, len(remNodes)-i-1)
copy(nextSetFirstPart, remNodes[:i])
copy(nextSetSecondPart, remNodes[i+1:])
nextSet := append(nextSetFirstPart, nextSetSecondPart...)
waitGroup.Add(1)
go find(nextSet, newCurrentCurrent, channel, waitGroup)
}
}