2 # -*- coding: utf-8 -*-
3 ##############################################################################
5 # OpenERP, Open Source Management Solution
6 # Copyright (C) 2004-2009 Tiny SPRL (<http://tiny.be>).
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.
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.
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/>.
21 ##############################################################################
27 def __init__(self, nodes, transitions, no_ancester=None):
28 """Initialize graph's object
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
35 self.nodes = nodes or []
36 self.edges = transitions or []
37 self.no_ancester = no_ancester or {}
41 trans.setdefault(t[0], [])
42 trans[t[0]].append(t[1])
43 self.transitions = trans
48 """Computes rank of the nodes of the graph by finding initial feasible tree
51 for link in self.links:
52 self.edge_wt[link] = self.result[link[1]]['x'] - self.result[link[0]]['x']
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:
60 for node in self.nodes:
61 if node not in self.reachable_nodes:
62 list_node.append(node)
64 for edge in self.edge_wt:
65 if edge not in self.tree_edges:
66 list_edge.append(edge)
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
77 if new_edge[0] not in self.reachable_nodes:
78 delta = -(self.edge_wt[new_edge]-1)
80 delta = self.edge_wt[new_edge]-1
82 for node in self.result:
83 if node in self.reachable_nodes:
84 self.result[node]['x'] += delta
86 for edge in self.edge_wt:
87 self.edge_wt[edge] = self.result[edge[1]]['x'] - self.result[edge[0]]['x']
93 self.reachable_nodes = []
95 self.reachable_node(self.start)
96 return self.reachable_nodes.__len__()
99 def reachable_node(self, node):
100 """Find the nodes of the graph which are only 1 rank apart from each other
103 if node not in self.reachable_nodes:
104 self.reachable_nodes.append(node)
105 for edge in self.edge_wt:
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])
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
122 for edge in self.tree_edges:
125 rest_edges += self.tree_edges
126 rest_edges.__delitem__(i)
127 self.head_component(self.start, rest_edges)
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:
137 for dest_node in self.transitions[source_node]:
138 if dest_node in self.head_nodes:
141 self.cut_edges[edge] = positive - negative
144 def head_component(self, node, rest_edges):
145 """Find nodes which are reachable from the starting node, after removing an edge
147 if node not in self.head_nodes:
148 self.head_nodes.append(node)
150 for edge in rest_edges:
152 self.head_component(edge[1],rest_edges)
155 def process_ranking(self, node, level=0):
156 """Computes initial feasible ranking after making graph acyclic with depth-first search
159 if node not in self.result:
160 self.result[node] = {'y': None, 'x':level, 'mark':0}
162 if level > self.result[node]['x']:
163 self.result[node]['x'] = level
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)
171 def make_acyclic(self, parent, node, level, tree):
172 """Computes Partial-order of the nodes with depth-first search
175 if node not in self.partial_order:
176 self.partial_order[node] = {'level':level, 'mark':0}
178 tree.append((parent, node))
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)
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
195 for link in self.links:
198 edge_len = self.partial_order[des]['level'] - self.partial_order[src]['level']
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)
205 elif math.fabs(edge_len) > 1:
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
216 self.tree_edges.__delitem__(self.tree_edges.index(e))
217 self.tree_edges.append(f)
218 self.init_cutvalues()
221 def enter_edge(self, edge):
222 """Finds a new_edge with minimum slack value to replace an edge with negative cut-value
224 @param edge edge with negative cut-value
229 rest_edges += self.tree_edges
230 rest_edges.__delitem__(rest_edges.index(edge))
231 self.head_component(self.start, rest_edges)
233 if self.head_nodes.__contains__(edge[1]):
235 for node in self.result:
236 if not self.head_nodes.__contains__(node):
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)
253 def leave_edge(self):
254 """Returns the edge with negative cut_value(if exists)
256 if self.critical_edges:
257 for edge in self.critical_edges:
258 self.cut_edges[edge] = 0
260 for edge in self.cut_edges:
261 if self.cut_edges[edge]<0:
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)
274 """The ranks are normalized by setting the least rank to zero.
277 least_rank = min(map(lambda x: x['x'], self.result.values()))
280 for node in self.result:
281 self.result[node]['x']-=least_rank
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.
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']
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}
299 for rank in range(start, end):
301 self.transitions[edge[0]].append((rank+1, 'temp'))
303 self.transitions.setdefault((rank, 'temp'), []).append(edge[1])
305 self.transitions.setdefault((rank, 'temp'), []).append((rank+1, 'temp'))
308 def init_order(self, node, level):
309 """Initialize orders the nodes in each rank with depth-first search
311 if not self.result[node]['y']:
312 self.result[node]['y'] = self.order[level]
313 self.order[level] = self.order[level]+1
315 for sec_end in self.transitions.get(node, []):
317 self.init_order(sec_end, self.result[sec_end]['x'])
320 def order_heuristic(self):
326 """Applies median heuristic to find optimzed order of the nodes with in their ranks
328 for level in self.levels:
331 nodes = self.levels[level]
333 node_median.append((node, self.median_value(node, level-1)))
335 sort_list = sorted(node_median, key=operator.itemgetter(1))
337 new_list = [tuple[0] for tuple in sort_list]
339 self.levels[level] = new_list
342 self.result[node]['y'] = order
346 def median_value(self, node, adj_rank):
347 """Returns median value of a vertex , defined as the median position of the adjacent vertices
349 @param node node to process
350 @param adj_rank rank 1 less than the node's rank
352 adj_nodes = self.adj_position(node, adj_rank)
359 return adj_nodes[m]#median of the middle element
361 return (adj_nodes[0]+adj_nodes[1])/2
363 left = adj_nodes[m-1] - adj_nodes[0]
364 right = adj_nodes[l-1] - adj_nodes[m]
365 return ((adj_nodes[m-1]*right) + (adj_nodes[m]*left))/(left+right)
368 def adj_position(self, node, adj_rank):
369 """Returns list of the present positions of the nodes adjacent to node in the given adjacent rank.
371 @param node node to process
372 @param adj_rank rank 1 less than the node's rank
375 pre_level_nodes = self.levels.get(adj_rank, [])
379 for src in pre_level_nodes:
380 if (self.transitions.get(src) and self.transitions[src].__contains__(node)):
381 adj_nodes.append(self.result[src]['y'])
386 def preprocess_order(self):
389 for r in self.partial_order:
390 l = self.result[r]['x']
391 levels.setdefault(l,[])
397 def graph_order(self):
398 """Finds actual-order of the nodes with respect to maximum number of nodes in a rank in component
401 max_level = max(map(lambda x: len(x), self.levels.values()))
403 for level in self.levels:
405 no = len(self.levels[level])
406 factor = (max_level - no) * 0.10
407 list = self.levels[level]
411 first_half = list[no/2:]
414 first_half = list[no/2+1:]
415 if max_level==1:#for the case when horizontal graph is there
416 self.result[list[no/2]]['y'] = mid_pos + (self.result[list[no/2]]['x']%2 * 0.5)
418 self.result[list[no/2]]['y'] = mid_pos + factor
420 last_half = list[:no/2]
423 for node in first_half:
424 self.result[node]['y'] = mid_pos - (i + factor)
428 for node in last_half:
429 self.result[node]['y'] = mid_pos + (i + factor)
432 self.max_order += max_level+1
433 mid_pos = self.result[self.start]['y']
436 def tree_order(self, node, last=0):
437 mid_pos = self.result[node]['y']
438 l = self.transitions.get(node, [])
443 first_half = l[no/2+rest:]
446 for i, child in enumerate(first_half):
447 self.result[child]['y'] = mid_pos - (i+1 - (0 if rest else 0.5))
449 if self.transitions.get(child, False):
451 self.result[child]['y'] = last + len(self.transitions[child])/2 + 1
452 last = self.tree_order(child, last)
456 self.result[mid_node]['y'] = mid_pos
458 if self.transitions.get((mid_node), False):
460 self.result[mid_node]['y'] = last + len(self.transitions[mid_node])/2 + 1
462 last = self.tree_order(mid_node)
465 self.result[mid_node]['y'] = last + 1
466 self.result[node]['y'] = self.result[mid_node]['y']
467 mid_pos = self.result[node]['y']
471 for child in last_half:
472 self.result[child]['y'] = mid_pos + (i - (0 if rest else 0.5))
475 if self.transitions.get(child, False):
477 self.result[child]['y'] = last + len(self.transitions[child])/2 + 1
479 last = self.tree_order(child, last)
482 last = self.result[last_child]['y']
487 def process_order(self):
488 """Finds actual-order of the nodes with respect to maximum number of nodes in a rank in component
492 max_level = max(map(lambda x: len(x), self.levels.values()))
495 self.result[self.start]['y'] = (max_level+1)/2 + self.max_order + (self.max_order and 1)
497 self.result[self.start]['y'] = (max_level)/2 + self.max_order + (self.max_order and 1)
502 self.result[self.start]['y'] = 0
503 self.tree_order(self.start, 0)
504 min_order = math.fabs(min(map(lambda x: x['y'], self.result.values())))
506 index = self.start_nodes.index(self.start)
511 for start in self.start_nodes[:index]:
513 for edge in self.tree_list[start][1:]:
514 if self.tree_list[self.start].__contains__(edge):
523 min_order += self.max_order
525 min_order += self.max_order + 1
527 for level in self.levels:
528 for node in self.levels[level]:
529 self.result[node]['y'] += min_order
532 roots.append(self.start)
533 one_level_el = self.tree_list[self.start][0][1]
534 base = self.result[one_level_el]['y']# * 2 / (index + 2)
538 first_half = roots[:no/2]
541 last_half = roots[no/2:]
543 last_half = roots[no/2+1:]
545 factor = -math.floor(no/2)
546 for start in first_half:
547 self.result[start]['y'] = base + factor
551 self.result[roots[no/2]]['y'] = base + factor
554 for start in last_half:
555 self.result[start]['y'] = base + factor
558 self.max_order = max(map(lambda x: x['y'], self.result.values()))
560 def find_starts(self):
561 """Finds other start nodes of the graph in the case when graph is disconneted
564 for node in self.nodes:
565 if not self.partial_order.get(node):
566 rem_nodes.append(node)
569 if len(rem_nodes)==1:
570 self.start_nodes.append(rem_nodes[0])
574 new_start = rem_nodes[0]
577 for node in rem_nodes:
578 self.partial_order = {}
579 tree = self.make_acyclic(None, node, 0, [])
580 if len(tree)+1 > count:
581 count = len(tree) + 1
586 new_start = rem_nodes[0]
587 rem_nodes.remove(new_start)
589 self.start_nodes.append(new_start)
592 for edge in largest_tree:
593 if rem_nodes.__contains__(edge[0]):
594 rem_nodes.remove(edge[0])
595 if rem_nodes.__contains__(edge[1]):
596 rem_nodes.remove(edge[1])
603 """Finds the optimized rank of the nodes using Network-simplex algorithm
605 @param start starting node of the component
608 self.critical_edges = []
609 self.partial_order = {}
611 self.Is_Cyclic = False
613 self.tree_list[self.start] = self.make_acyclic(None, self.start, 0, [])
614 self.Is_Cyclic = self.rev_edges(self.tree_list[self.start])
615 self.process_ranking(self.start)
618 #make cut values of all tree edges to 0 to optimize feasible tree
619 e = self.leave_edge()
622 f = self.enter_edge(e)
624 self.critical_edges.append(e)
627 e = self.leave_edge()
629 #finalize rank using optimum feasible tree
630 # self.optimal_edges = {}
631 # for edge in self.tree_edges:
632 # source = self.optimal_edges.setdefault(edge[0], [])
633 # source.append(edge[1])
635 # self.finalize_rank(self.start, 0)
639 for edge in self.edge_wt:
640 self.edge_wt[edge] = self.result[edge[1]]['x'] - self.result[edge[0]]['x']
642 def order_in_rank(self):
643 """Finds optimized order of the nodes within their ranks using median heuristic
645 @param start: starting node of the component
649 self.preprocess_order()
651 max_rank = max(map(lambda x: x, self.levels.keys()))
653 for i in range(max_rank+1):
656 self.init_order(self.start, self.result[self.start]['x'])
658 for level in self.levels:
659 self.levels[level].sort(lambda x, y: cmp(self.result[x]['y'], self.result[y]['y']))
661 self.order_heuristic()
664 def process(self, starting_node):
665 """Process the graph to find ranks and order of the nodes
667 @param starting_node node from where to start the graph search
670 self.start_nodes = starting_node or []
671 self.partial_order = {}
677 #add dummy edges to the nodes which does not have any incoming edges
678 tree = self.make_acyclic(None, self.start_nodes[0], 0, [])
680 for node in self.no_ancester:
681 for sec_node in self.transitions.get(node, []):
682 if sec_node in self.partial_order.keys():
683 self.transitions[self.start_nodes[0]].append(node)
686 self.partial_order = {}
687 tree = self.make_acyclic(None, self.start_nodes[0], 0, [])
690 # if graph is disconnected or no start-node is given
691 #than to find starting_node for each component of the node
692 if len(self.nodes) > len(self.partial_order):
696 #for each component of the graph find ranks and order of the nodes
697 for s in self.start_nodes:
699 self.rank() # First step:Netwoek simplex algorithm
700 self.order_in_rank() #Second step: ordering nodes within ranks
705 for l in self.levels:
706 result += 'PosY: ' + str(l) + '\n'
707 for node in self.levels[l]:
708 result += '\tPosX: '+ str(self.result[node]['y']) + ' - Node:' + str(node) + "\n"
712 def scale(self, maxx, maxy, nwidth=0, nheight=0, margin=20):
713 """Computes actual co-ordiantes of the nodes
716 #for flat edges ie. source an destination nodes are on the same rank
717 for src in self.transitions:
718 for des in self.transitions[src]:
719 if (self.result[des]['x'] - self.result[src]['x'] == 0):
720 self.result[src]['x'] += 0.08
721 self.result[des]['x'] -= 0.08
723 factorX = maxx + nheight
724 factorY = maxy + nwidth
726 for node in self.result:
727 self.result[node]['y'] = (self.result[node]['y']) * factorX + margin
728 self.result[node]['x'] = (self.result[node]['x']) * factorY + margin
731 def result_get(self):
734 if __name__=='__main__':
735 starting_node = ['profile'] # put here nodes with flow_start=True
736 nodes = ['project','account','hr','base','product','mrp','test','profile']
740 ('project','product'),
743 ('project','account'),
746 ('account','product'),
754 g = graph(nodes, transitions)
755 g.process(starting_node)
756 g.scale(radius*3,radius*3, radius, radius)
758 from PIL import Image
759 from PIL import ImageDraw
760 img = Image.new("RGB", (800, 600), "#ffffff")
761 draw = ImageDraw.Draw(img)
763 result = g.result_get()
766 node_res[node] = result[node]
768 for name,node in node_res.items():
770 draw.arc( (int(node['y']-radius), int(node['x']-radius),int(node['y']+radius), int(node['x']+radius) ), 0, 360, (128,128,128))
771 draw.text( (int(node['y']), int(node['x'])), str(name), (128,128,128))
774 for t in transitions:
775 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) )
776 img.save("graph.png", "PNG")
779 # vim:expandtab:smartindent:tabstop=4:softtabstop=4:shiftwidth=4: