src/pyqt/gui/graph.py

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