bin/tools/graph.py

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