* Fixed `new graph` (partially implemented graph algorithem) (ref. ksh)

bzr revid: ame@tinyerp.com-9ece42d68ea21369777d7b927355a6fc4b01a517

1 files changed, 172 insertions, 6 deletions

diff --git a/bin/tools/graph.py b/bin/tools/graph.py
index 6dde9eee5d5..a90c9fe9705 100644
--- a/bin/tools/graph.py
+++ b/bin/tools/graph.py
@@ -3,6 +3,7 @@
 class graph(object):
 	def __init__(self, nodes, transitions):
 		self.nodes = nodes
+		self.links = transitions
 		trans = {}
 		for t in transitions:
 			trans.setdefault(t[0], [])
@@ -10,22 +11,134 @@ class graph(object):
 		self.transitions = trans
 		self.result = {}
 		self.levels = {}
+		
+	def get_parent(self,node):
+		count = 0
+		for item in self.transitions:
+			if self.transitions[item].__contains__(node):
+				count +=1
+		return count
+	
+	def init_rank(self):
+		self.temp = {}
+		for link in self.links:
+			self.temp[link] = self.result[link[1]]['y'] - self.result[link[0]]['y']
+		
+		cnt = 0
+		list_node = []
+		list_edge = []
+			
+		while self.tight_tree()<self.result.__len__():
+			cnt+=1
+			list_node = []
+			
+			for node in self.nodes:
+				if node not in self.reachable_nodes:
+					list_node.append(node)
+			list_edge = []
+			
+			for link in self.temp:
+				 if link not in self.tree_edges:
+				 	list_edge.append(link)
+			
+			slack = 100
+			
+			for edge in list_edge:
+				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):
+					if(slack>self.temp[edge]-1):
+						slack = self.temp[edge]-1
+						new_edge = edge
+						
+			if new_edge[0] not in self.reachable_nodes:
+				delta = -(self.temp[new_edge]-1)
+			else:
+				delta = self.temp[new_edge]-1
+				
+			for node in self.result:
+				if node in self.reachable_nodes:
+					self.result[node]['y'] += delta
+					
+			for link in self.temp:
+				self.temp[link] = self.result[link[1]]['y'] - self.result[link[0]]['y']		
+		
+		self.init_cutvalues()			
+		
+		
+		
+		
+	def tight_tree(self,):
+		self.reachable_nodes = []
+		self.tree_edges = []
+		self.reachable_node(self.start)	
+		return self.reachable_nodes.__len__()
+	
+	def reachable_node(self,node):
+		if node not in self.reachable_nodes:
+			self.reachable_nodes.append(node)
+		for link in self.temp:
+			if link[0]==node:
+#				print link[0]
+				if self.temp[link]==1:
+					self.tree_edges.append(link)
+					if link[1] not in self.reachable_nodes:
+						self.reachable_nodes.append(link[1])
+					self.reachable_node(link[1])
+					
+					
+	def init_cutvalues(self):
+		self.cut_edges = {}
+		self.head_nodes = []
+		i=0;
+		for edge in self.tree_edges:
+			self.head_nodes = []
+			rest_edges = []
+			rest_edges += self.tree_edges
+			rest_edges.__delitem__(i)
+			self.head_component(self.start,rest_edges)		
+			i+=1
+			positive = 0
+			negative = 0
+			for source_node in self.transitions:
+				if source_node in self.head_nodes:					
+					for dest_node in self.transitions[source_node]:
+						if dest_node not in self.head_nodes:
+							negative+=1
+				else:
+					for dest_node in self.transitions[source_node]:
+						if dest_node in self.head_nodes:
+							positive+=1
+
+			self.cut_edges[edge] = positive - negative
+		
+			
+
+				
+	def head_component(self, node, rest_edges):
+		if node not in self.head_nodes:
+			self.head_nodes.append(node)
+		for link in rest_edges:
+			if link[0]==node:		
+				self.head_component(link[1],rest_edges)
+		
 
 	def process_ranking(self, node, level=0):
 		if node not in self.result:
-			self.result[node] = {'x': None, 'y':level}
+			self.result[node] = {'x': None, 'y':level, 'mark':0}
 		else:
 			if level > self.result[node]['y']:
 				self.result[node]['y'] = level
-		for t in self.transitions.get(node, []):
-			self.process_ranking(t, level+1)
+		if self.result[node]['mark']==0:
+			self.result[node]['mark'] = 1
+			for t in self.transitions.get(node, []):
+				self.process_ranking(t, level+1)
+				
 
 	def preprocess_order(self):
 		levels = {}
 		for r in self.result:
 			l = self.result[r]['y']
 			levels.setdefault(l,[])
-			levels[l].append(r)
+			levels[l].append(r)			
 		self.levels = levels
 
 	def process_order(self, level):
@@ -54,18 +167,71 @@ class graph(object):
 				for n2 in self.transitions[node]:
 					self.result[n2]['x'] = pos
 					pos += step
+					
+	def exchange(self,e,f):
+		print e
+		print f
+					
+	def enter_edge(self,edge):
+		self.head_nodes = []
+		rest_edges = []
+		rest_edges += self.tree_edges
+		rest_edges.__delitem__(rest_edges.index(edge))
+		self.head_component(self.start,rest_edges)
+		slack = 100
+		for source_node in self.transitions:
+			if source_node in self.head_nodes:					
+				for dest_node in self.transitions[source_node]:
+					if dest_node not in self.head_nodes:
+						if(slack>(self.temp[edge]-1)):
+							slack = self.temp[edge]-1
+							new_edge = (source_node,dest_node)
+		return new_edge	
+						
+			
+
+	def leave_edge(self):
+		for edge in self.cut_edges:
+			if self.cut_edges[edge]<0:
+				return edge
+		return ()	
 
 	def process(self, starting_node):
 		pos = (len(starting_node) - 1.0)/2.0
+		self.start = starting_node[0]
 		for s in starting_node:
 			self.process_ranking(s)
 			self.result[s]['x'] = pos
 			pos += 1.0
-
+		self.init_rank()
+		#normalize
+		least_rank=100
+		
+		for node in self.result:
+			if least_rank>self.result[node]['y']:
+				least_rank = self.result[node]['y']
+		
+		if(least_rank!=0):
+			diff = least_rank
+			for node in self.result:
+				self.result[node]['y']-=least_rank
+					
+#		e = self.leave_edge()
+#		print '============e==============',e
+##		while e:
+#		f = self.enter_edge(e)
+#		print '=========f===============',f
+#		self.exchange(e,f) 
+#		e = self.leave_edge()	
+		
+			
+		
 		self.preprocess_order()
-
 		for n in self.levels:
 			self.process_order(n)
+			
+		
+			
 
 	def __str__(self):
 		result = ''