-
Notifications
You must be signed in to change notification settings - Fork 0
/
guide_hair.py
169 lines (140 loc) · 5.54 KB
/
guide_hair.py
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
import metis_graph as mg
class GroupedGraph(mg.MetisGraph):
def __init__(self, mgraph, group):
self.xadj = mgraph.xadj
self.adjncy = mgraph.adjncy
self.eweights = mgraph.eweights
self.hairGroup = group
self.n_group = max(group)+1
self.n_strand = len(group)
def initSolution(self, opt):
self.createLookupTable()
self.initGuideHair(opt)
def createLookupTable(self):
'''convert the group table into a query link list'''
self.lookup = []
for i in range(self.n_group):
self.lookup.append([])
for i in range(self.n_strand):
self.lookup[self.hairGroup[i]].append(i)
def randomInitGuideHair(self):
import random
for i in range(self.n_group):
if self.guide[i] == None:
num = self.hairGroup.count(i)
self.guide[i] = self.lookup[i][int(num*random.random())]
def initSubOptimizedGuideHair(self):
for i in range(self.n_strand):
s = sum(self.eweights[self.xadj[i]:self.xadj[i+1]])
if s > self.guideVals[self.hairGroup[i]]:
if s == 0 and self.xadj[i] == self.xadj[i+1]:
continue
self.guideVals[self.hairGroup[i]] = s
self.guide[self.hairGroup[i]] = i
def initWorstGuideHair(self):
self.guideVals = [1e10] * self.n_group
for i in range(self.n_strand):
s = sum(self.eweights[self.xadj[i]:self.xadj[i+1]])
if s < self.guideVals[self.hairGroup[i]]:
self.guideVals[self.hairGroup[i]] = s
self.guide[self.hairGroup[i]] = i
def initGuideHair(self, opt):
self.guide = [None] * self.n_group
self.guideVals = [None] * self.n_group
if opt == "opt":
self.needIteration = True
self.initSubOptimizedGuideHair();
self.randomInitGuideHair();
elif opt == "rand":
self.needIteration = False
self.randomInitGuideHair();
elif opt == "worst":
self.needIteration = False
self.initWorstGuideHair();
self.randomInitGuideHair();
self.energy = self.computeEnergy()
print "\ninit guides: "
print " ", self.guide[:15], "..."
print "init values: "
print " ", self.energy
def computeEnergy(self, guide=None):
if guide == None:
guide = self.guide
eitr = mg.UndirectedIterator(self)
result = 0.
for i, j, weight in eitr:
if self.validPair(i, j, guide):
result += weight
return result
def isGuideHair(self, id, guide=None):
if guide == None:
guide = self.guide
groupId = self.hairGroup[id]
return id == guide[groupId]
def validPair(self, i, j, guide):
return (self.isGuideHair(i, guide) and (not self.isGuideHair(j, guide))) or \
(self.isGuideHair(j, guide) and (not self.isGuideHair(i, guide)))
def contributeForEnergyAsGuideMinusAsNormal(self, i, guide):
eitr = mg.EdgeIterator(self, i)
result = 0
for j, weight in eitr:
if not self.isGuideHair(j, guide):
result += weight
else:
result -= weight
return result
def iterate(self):
changed = False
for groupId in range(self.n_group):
sub = self.contributeForEnergyAsGuideMinusAsNormal(self.guide[groupId], self.guide)
for curNode in self.lookup[groupId]:
origin, self.guide[groupId] = self.guide[groupId], curNode
add = self.contributeForEnergyAsGuideMinusAsNormal(self.guide[groupId], self.guide)
if add > sub:
changed = True
self.energy -= sub
self.energy += add
sub = add
else:
self.guide[groupId] = origin
return changed
def solve(self, opt):
self.initSolution(opt)
count = 0
if self.needIteration:
while 1:
count += 1
if not self.iterate():
break
print "\niteration %d" % count
print self.energy
print "%d groups:" % len(self.guide)
print " ", self.guide[:15], "..."
print "values: "
print " ", self.energy
self.initGroupNeighbourMap()
return self.guide
def initGroupNeighbourMap(self):
self.groupNeighMap = [None] * self.n_group
self.groupGuideMap = [None] * self.n_group
for i in range(self.n_group):
self.groupNeighMap[i] = set([i])
eItr = mg.UndirectedIterator(self)
for i, j, w in eItr:
gi = self.hairGroup[i]
gj = self.hairGroup[j]
self.groupNeighMap[gi].add(gj)
self.groupNeighMap[gj].add(gi)
def findGuide(thiz, id):
return thiz.guide[id]
for i in range(self.n_group):
n_neigh = len(self.groupNeighMap[i])
self.groupGuideMap[i] = map(findGuide, [self]*n_neigh, self.groupNeighMap[i])
def dumpNeighbourMap(self, fileName):
import struct
import array
with open(fileName+"-"+str(self.n_group)+".neigh", "wb") as out:
out.write(struct.pack('i', self.n_group))
for i in range(self.n_group):
out.write(struct.pack('i', len(self.groupNeighMap[i])))
array.array('i', list(self.groupNeighMap[i])).tofile(out)