src/pyqt/gui/graph.py

   1 import sys
   2 import pilot
   3 import Item
   4 from qt import *
   5 from qtcanvas import *
   6 from GraphViewer import GraphViewer
   7 import Editor
   8 import CItems
   9 import pygraphviz
  10 from pygraphviz import graphviz as gv
  11 import traceback
  12 import CONNECTOR
  13 import bisect
  14
  15 class MyCanvas(QCanvas):
  16   def customEvent(self,event):
  17     object=event.data()
  18     object.customEvent(event)
  19     self.update()
  20
  21 class Graph:
  22   def __init__(self,item,parent):
  23     self.parent=parent
  24     self.item=item
  25     self.node=item.node
  26     #initial canvas size : 1000x1000
  27     self.canvas=MyCanvas(1000,1000)
  28     self.editor=GraphViewer(self.canvas,parent,"example",0)
  29     self.createGraph()
  30     root=self.node.getRootNode()
  31     rootItem=Item.adapt(root)
  32     CONNECTOR.Connect(rootItem,"selected",self.selectItem,())
  33     CONNECTOR.Connect(self.item,"add",self.addItem,())
  34     CONNECTOR.Connect(self.item.datalinks,"add",self.addLink,())
  35
  36   def createGraph(self):
  37     #citems dict helps finding items in canvas from swig proxy
  38     #To find an item node make : citems[node.ptr()]
  39     citems={}
  40     self.citems=citems
  41     #pitems dict helps finding items in canvas from swig proxy
  42     #To find an item port make : pitems[port.ptr()]
  43     pitems={}
  44
  45     y=0
  46     lnode=self.node.edGetDirectDescendants()
  47     for n in lnode:
  48       c=CItems.Cell(n,self.canvas)
  49       citems[n.ptr()]=c
  50       c.show()
  51
  52     for k,n in citems.items():
  53       for p in n.inports:
  54         pitems[p.port.ptr()]=p
  55       for p in n.outports:
  56         pitems[p.port.ptr()]=p
  57
  58     for pout,pin in self.node.getSetOfInternalLinks():
  59       if pout.getNode().getFather() != self.node and pin.getNode().getFather() != self.node:
  60         continue
  61       po=pitems.get(pout.ptr())
  62       pi=pitems.get(pin.ptr())
  63       if pi and po:
  64         CItems.LinkItem(po,pi,self.canvas)
  65
  66     for n in lnode:
  67       itemup=citems[n.ptr()]
  68       for ndown in n.getOutNodes():
  69         itemdown=citems[ndown.ptr()]
  70         CItems.ControlLinkItem(itemup.outgate,itemdown.ingate,self.canvas)
  71
  72     self.layout("LR")
  73
  74   def addLink(self,link):
  75     print "graph.addLink",link
  76     #CItem for outport
  77     nodeS=self.citems[link.pout.getNode().ptr()]
  78     nodeE=self.citems[link.pin.getNode().ptr()]
  79     po=pi=None
  80     for p in nodeS.outports:
  81       if p.port == link.pout:
  82         po=p
  83         break
  84     for p in nodeE.inports:
  85       if p.port == link.pin:
  86         pi=p
  87         break
  88
  89     if pi and po:
  90       l=CItems.LinkItem(po,pi,self.canvas)
  91       self.canvas.update()
  92
  93   def addItem(self,item):
  94     #print "graph.addItem",item
  95     node=CItems.Cell(item.node,self.canvas)
  96     self.citems[item.node.ptr()]=node
  97     node.show()
  98     self.canvas.update()
  99
 100   def selectItem(self,item):
 101     #print "graph.selectItem",item
 102     self.editor.selectItem(item)
 103
 104   def layout(self,rankdir):
 105     """Compute graph layout with graphviz package"""
 106     G=pygraphviz.AGraph(strict=False,directed=True)
 107     G.graph_attr["rankdir"]=rankdir
 108     G.graph_attr["dpi"]="72"
 109     dpi=72.
 110     aspect=dpi/72
 111     for k,n in self.citems.items():
 112       #k is node address (YACS)
 113       #n is item in canvas
 114       G.add_node(k)
 115
 116     for pout,pin in self.node.getSetOfInternalLinks():
 117       if pout.getNode().ptr() not in self.citems :
 118         continue
 119       if pin.getNode().ptr() not in self.citems:
 120         continue
 121       G.add_edge(pout.getNode().ptr(),pin.getNode().ptr())
 122
 123     for k,n in self.citems.items():
 124       for ndown in n.node.getOutNodes():
 125         G.add_edge(n.node.ptr(),ndown.ptr())
 126
 127     #By default graphviz uses 96.0 pixel per inch (dpi=96.0)
 128     for n in G.nodes():
 129       item=self.citems[int(n)]
 130       h=item.height()/dpi #height in inch
 131       w=item.width()/dpi  #width in inch
 132       n.attr['height']=str(h)
 133       n.attr['width']=str(w)
 134       n.attr['fixedsize']="true"
 135       n.attr['shape']="box"
 136       #n.attr['label']=item.node.getName()
 137
 138     G.layout(prog='dot') # use dot
 139     #G.write("layout.dot")
 140     #G.draw("layout.png")
 141
 142     graph_attr=dict(attrs(G))
 143     bbox=graph_attr["bb"]
 144     x1,y1,x2,y2=eval(bbox)
 145     h=self.canvas.height()
 146     w=self.canvas.width()
 147     h2=max(h,y2-y1+100)
 148     w2=max(w,x2-x1+100)
 149     if h2 > h or w2 > w:
 150       self.canvas.resize(w2,h2)
 151
 152     for n in G:
 153       pos=n.attr['pos'] #position is given in points (72 points par inch, so 1 point = dpi/72=1.34)
 154       x,y=eval(pos)
 155       x=aspect*x
 156       y=aspect*y
 157       item=self.citems[int(n)]
 158       x0=item.x()
 159       y0=item.y()
 160       x=x-x0
 161       y=y-y0
 162       item.moveBy(x,y)
 163
 164     self.canvas.update()
 165
 166   def clearLinks(self):
 167     items=self.citems.values()
 168     for node in items:
 169       for port in node.outports:
 170         if not hasattr(port,"links"):
 171           continue
 172         for link in port.links():
 173           link.clearPoints()
 174     self.canvas.update()
 175
 176   def orthoLinks(self):
 177     items=self.citems.values()
 178     g=grid(items)
 179     for node in items:
 180       for port in node.outports:
 181         if not hasattr(port,"links"):
 182           continue
 183         for link in port.links():
 184           #clear all intermediate points of the link
 185           link.clearPoints()
 186           #if isinstance(link,CItems.ControlLinkItem):
 187           #  print port.port.getNode().getName() +"->"+link.toPort.port.getNode().getName()
 188           #else:
 189           #  print port.port.getNode().getName() +":"+port.port.getName()+"->"+link.toPort.port.getNode().getName()+":"+link.toPort.port.getName()
 190           #print (port.x(),port.y()),(link.toPort.x(),link.toPort.y())
 191           x0,y0=port.x()+5,port.y()
 192           while g.get((x0,y0)).blocked:
 193             x0=x0+1
 194           x1,y1=link.toPort.x()-5,link.toPort.y()
 195           while g.get((x1,y1)).blocked:
 196             x1=x1-1
 197           path=g.findPath((x0,y0),(x1,y1))
 198           #print path
 199           if len(path)==1:
 200             if port.y() == link.toPort.y():
 201               #near ports face to face
 202               continue
 203             else:
 204               x,y=path[0]
 205               path=[(x,port.y()),(x,link.toPort.y())]
 206           elif len(path)==2:
 207             x1,y1=path[0]
 208             x2,y2=path[1]
 209             if x1 == x2:
 210               #vertical line
 211               path=[(x1,port.y()),(x1,link.toPort.y())]
 212             else:
 213               #horizontal line
 214               if port.y() == link.toPort.y():
 215                 #near ports face to face
 216                 continue
 217               else:
 218                 #transform it into a vertical line
 219                 x=(x1+x2)/2
 220                 path=[(x,port.y()),(x,link.toPort.y())]
 221
 222           #adjust the first point to the same y as port
 223           x0,y0=path[0]
 224           x1,y1=path[1]
 225           if y0==y1:
 226             #remove first point and adjust second one
 227             del path[0]
 228             x0=x1
 229           path[0]=x0,port.y()
 230           #adjust the last point to the same y as link.toPort
 231           x0,y0=path[-1]
 232           x1,y1=path[-2]
 233           if y0==y1:
 234             #remove last point and adjust new last one
 235             del path[-1]
 236             x0=x1
 237           path[-1]=x0,link.toPort.y()
 238           #print path
 239
 240           #add intermediate points
 241           for x,y in path:
 242             line=link.lines[-1]
 243             link.splitLine(line,x,y)
 244     self.canvas.update()
 245
 246 def attrs(g,t=gv.AGRAPH):
 247   ah=None
 248   while 1:
 249     ah=gv.agnxtattr(g.handle,t,ah)
 250     value=gv.agxget(g.handle,ah)
 251     yield gv.agattrname(ah),value
 252
 253 def h(x,y,destx,desty):
 254   return abs(destx-x)+abs(desty-y)
 255
 256 def distance(node,new_node):
 257   x,y=node.coord
 258   x1,y1=new_node.coord
 259   d= abs(x1-x)+abs(y1-y)
 260   if node.parent != None:
 261     x0,y0=node.parent.coord
 262     if (x1-x)*(y0-y)-(y1-y)*(x0-x) != 0:
 263       #corner add some cost to penalize
 264       d=d+1
 265   return d
 266
 267 class node:
 268   def __init__(self,coord,index):
 269     self.coord=coord
 270     self.index=index
 271     self.blocked=0
 272     self.total=0
 273     self.path_cost=0
 274     self.parent=None
 275     self.open=0
 276     self.close=0
 277
 278 class grid:
 279   def __init__(self,graph):
 280     self.graph=graph
 281     xs=set()
 282     ys=set()
 283     xmargin=5
 284     ymargin=5
 285     for n in graph:
 286       h=n.height()
 287       w=n.width()
 288       x=n.x()
 289       y=n.y()
 290       xs.add(x-xmargin)
 291       xs.add(x+w+xmargin)
 292       ys.add(y-ymargin)
 293       ys.add(y+h+ymargin)
 294
 295     xs=list(xs)
 296     xs.sort()
 297     x0=xs[0]-36
 298     xs.insert(0,x0)
 299     x0=xs[-1]+36
 300     xs.append(x0)
 301
 302     ys=list(ys)
 303     ys.sort()
 304     y0=ys[0]-36
 305     ys.insert(0,y0)
 306     y0=ys[-1]+36
 307     ys.append(y0)
 308
 309     self.xs=xs
 310     self.ys=ys
 311     self.cols=[]
 312     for w in xrange(len(xs)-1):
 313       col=[]
 314       x=(xs[w]+xs[w+1])/2
 315       for h in xrange(len(ys)-1):
 316         y=(ys[h]+ys[h+1])/2
 317         col.append(node((x,y),(w,h)))
 318       self.cols.append(col)
 319
 320     for n in graph:
 321       h=n.height()
 322       w=n.width()
 323       x=n.x()
 324       y=n.y()
 325       l1,l2=bisect.bisect_left(ys,y-ymargin),bisect.bisect_left(ys,y+h+ymargin)
 326       i1,i2=bisect.bisect_left(xs,x-xmargin),bisect.bisect_left(xs,x+w+xmargin)
 327       for c in self.cols[i1:i2]:
 328         for e in c[l1:l2]:
 329           e.blocked=1
 330
 331     #for col in self.cols:
 332     #  print [e.coord +(e.blocked,) for e in col]
 333
 334   def reset(self):
 335     for c in self.cols:
 336       for n in c:
 337         n.open=n.close=0
 338         n.total= n.path_cost=0
 339         n.parent=None
 340
 341   def get(self,coord):
 342     x,y=coord
 343     col= bisect.bisect_left(self.xs,x)-1
 344     if col < 0 or col >= len(self.cols):
 345       return None
 346     col=self.cols[col]
 347     row=bisect.bisect_left(self.ys,y)-1
 348     if row < 0 or row >= len(col):
 349       return None
 350     return col[row]
 351
 352   def getPath(self,node):
 353     path=[node.coord]
 354     parent=node.parent
 355     while parent:
 356       prev=node
 357       node=parent
 358       parent=node.parent
 359       if parent:
 360         #if points are aligned don't keep the middle point
 361         x,y=node.coord
 362         x0,y0=prev.coord
 363         x1,y1=parent.coord
 364         if (x1-x)*(y0-y)-(y1-y)*(x0-x) == 0:
 365           continue
 366       path.append(node.coord)
 367     path.reverse()
 368     return path
 369
 370   def neighbours(self,node):
 371     col,row=node.index
 372     l=[]
 373     steps=((0,  +1), (+1,  0), (0,  -1), (-1,  0 ))
 374     for step in steps:
 375       c=col+step[0]
 376       r=row+step[1]
 377       if c < 0 or c >=len(self.cols):
 378         continue
 379       co=self.cols[c]
 380       if r <0 or r >= len(co):
 381         continue
 382       n=co[r]
 383       if n.blocked:
 384         continue
 385       l.append(n)
 386     return l
 387
 388   def findPath(self,fromLoc,toLoc):
 389     """Find shortest path from fromLoc to toLoc"""
 390     self.reset()
 391     self.open=[]
 392     fromNode=self.get(fromLoc)
 393     self.open.append((fromNode.total,fromNode))
 394     toNode=self.get(toLoc)
 395     if toNode.blocked:
 396       print "toNode is blocked"
 397       return []
 398     destx,desty=toNode.coord
 399     while self.open:
 400       #if open is not void, take the best node (the first one)
 401       t,node=self.open.pop(0)
 402       node.close=1
 403       if node == toNode:
 404         #got toLoc
 405         return self.getPath(node)
 406
 407       for new_node in self.neighbours(node):
 408         if new_node.close :
 409           continue
 410         x,y =new_node.coord
 411         path_cost=node.path_cost+distance(node,new_node)
 412         total=path_cost+h(x,y,destx,desty)
 413         if new_node.open :
 414           #the node is already in open
 415           if total < new_node.total:
 416             self.open.remove((new_node.total,new_node))
 417             new_node.path_cost=path_cost
 418             new_node.parent=node
 419             new_node.total=total
 420             bisect.insort(self.open,(new_node.total,new_node))
 421         else:
 422           #the node is not yet in open
 423           new_node.path_cost=path_cost
 424           new_node.parent=node
 425           new_node.total=total
 426           bisect.insort(self.open,(new_node.total,new_node))
 427           new_node.open=1
 428
 429     return []
 430