-
Notifications
You must be signed in to change notification settings - Fork 8.8k
/
perm.go
134 lines (116 loc) · 4.13 KB
/
perm.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
Copyright IBM Corp. All Rights Reserved.
SPDX-License-Identifier: Apache-2.0
*/
package graph
import (
"math/rand"
"time"
)
func init() {
rand.Seed(time.Now().UnixNano())
}
// treePermutations represents possible permutations
// of a tree
type treePermutations struct {
combinationUpperBound int // The upper bound of combinations of direct descendants.
originalRoot *TreeVertex // The root vertex of all sub-trees
permutations []*TreeVertex // The accumulated permutations
descendantPermutations map[*TreeVertex][][]*TreeVertex // Defines the combinations of sub-trees based on the threshold of the current vertex
}
// newTreePermutation creates a new treePermutations object with a given root vertex
func newTreePermutation(root *TreeVertex, combinationUpperBound int) *treePermutations {
return &treePermutations{
combinationUpperBound: combinationUpperBound,
descendantPermutations: make(map[*TreeVertex][][]*TreeVertex),
originalRoot: root,
permutations: []*TreeVertex{root},
}
}
// permute returns Trees that their vertices and edges all exist in the original tree who's vertex
// is the 'originalRoot' field of the treePermutations
func (tp *treePermutations) permute() []*Tree {
tp.computeDescendantPermutations()
it := newBFSIterator(tp.originalRoot)
for {
v := it.Next()
if v == nil {
break
}
if len(v.Descendants) == 0 {
continue
}
// Iterate over all permutations where v exists
// and separate them to 2 sets: a indiceSet where it exists and a indiceSet where it doesn't
var permutationsWhereVexists []*TreeVertex
var permutationsWhereVdoesntExist []*TreeVertex
for _, perm := range tp.permutations {
if perm.Exists(v.Id) {
permutationsWhereVexists = append(permutationsWhereVexists, perm)
} else {
permutationsWhereVdoesntExist = append(permutationsWhereVdoesntExist, perm)
}
}
// Remove the permutations where v exists from the permutations
tp.permutations = permutationsWhereVdoesntExist
// Next, we replace each occurrence of a permutation where v exists,
// with multiple occurrences of its descendants permutations
for _, perm := range permutationsWhereVexists {
// For each permutation of v's descendants, clone the graph
// and create a new graph with v replaced with the permutated graph
// of v connected to the descendant permutation
for _, permutation := range tp.descendantPermutations[v] {
subGraph := &TreeVertex{
Id: v.Id,
Data: v.Data,
Descendants: permutation,
}
newTree := perm.Clone()
newTree.replace(v.Id, subGraph)
// Add the new option to the permutations
tp.permutations = append(tp.permutations, newTree)
}
}
}
res := make([]*Tree, len(tp.permutations))
for i, perm := range tp.permutations {
res[i] = perm.ToTree()
}
return res
}
// computeDescendantPermutations computes all possible combinations of sub-trees
// for all vertices, based on the thresholds.
func (tp *treePermutations) computeDescendantPermutations() {
it := newBFSIterator(tp.originalRoot)
for {
v := it.Next()
if v == nil {
return
}
// Skip leaves
if len(v.Descendants) == 0 {
continue
}
// Ensure we don't have too much combinations of descendants
for CombinationsExceed(len(v.Descendants), v.Threshold, tp.combinationUpperBound) {
// Randomly pick a descendant, and remove it
victim := rand.Intn(len(v.Descendants))
v.Descendants = append(v.Descendants[:victim], v.Descendants[victim+1:]...)
}
// Iterate over all options of selecting the threshold out of the descendants
for _, el := range chooseKoutOfN(len(v.Descendants), v.Threshold) {
// And for each such option, append it to the current TreeVertex
tp.descendantPermutations[v] = append(tp.descendantPermutations[v], v.selectDescendants(el.indices))
}
}
}
// selectDescendants returns a subset of descendants according to given indices
func (v *TreeVertex) selectDescendants(indices []int) []*TreeVertex {
r := make([]*TreeVertex, len(indices))
i := 0
for _, index := range indices {
r[i] = v.Descendants[index]
i++
}
return r
}