src/pyqt/gui/graph.py

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