bin/tools/graph.py

   1 #!/usr/bin/python
   2 # -*- encoding: utf-8 -*-
   3 ##############################################################################
   4 #
   5 # Copyright (c) 2004-2008 Tiny SPRL (http://tiny.be) All Rights Reserved.
   6 #
   7 # $Id$
   8 #
   9 # WARNING: This program as such is intended to be used by professional
  10 # programmers who take the whole responsability of assessing all potential
  11 # consequences resulting from its eventual inadequacies and bugs
  12 # End users who are looking for a ready-to-use solution with commercial
  13 # garantees and support are strongly adviced to contract a Free Software
  14 # Service Company
  15 #
  16 # This program is Free Software; you can redistribute it and/or
  17 # modify it under the terms of the GNU General Public License
  18 # as published by the Free Software Foundation; either version 2
  19 # of the License, or (at your option) any later version.
  20 #
  21 # This program is distributed in the hope that it will be useful,
  22 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  23 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24 # GNU General Public License for more details.
  25 #
  26 # You should have received a copy of the GNU General Public License
  27 # along with this program; if not, write to the Free Software
  28 # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  29 ###############################################################################
  30 import operator
  31 import math
  32
  33 class graph(object):
  34     def __init__(self, nodes, transitions, no_ancester=None):
  35         """Initailize graph's object
  36
  37         @param nodes: list of ids of nodes in the graph
  38         @param transitions: list of edges in the graph in the form (source_node, destination_node)
  39         @param no_ancester: list of nodes with no incoming edges
  40         """
  41
  42         self.nodes = nodes or []
  43         self.edges = transitions or []
  44         self.no_ancester = no_ancester or {}
  45         trans = {}
  46
  47         for t in transitions:
  48             trans.setdefault(t[0], [])
  49             trans[t[0]].append(t[1])
  50         self.transitions = trans
  51         self.result = {}
  52         self.levels = {}
  53
  54
  55     def init_rank(self):
  56         """Computes rank of the nodes of the graph by finding initial feasible tree
  57         """
  58         self.edge_wt = {}
  59         for link in self.links:
  60             self.edge_wt[link] = self.result[link[1]]['y'] - self.result[link[0]]['y']
  61
  62         cnt = 0
  63         list_node = []
  64         list_edge = []
  65
  66         tot_node = self.partial_order.__len__()
  67         #do until all the nodes in the components are searched
  68         while self.tight_tree()<tot_node:
  69             cnt+=1
  70             list_node = []
  71
  72             for node in self.nodes:
  73                 if node not in self.reachable_nodes:
  74                     list_node.append(node)
  75             list_edge = []
  76
  77             for link in self.edge_wt:
  78                  if link not in self.tree_edges:
  79                     list_edge.append(link)
  80
  81             slack = 100
  82
  83             for edge in list_edge:
  84                 if (self.reachable_nodes.__contains__(edge[0]) and edge[1] not in self.reachable_nodes) or ( self.reachable_nodes.__contains__(edge[1]) and  edge[0] not in self.reachable_nodes):
  85                     if(slack>self.edge_wt[edge]-1):
  86                         slack = self.edge_wt[edge]-1
  87                         new_edge = edge
  88
  89             if new_edge[0] not in self.reachable_nodes:
  90                 delta = -(self.edge_wt[new_edge]-1)
  91             else:
  92                 delta = self.edge_wt[new_edge]-1
  93
  94             for node in self.result:
  95                 if node in self.reachable_nodes:
  96                     self.result[node]['y'] += delta
  97
  98             for link in self.edge_wt:
  99                 self.edge_wt[link] = self.result[link[1]]['y'] - self.result[link[0]]['y']
 100
 101         self.init_cutvalues()
 102
 103
 104     def tight_tree(self):
 105         self.reachable_nodes = []
 106         self.tree_edges = []
 107         self.reachable_node(self.start)
 108         return self.reachable_nodes.__len__()
 109
 110     def reachable_node(self, node):
 111         """Find the nodes of the graph which are only 1 rank apart from each other
 112         """
 113
 114         if node not in self.reachable_nodes:
 115             self.reachable_nodes.append(node)
 116         for link in self.edge_wt:
 117             if link[0]==node:
 118                 if self.edge_wt[link]==1:
 119                     self.tree_edges.append(link)
 120                     if link[1] not in self.reachable_nodes:
 121                         self.reachable_nodes.append(link[1])
 122                     self.reachable_node(link[1])
 123
 124
 125     def init_cutvalues(self):
 126         """Initailize cut values of edges of the feasible tree.
 127         Edges with negative cut-values are removed from the tree to optimize rank assignment
 128         """
 129         self.cut_edges = {}
 130         self.head_nodes = []
 131         i=0;
 132
 133         for edge in self.tree_edges:
 134             self.head_nodes = []
 135             rest_edges = []
 136             rest_edges += self.tree_edges
 137             rest_edges.__delitem__(i)
 138             self.head_component(self.start, rest_edges)
 139             i+=1
 140             positive = 0
 141             negative = 0
 142             for source_node in self.transitions:
 143                 if source_node in self.head_nodes:
 144                     for dest_node in self.transitions[source_node]:
 145                         if dest_node not in self.head_nodes:
 146                             negative+=1
 147                 else:
 148                     for dest_node in self.transitions[source_node]:
 149                         if dest_node in self.head_nodes:
 150                             positive+=1
 151
 152             self.cut_edges[edge] = positive - negative
 153
 154
 155     def head_component(self, node, rest_edges):
 156         """Find nodes which are reachable from the starting node, after removing an edge
 157         """
 158         if node not in self.head_nodes:
 159             self.head_nodes.append(node)
 160         for link in rest_edges:
 161             if link[0]==node:
 162                 self.head_component(link[1],rest_edges)
 163
 164
 165     def process_ranking(self, node, level=0):
 166         """Computes initial feasible ranking after making graph acyclic with depth-first search
 167         """
 168
 169         if node not in self.result:
 170             self.result[node] = {'x': None, 'y':level, 'mark':0}
 171         else:
 172             if level > self.result[node]['y']:
 173                 self.result[node]['y'] = level
 174         if self.result[node]['mark']==0:
 175             self.result[node]['mark'] = 1
 176             for t in self.transitions.get(node, []):
 177                 self.process_ranking(t, level+1)
 178
 179
 180     def make_acyclic(self, parent, node, level, tree):
 181         """Computes Partial-order of the nodes with depth-first search
 182         """
 183
 184         if node not in self.partial_order:
 185             self.partial_order[node] = {'level':level, 'mark':0}
 186             if parent:
 187                 tree.append((parent, node))
 188
 189         if self.partial_order[node]['mark']==0:
 190             self.partial_order[node]['mark'] = 1
 191             for t in self.transitions.get(node, []):
 192                 self.links.append((node, t))
 193                 self.make_acyclic(node, t, level+1, tree)
 194
 195         return tree
 196
 197
 198     def rev_edges(self, tree):
 199         """reverse the direction of the edges whose source-node-partail_order> destination-node-partail_order
 200         to make the graph acyclic
 201         """
 202         Is_Cyclic = False
 203         i=0
 204         for link in self.links:
 205             src = link[0]
 206             des = link[1]
 207             edge_len = self.partial_order[des]['level'] - self.partial_order[src]['level']
 208             if edge_len < 0:
 209                 self.links.__delitem__(i)
 210                 self.links.insert(i, (des, src))
 211                 self.transitions[src].remove(des)
 212                 self.transitions.setdefault(des, []).append(src)
 213                 Is_Cyclic = True
 214             elif math.fabs(edge_len) > 1:
 215                 Is_Cyclic = True
 216             i += 1
 217
 218         return Is_Cyclic
 219
 220     def exchange(self, e, f):
 221         """Exchange edges to make feasible-tree optimized
 222         @param edge: edge with negative cut-value
 223         @param edge: new edge with minimum slack-value
 224         """
 225         self.tree_edges.__delitem__(self.tree_edges.index(e))
 226         self.tree_edges.append(f)
 227         self.init_cutvalues()
 228
 229
 230     def enter_edge(self, edge):
 231         """Finds a new_edge with minimum slack value to replace an edge with negative cut-value
 232
 233         @param edge: edge with negative cut-value
 234         """
 235
 236         self.head_nodes = []
 237         rest_edges = []
 238         rest_edges += self.tree_edges
 239         rest_edges.__delitem__(rest_edges.index(edge))
 240         self.head_component(self.start, rest_edges)
 241
 242         if self.head_nodes.__contains__(edge[1]):
 243             list = []
 244             for node in self.result:
 245                 if not self.head_nodes.__contains__(node):
 246                     list.append(node)
 247             self.head_nodes = list
 248
 249         slack = 100
 250         new_edge = edge
 251         for source_node in self.transitions:
 252             if source_node in self.head_nodes:
 253                 for dest_node in self.transitions[source_node]:
 254                     if dest_node not in self.head_nodes:
 255                         if(slack>(self.edge_wt[edge]-1)):
 256                             slack = self.edge_wt[edge]-1
 257                             new_edge = (source_node,dest_node)
 258         return new_edge
 259
 260
 261     def leave_edge(self):
 262         """Returns the edge with negative cut_value(if exists)
 263         """
 264         if self.critical_edges:
 265             for edge in self.critical_edges:
 266                 self.cut_edges[edge] = 0
 267
 268         for edge in self.cut_edges:
 269             if self.cut_edges[edge]<0:
 270                 return edge
 271         return None
 272
 273
 274     def finalize_rank(self, node, level):
 275         self.result[node]['y'] = level
 276         for destination in self.optimal_edges.get(node, []):
 277             self.finalize_rank(destination, level+1)
 278
 279
 280     def normalize(self):
 281         """The ranks are normalized by setting the least rank to zero.
 282         """
 283
 284         least_rank=100
 285
 286         for node in self.result:
 287             if least_rank>self.result[node]['y']:
 288                 least_rank = self.result[node]['y']
 289
 290         if(least_rank!=0):
 291             for node in self.result:
 292                 self.result[node]['y']-=least_rank
 293
 294
 295     def make_chain(self):
 296         """Edges between nodes more than one rank apart are replaced by chains of unit
 297            length edges between temporary nodes.
 298         """
 299
 300         for edge in self.edge_wt:
 301             if self.edge_wt[edge]>1:
 302                 self.transitions[edge[0]].remove(edge[1])
 303                 start = self.result[edge[0]]['y']
 304                 end = self.result[edge[1]]['y']
 305
 306                 for rank in range(start+1, end):
 307                     if not self.result.get((rank, 'temp'), False):
 308                         self.result[(rank, 'temp')] = {'x': None, 'y': rank, 'mark': 0}
 309
 310                 for rank in range(start, end):
 311                     if start==rank:
 312                         self.transitions[edge[0]].append((rank+1, 'temp'))
 313                     elif rank==end-1:
 314                         self.transitions.setdefault((rank, 'temp'), []).append(edge[1])
 315                     else:
 316                         self.transitions.setdefault((rank, 'temp'), []).append((rank+1, 'temp'))
 317
 318
 319     def init_order(self, node, level):
 320         """Initialize orders the nodes in each rank with depth-first search
 321         """
 322         if not self.result[node]['x']:
 323             self.result[node]['x'] = self.order[level]
 324             self.order[level] = self.order[level]+1
 325
 326         for sec_end in self.transitions.get(node, []):
 327             self.init_order(sec_end, self.result[sec_end]['y'])
 328
 329
 330     def order_heuristic(self):
 331         for i in range(12):
 332             self.wmedian()
 333
 334
 335     def wmedian(self):
 336         """Applies median heuristic to find optimzed order of the nodes with in their ranks
 337         """
 338         for level in self.levels:
 339
 340             node_median = []
 341             for node in self.levels[level]:
 342                 node_median.append((node, self.median_value(node, level-1)))
 343
 344             sort_list = sorted(node_median, key=operator.itemgetter(1))
 345
 346             new_list = [tuple[0] for tuple in sort_list]
 347
 348             self.levels[level] = new_list
 349             order = 0
 350             for node in self.levels[level]:
 351                 self.result[node]['x'] = order
 352                 order +=1
 353
 354
 355
 356
 357     def median_value(self, node, adj_rank):
 358         """Returns median value of a vertex , defined as the median position of the adjacent vertices
 359
 360         @param node: node to process
 361         @param adj_rank: rank 1 less than the node's rank
 362         """
 363         adj_nodes = self.adj_position(node, adj_rank)
 364         l = len(adj_nodes)
 365         m = l/2
 366
 367         if l==0:
 368             return -1.0
 369         elif l%2 == 1:
 370             return adj_nodes[m]#median of the middle element
 371         elif l==2:
 372             return (adj_nodes[0]+adj_nodes[1])/2
 373         else:
 374             left = adj_nodes[m-1] - adj_nodes[0]
 375             right = adj_nodes[l-1] - adj_nodes[m]
 376             return ((adj_nodes[m-1]*right) + (adj_nodes[m]*left))/(left+right)
 377
 378
 379     def adj_position(self, node, adj_rank):
 380         """Returns list of the present positions of the nodes adjacent to node in the given adjacent rank.
 381
 382         @param node: node to process
 383         @param adj_rank: rank 1 less than the node's rank
 384         """
 385
 386         pre_level_nodes = self.levels.get(adj_rank)
 387
 388         adj_nodes = []
 389         if pre_level_nodes:
 390             for n in pre_level_nodes:
 391                 if (self.transitions.get(n) and self.transitions[n].__contains__(node)):
 392                     adj_nodes.append(self.result[n]['x'])
 393
 394         return adj_nodes
 395
 396
 397     def preprocess_order(self):
 398         levels = {}
 399         for r in self.partial_order:
 400             l = self.result[r]['y']
 401             levels.setdefault(l,[])
 402             levels[l].append(r)
 403         self.levels = levels
 404
 405
 406     def graph_order(self):
 407         """Finds actual-order of the nodes with respect to maximum number of nodes in a rank in component
 408         """
 409         mid_pos = None
 410         max_level = max(map(lambda x: len(x), self.levels.values()))
 411
 412         for level in self.levels:
 413             if level:
 414                 no = len(self.levels[level])
 415                 factor = (max_level - no) * 0.10
 416                 self.levels[level].reverse()
 417                 list = self.levels[level]
 418
 419                 if no%2==0:
 420                     first_half = list[no/2:]
 421                     factor = -factor
 422                 else:
 423                     first_half = list[no/2+1:]
 424                     if max_level==1:
 425                         self.result[list[no/2]]['x'] = mid_pos + (self.result[list[no/2]]['y']%2 * 0.5)
 426                     else:
 427                         self.result[list[no/2]]['x'] = mid_pos + factor
 428
 429                 last_half = list[:no/2]
 430                 i=1
 431                 for node in first_half:
 432                     self.result[node]['x'] = mid_pos - (i + factor)
 433                     i += 1
 434
 435                 i=1
 436                 for node in last_half:
 437                     self.result[node]['x'] = mid_pos + (i + factor)
 438                     i += 1
 439             else:
 440                 self.max_order += max_level+1
 441                 mid_pos = self.result[self.start]['x']
 442
 443
 444     def tree_order(self, node, last=0):
 445         mid_pos = self.result[node]['x']
 446         l = self.transitions[node]
 447         l.reverse()
 448         no = len(l)
 449         if no%2==0:
 450             first_half = l[no/2:]
 451             factor = 1
 452         else:
 453             first_half = l[no/2+1:]
 454             factor = 0
 455
 456         last_half = l[:no/2]
 457
 458         i=1
 459         for child in first_half:
 460             self.result[child]['x'] = mid_pos - (i - (factor * 0.5))
 461             i += 1
 462
 463             if self.transitions.get(child, False):
 464                 if last:
 465                     self.result[child]['x'] = last + len(self.transitions[child])/2 + 1
 466                 last = self.tree_order(child, last)
 467
 468         if no%2:
 469             mid_node = l[no/2]
 470             self.result[mid_node]['x'] = mid_pos
 471
 472             if self.transitions.get((mid_node), False):
 473                 if last:
 474                     self.result[mid_node]['x'] = last + len(self.transitions[mid_node])/2 + 1
 475                 last = self.tree_order(mid_node)
 476             else:
 477                 if last:
 478                     self.result[mid_node]['x'] = last + 1
 479             self.result[node]['x'] = self.result[mid_node]['x']
 480             mid_pos = self.result[node]['x']
 481
 482         i=1
 483         last_child = None
 484         for child in last_half:
 485             self.result[child]['x'] = mid_pos + (i - (factor * 0.5))
 486             last_child = child
 487             i += 1
 488             if self.transitions.get(child, False):
 489                 if last:
 490                     self.result[child]['x'] = last + len(self.transitions[child])/2 + 1
 491                 last = self.tree_order(child, last)
 492         if last_child:
 493             last = self.result[last_child]['x']
 494         return last
 495
 496
 497     def process_order(self):
 498         """Finds actual-order of the nodes with respect to maximum number of nodes in a rank in component
 499         """
 500         max_level = max(map(lambda x: len(x), self.levels.values()))
 501         if max_level%2:
 502             self.result[self.start]['x'] = (max_level+1)/2 + self.max_order
 503         else:
 504             self.result[self.start]['x'] = (max_level)/2 + self.max_order
 505
 506         if self.Is_Cyclic:
 507             self.graph_order()
 508         else:
 509             self.result[self.start]['x'] = 0
 510             self.tree_order(self.start, 0)
 511             min_order = math.fabs(min(map(lambda x: x['x'], self.result.values())))
 512             for node in self.result:
 513                 self.result[node]['x'] += min_order
 514
 515
 516     def find_starts(self):
 517         """Finds other start nodes of the graph in the case when graph is disconneted
 518         """
 519         rem_nodes = []
 520         for node in self.nodes:
 521             if not self.partial_order.get(node):
 522                 rem_nodes.append(node)
 523         cnt = 0
 524         while True:
 525             if len(rem_nodes)==1:
 526                 self.start_nodes.append(rem_nodes[0])
 527                 break
 528             else:
 529                 count = 0
 530                 new_start = rem_nodes[0]
 531                 largest_tree = []
 532                 for node in rem_nodes:
 533                     self.partial_order = {}
 534                     tree = self.make_acyclic(None, node, 0, [])
 535                     if len(tree)+1 > count:
 536                         count = len(tree) + 1
 537                         new_start = node
 538                         largest_tree = tree
 539
 540                 self.start_nodes.append(new_start)
 541
 542                 for edge in largest_tree:
 543                     if rem_nodes.__contains__(edge[0]):
 544                         rem_nodes.remove(edge[0])
 545                     if rem_nodes.__contains__(edge[1]):
 546                         rem_nodes.remove(edge[1])
 547
 548                 if not rem_nodes:
 549                     break
 550
 551
 552     def rank(self):
 553         """Finds the optimized rank of the nodes using Network-simplex algorithm
 554
 555         @param start: starting node of the component
 556         """
 557         self.levels = {}
 558         self.critical_edges = []
 559         self.partial_order = {}
 560         self.links = []
 561         self.Is_Cyclic = False
 562
 563         tree = self.make_acyclic(None, self.start, 0, [])
 564         self.Is_Cyclic = self.rev_edges(tree)
 565         self.process_ranking(self.start)
 566         self.init_rank()
 567
 568         #make cut values of all tree edges to 0 to optimize feasible tree
 569         e = self.leave_edge()
 570
 571         while e :
 572             f = self.enter_edge(e)
 573             if e==f:
 574                 self.critical_edges.append(e)
 575             else:
 576                 self.exchange(e,f)
 577             e = self.leave_edge()
 578
 579         #finalize rank using optimum feasible tree
 580         self.optimal_edges = {}
 581         for edge in self.tree_edges:
 582             source = self.optimal_edges.setdefault(edge[0], [])
 583             source.append(edge[1])
 584
 585         self.finalize_rank(self.start, 0)
 586
 587         #normalization
 588 #        self.normalize()
 589         for edge in self.edge_wt:
 590             self.edge_wt[edge] = self.result[edge[1]]['y'] - self.result[edge[0]]['y']
 591
 592     def order_in_rank(self):
 593         """Finds optimized order of the nodes within their ranks using median heuristic
 594
 595         @param start: starting node of the component
 596         """
 597
 598         self.make_chain()
 599         self.preprocess_order()
 600         self.order = {}
 601         max_rank = max(map(lambda x: x, self.levels.keys()))
 602         for i in range(max_rank+1):
 603             self.order[i] = 0
 604
 605         self.init_order(self.start, self.result[self.start]['y'])
 606
 607         for level in self.levels:
 608             self.levels[level].sort(lambda x,y: cmp(self.result[x]['x'], self.result[y]['x']))
 609
 610         self.order_heuristic()
 611
 612         for level in self.levels:
 613             for node in self.levels[level]:
 614                 try:
 615                     if int(node):
 616                         continue
 617                 except ValueError:
 618                     self.levels[level].remove(node)
 619                     self.result.__delitem__(node)
 620         self.process_order()
 621
 622
 623     def process(self, starting_node):
 624         """Process the graph to find ranks and order of the nodes
 625
 626         @param starting_node: node from where to start the graph search
 627         """
 628
 629         self.start_nodes = starting_node or []
 630         self.partial_order = {}
 631         self.links = []
 632
 633         if self.nodes:
 634             if self.start_nodes:
 635                 #add dummy edges to the nodes which does not have any incoming edges
 636                 for node in self.no_ancester:
 637                     self.transitions[self.start_nodes[0]].append(node)
 638
 639
 640                 tree = self.make_acyclic(None, self.start_nodes[0], 0, [])
 641
 642
 643             # if graph is disconnected or no start-node is given
 644             #than to find starting_node for each component of the node
 645             if len(self.nodes) > len(self.partial_order):
 646                 self.find_starts()
 647
 648
 649             self.max_order = 0
 650
 651             #for each component of the graph find ranks and order of the nodes
 652             for s in self.start_nodes:
 653                 self.start = s
 654                 self.rank()   # First step:Netwoek simplex algorithm
 655                 self.order_in_rank()    #Second step: ordering nodes within ranks
 656
 657
 658     def __str__(self):
 659         result = ''
 660         for l in self.levels:
 661             result += 'PosY: ' + str(l) + '\n'
 662             for node in self.levels[l]:
 663                 result += '\tPosX: '+ str(self.result[node]['x']) + '  - Node:' + node + "\n"
 664         return result
 665
 666     def scale(self, maxx, maxy, plusx2=0, plusy2=0):
 667         """Computes actual co-ordiantes of the nodes
 668         """
 669
 670         for r in self.result:
 671             self.result[r]['x'] = (self.result[r]['x']) * maxx + plusx2
 672             self.result[r]['y'] = (self.result[r]['y']) * maxy + plusy2
 673
 674     def result_get(self):
 675         return self.result
 676
 677 if __name__=='__main__':
 678     starting_node = ['profile']  # put here nodes with flow_start=True
 679     nodes = ['project','account','hr','base','product','mrp','test','profile']
 680     transitions = [
 681         ('profile','mrp'),
 682         ('mrp','project'),
 683         ('project','product'),
 684         ('mrp','hr'),
 685         ('mrp','test'),
 686         ('project','account'),
 687         ('project','hr'),
 688         ('product','base'),
 689         ('account','product'),
 690         ('account','test'),
 691         ('account','base'),
 692         ('hr','base'),
 693         ('test','base')
 694     ]
 695
 696     radius = 20
 697     g = graph(nodes, transitions)
 698     g.process(starting_node)
 699     g.scale(radius*3,radius*3, radius, radius)
 700
 701     print g
 702
 703     import Image
 704     import ImageDraw
 705     img = Image.new("RGB", (800, 600), "#ffffff")
 706     draw = ImageDraw.Draw(img)
 707
 708     for name,node in g.result.items():
 709         draw.arc( (int(node['x']-radius), int(node['y']-radius),int(node['x']+radius), int(node['y']+radius) ), 0, 360, (128,128,128))
 710         draw.text( (int(node['x']),  int(node['y'])), name,  (128,128,128))
 711
 712
 713     for nodefrom in g.transitions:
 714         for nodeto in g.transitions[nodefrom]:
 715             draw.line( (int(g.result[nodefrom]['x']), int(g.result[nodefrom]['y']),int(g.result[nodeto]['x']),int(g.result[nodeto]['y'])),(128,128,128) )
 716
 717     img.save("graph.png", "PNG")
 718
 719
 720 # vim:expandtab:smartindent:tabstop=4:softtabstop=4:shiftwidth=4:
 721