forked from ccarlile/conceptDraw
-
Notifications
You must be signed in to change notification settings - Fork 0
/
conceptDraw.py
510 lines (418 loc) · 19.4 KB
/
conceptDraw.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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
from pprint import PrettyPrinter
from math import sqrt
import networkx as nx
import pygraphviz as pgv
import matplotlib.pyplot as plt
from subprocess import check_output
from sys import argv
# This should be the final version of the concept drawing function. I'm going to leverage
# several different libraries in the name of not messing anything up myself, and to make
# this whole thing slightly more readable. The general idea is as follows:
# 1. Look ahead to the whole lession. Build a graph out of it. Lay it out using a modified sugiyama
# layout using graphviz. Record the positions of the nodes (maybe edges too?) in the associated
# pos dict.
#
# 2. Enter listening mode. The program will wait for input, whether it be from the agent or
# from the user. If agent input, retrieve the location of the soon-to-be displayed node
# and draw it using matplotlib. If user input, do nothing unless it overlaps, in which case
# use the force-scan algorithm
#
# 3. Either way, add a history item after number 2 is completed. Try and keep it uniform, i
# suppose
GVPIX = 1.388
class ForceScan:
def __init__(self, graph, pos):
self._defaultWidth = 0
self._defaultHeight= 0
self._nodesep = 20
self._pos = {}
self._graph = nx.DiGraph()
self._initialLayout(graph, pos)
self._forceScan()
def _returnNewPos(self):
pass
def _initialLayout(self, graph, posd):
#given a posd dict, create a forcescan class with nodes in their specified positions
for node in posd:
width = posd[node]['width']
height = posd[node]['height']
center = [ posd[node]['pos'][0] + int(width/2), posd[node]['pos'][1] + int(height/2) ]
self._pos[node] = {'width': width, 'height': height, 'center':center}
self._graph = graph
def _addNode(self, node):
#add a node to node dict. Here, node is a dict with initial position information
#ForceScan._addNode(self, {'id'=name, 'pos'=(x,y)})
#self.graph.add_node(
pass
def _removeNode(self, node):
pass
def _addEdge(self, node):
#adds an edge to the edge dict
pass
def _unitVector(self, node, target):
#reutrns a 2-element list representing the unit vector in the direnction u -> v
np = self._pos[node]['center']
tp = self._pos[target]['center']
d = self._euclideanDistance(node, target)
v = [tp[0] - np[0], tp[1] - np[1]]
uv = [x / d for x in v]
return uv
def _euclideanDistance(self, node, target):
#returns a scalar that is the distance in pixels between node and target
np = self._pos[node]['center']
tp = self._pos[target]['center']
d = sqrt( (np[0] - tp[0])**2 + (np[1] - tp[1])**2)
return d
def _calculateForce(self, node, target):
#returns a 2-element list representing the projections of the forces in the x and y directions
uv = self._unitVector(node, target)
duv = self._euclideanDistance(node, target)
u = self._pos[node]
v = self._pos[target]
w_u = u['width']
w_v = v['width']
h_u = u['height']
h_v = v['height']
k_uv_x = (w_u + w_v) / 2
k_uv_y = (h_u + h_v) / 2
f_uv = [((k_uv_x - duv) * uv[0]), ((k_uv_y - duv) * uv[1])]
return f_uv
def _forceScan(self):
#updates all position dict entries
g = self._graph.succ
p = self._pos
V = len(g)
xs = sorted(p, key=lambda x: p[x]['center'][0])
ys = sorted(p, key=lambda y: p[y]['center'][1])
# FORCE-SCAN PSUEDOCODE
# i <- 1
# while i < |V| do
# suppose x_i = x_i+1 = ... = x_k;
# delta <- max ([ f^x(v_m, v_j) for i <= m <= k <=j <=|V|]
# for (j=k+1, |V|) do: x_vj <- x_vj + delta
# i <- k+1
#Horizontal Scan
i = 0
while i < V:
#nodes after i whose centers have the same x value as i's
xi = [x for x in xs[i:] if self._pos[x]['center'][0] == self._pos[xs[i]]['center'][0]]
#print xi
k = len(xi)
try:
delta = max([self._calculateForce(x, y)[0] for x in xi for y in xs[i + k:]])
except ValueError:
delta = 0
for x in xs[i+k:]:
p[x]['center'][0] = int(p[x]['center'][0] + delta)
i += k
#Vertical Scan
i = 0
while i < V:
#nodes after i whose centers have the same x value as i's
yi = [y for y in ys[i:] if self._pos[y]['center'][1] == self._pos[ys[i]]['center'][1]]
k = len(yi)
try:
delta = max([self._calculateForce(x, y)[1] for x in yi for y in ys[i + k:]])
except ValueError:
delta = 0
for y in ys[i+k:]:
p[y]['center'][1] = int(p[y]['center'][1]+ delta)
i += k
class ConceptDrawer:
def __init__(self, graph):
self._dataGraph = nx.DiGraph()
self._displayGraph = nx.DiGraph()
self._history = []
self._compound = {'pred': {},'succ': {}}
self._dotfile = ''
self._dotnode = {}
self._minNodeDist = 20
self._pos = {}
self._processBaseGraph(graph)
def _buildInitialGraph(self):
pass
def _nodeDist(node1, node2):
pass
def _findInitialPos(self):
pass
def _draw(self):
pass
def _updateDrawGraph(self):
pass
def _addToHistory(self, histObject):
pass
def _forceScan(self):
pass
def _toPyplot(self, pos):
#takes a pos dict in pixels and returns it in an array, just like matplotlib likes it.
posnx = {}
for node in pos:
posnx[node] = [pos[node]['pos'][0],pos[node]['pos'][1]]
return posnx
def drawplt(self, pos):
#G is actual semantic graph
#pos is the position dict (posnx, use the _toPyplot)
nx.draw_networkx(self._dataGraph, pos)
plt.show()
pass
def findCompound(self, graph):
#takes care of all the pretty stuffs for the base graph - namely, compound edges
#and horizontal relationships
grouped = []
groups = []
groupsh = [] #horizontal group
labels= []
for node in graph.succ:
#new strategy: iterate through all edge labels. find all nodes with edges with that label.
#check to see if others are compound
mlabel = [graph.succ[node][value]['label'] for value in graph.succ[node]]
labels.extend(mlabel)
for node in graph.pred:
mlabel = [graph.pred[node][value]['label'] for value in graph.pred[node]]
labels.extend(mlabel)
labels = list(set(labels))
#now that we have the labels in question:
for label in labels:
for node in graph.succ:
#for each label, make key, value pairs for nodes
sharedlabels = [x for x, y in graph.succ[node].iteritems() if y['label'] == label]
if len(sharedlabels) > 1:
#check if all horiz attributes are True
if False not in [graph.succ[node][x]['horiz'] == True for x in sharedlabels]:
groupsh.append(sharedlabels)
else:
groups.append(sharedlabels)
for x in sharedlabels:
grouped.append(x)
for node in graph.pred:
#for each label, make key, value pairs for nodes
sharedlabels = [x for x, y in graph.pred[node].iteritems() if y['label'] == label]
if len(sharedlabels) > 1:
if False not in [graph.pred[node][x]['horiz'] == True for x in sharedlabels]:
groupsh.append(sharedlabels)
else:
groups.append(sharedlabels)
for x in sharedlabels:
grouped.append(x)
for node in graph.succ:
if node not in grouped:
grouped.append(node)
groups.append([node])
return groups, groupsh
def addNodeToDotfile(self, node, *args):
#node is actually a list - we will do different things based on whether this list is of
#length 1 or not.
#only called during creation of the dotfile.
#create property dict for all nodes: keys are node names, values what graphviz will be using
#to id nodes in record nodes when making edges
#while iterating through the groups, add all nodes to the dotfile
#this is where the ids should be stripped of spaces
if len(node) == 1:
nodeit = node[0]
nodestrip = nodeit.replace(' ','').replace('-','')
self._dotfile += 'node [shape=box];\n'
self._dotnode[nodeit] = {'id' : nodestrip, 'label':nodeit}
self._dotfile += nodestrip + ' [label="' + nodeit + '"];\n'
elif 'horizontal' in args:
self._dotfile += 'node [shape=record];\n'
recordlabel = ''.join(node).replace(' ','').replace('-','')
self._dotfile += recordlabel + ' [label="{'
for num, nodeit in enumerate(node):
nodestrip = nodeit.replace(' ','').replace('-','')
self._dotnode[nodeit] = {'id' : recordlabel + ':' + nodestrip, 'label': nodeit}
self._dotfile += '<' + nodestrip + '>' + nodeit
if len(node) == num + 1:
self._dotfile += '}"];\n'
else:
self._dotfile += '|'
else:
self._dotfile += 'node [shape=record];\n'
recordlabel = ''.join(node).replace(' ','').replace('-','')
self._dotfile += recordlabel + ' [label="'
for num, nodeit in enumerate(node):
nodestrip = nodeit.replace(' ','').replace('-','')
self._dotnode[nodeit] = {'id' : recordlabel + ':' + nodestrip, 'label': nodeit}
self._dotfile += '<' + nodestrip + '>' + nodeit
if len(node) == num + 1:
self._dotfile += '"];\n'
else:
self._dotfile += '|'
def formatBaseGraph(self, graph):
#this method that takes groups of compound predicates and the initial data graph and
#makes a dotfile for layout with graphviz. Not quite worried about edge nodes yet -
#will work on that for the rest of the month.
#iterate through groups list
groups, groupsh = self.findCompound(graph)
for group in groups:
self.addNodeToDotfile(group)
for group in groupsh:
self.addNodeToDotfile(group, 'horizontal')
#next, iterate through the successor dict and add all edges to the dotfile, using the
#property dict to ensure proper edge labels
for source in graph.succ:
for target in graph.succ[source]:
self._dotfile += self._dotnode[source]['id'] + '->'
self._dotfile += self._dotnode[target]['id'] +';\n'
self._dotfile = 'digraph G {\n'+ self._dotfile + '}'
def _posFromParsedDot(self):
#pos is the dict of positions we're going to return. It'll look like this:
#pos = {node: ("width": width, "height": height, "pos": pos} for however many
#nodes there may be
posd = {}
dotfile = self._dotout
dotfile = dotfile.replace('\n','').replace('\t','')
entries = dotfile.split(';')
entries2 = [entry for entry in entries if '->' not in entry and 'pos=' in entry]
#record nodes' positions are defined in "GV pixels", from which I can tell are
#approximately 1/1.388 the size of the pixels on my screen. Height and width are
#given in inches, and can be converted to GV pixels by multiplying by 96.
#we want to define a bottom-left hand corner (assuming we're in Quadrant I)
for entry in entries2:
if 'rects=' in entry:
#record nodes' rects are so far unknwon. We use their relative widths/heights to
#figure out how many GV pixels to assign to each record
#split on the '"'
names = []
horizNames = []
pos = (0,0)
horiz = False
ids = []
width = 0
height = 0
current = entry.split('"')
for i, split in enumerate(current):
if 'pos=' in split: pos = tuple(current[i+1].split(","))
if 'label=' in split:
names = current[i+1].split("|")
if True in ['{' in x or '}' in x for x in names]:
horizNames.extend(names)
if 'rects=' in split: rects = current[i+1].split(" ")
splits = split.split("=")
for j, subsplit in enumerate(splits):
if 'height' in subsplit:
height = splits[j+1].split(",")[0]
if 'width' in subsplit:
width = splits[j+1].strip("]")
if names:
horiz = False
for name in names:
idtoappend = name.split('>')[1]
if name in horizNames:
idtoappend = idtoappend.replace('{','').replace('}','')
horiz = True
ids.append(idtoappend)
#begin arduous hacking logic. Going to keep everything in "real pixels"
center = tuple([int(float(coord) * GVPIX) for coord in pos])
width = int(float(width)*96)
height = int(float(height)*96)
#get realtive widths and heights
ys = [float(x) for x in ','.join(rects).split(',')[1::2]]
xs = [float(x) for x in ','.join(rects).split(',')[0::2]]
maxw = abs(max(xs) - min(xs))
maxh = abs(max(ys) - min(ys))
relws = [(xs[i+1] - xs[i]) / maxw for i in range(0, len(xs), 2)]
relhs = [(ys[i+1] - ys[i]) / maxh for i in range(0, len(ys), 2)]
widths = [int(width * x) for x in relws]
heights = [int(height * x) for x in relhs]
#get bottom-left corner
corner = (center[0] - width/2, center[1] - height/2)
#this whole block, beginning with "if names:", does positioning in chunks
#Therefore we can assume that all nodes in "ids" are all laid out the
#same way (horizontally, vertically) and change the positioning chunk as
#we need it
if not horiz:
for i, myid in enumerate(ids):
if i > 0:
sumw = sum([widths[j] for j in range(i)])
posd[myid] = {'width': widths[i], 'height':height, 'pos': (
corner[0] + sumw, corner[1])}
else:
posd[myid] = {'width': widths[i], 'height':height, 'pos': corner}
#horizontal arrangement
else:
for i, myid in enumerate(ids):
if i > 0:
sumh = sum([heights[j] for j in range(i)])
posd[myid] = {'width': width, 'height':heights[i], 'pos': (
corner[0], corner[1] + sumh)}
else:
posd[myid] = {'width': width, 'height':heights[i], 'pos': corner}
#i.e. shape is not record
else:
current = entry.split("=")
ids = entry.split('[')[0].strip()
ids = self._nameFromDotLabel(ids)
#fix space in normal node issue here
for i, split in enumerate(current):
if "height" in split: height = int(float(current[i+1].split(',')[0] ) * 96)
if "width" in split: width = int(float(current[i+1].strip(']')) * 96)
if "pos" in split: pos = tuple(current[i+1].split('"')[1].split(','))
pos = tuple([int(float(x)) for x in pos])
posd[ids] = {'width':width, 'height':height, 'pos':pos}
#pp = PrettyPrinter()
#pp.pprint(posd)
return posd
def _nameFromDotLabel(self, nodeid):
for node, item in self._dotnode.items():
if nodeid == item['id']: return item['label']
return nodeid
def addNode(self, node, pos):
self._dataGraph.add_node(node)
self._pos[node] = {'pos':tuple(pos), 'height':50,'width':90}
self.plotGraph('forcescan')
pass
def plotGraph(self, *args):
if 'forcescan' in args:
d = ForceScan(self._dataGraph, self._pos)
self._updatePosDict(d)
posd = {}
for node, pos in self._pos.items():
posd[node] = pos['pos']
nx.draw(self._dataGraph, pos=posd, node_shape='s', node_size=1200)
plt.show()
def listen(self):
while True:
node = input('add a node: name?\n')
posx = input('add a node: x position?\n')
posy = input('add a node, y position?\n')
print 'added node', node, 'at', posx, posy
#add the node to the conceptDrawer class with left-corner notation and corresponding w/h
#create apply force-scan to the new pos dict in conceptdrawer
self.addNode(node, (posx,posy))
def _updatePosDict(self, forcescan):
#take updated dict from force scan and update the drawgraph (self.graph) with new values
#to get left bottom corner, subtract half the width from x and half the height from y
fd = forcescan._pos
sd = self._pos
for node in sd:
width = sd[node]['width']
height = sd[node]['height']
sd[node]['pos'] = (fd[node]['center'][0] - int(width/2), fd[node]['center'][1] - int(height/2))
def _processBaseGraph(self, graph):
self._dataGraph = graph.copy()
self.formatBaseGraph(graph)
#write the dotfile and run it with graphviz
with open('./dotout.txt', 'w+') as f:
f.write(self._dotfile)
#actually run dot
self._dotout = check_output(['dot', './dotout.txt'])
#write the output of dot for checkin'
#with open('./conceptDraw.dot','w') as f:
# f.write(self._dotout)
#plot the graph pre-forcescan
self._pos = self._posFromParsedDot()
nxpos = self._toPyplot(self._pos)
self.drawplt(nxpos)
#create a forescan class and feed it the position dict we harvested from DOT
d = ForceScan(graph, self._pos)
self._updatePosDict(d)
#plot the graph again
nxpos = self._toPyplot(self._pos)
self.drawplt(nxpos)
if __name__== '__main__':
inputgraph = './lessons/14-6-7.py'
graphInput = nx.DiGraph()
grGlobals = {'graph': graphInput}
execfile(inputgraph, grGlobals)
d = ConceptDrawer(graphInput)
#d.listen()