class graph(object):
def __init__(self, nodes, transitions, no_ancester=None):
- """Initailize graph's object
+ """Initialize graph's object
- @param nodes: list of ids of nodes in the graph
- @param transitions: list of edges in the graph in the form (source_node, destination_node)
- @param no_ancester: list of nodes with no incoming edges
+ @param nodes list of ids of nodes in the graph
+ @param transitions list of edges in the graph in the form (source_node, destination_node)
+ @param no_ancester list of nodes with no incoming edges
"""
self.nodes = nodes or []
for link in self.links:
self.edge_wt[link] = self.result[link[1]]['x'] - self.result[link[0]]['x']
- tot_node = self.partial_order.__len__()
+ tot_node = len(self.partial_order)
#do until all the nodes in the component are searched
while self.tight_tree()<tot_node:
list_node = []
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.edge_wt[edge]-1):
+ if ((edge[0] in self.reachable_nodes and edge[1] not in self.reachable_nodes) or
+ (edge[1] in self.reachable_nodes and edge[0] not in self.reachable_nodes)):
+ if slack > self.edge_wt[edge]-1:
slack = self.edge_wt[edge]-1
new_edge = edge
self.reachable_nodes = []
self.tree_edges = []
self.reachable_node(self.start)
- return self.reachable_nodes.__len__()
+ return len(self.reachable_nodes)
def reachable_node(self, node):
"""
self.cut_edges = {}
self.head_nodes = []
- i=0;
+ i=0
for edge in self.tree_edges:
self.head_nodes = []
rest_edges = []
rest_edges += self.tree_edges
- rest_edges.__delitem__(i)
+ del rest_edges[i]
self.head_component(self.start, rest_edges)
i+=1
positive = 0
des = link[1]
edge_len = self.partial_order[des]['level'] - self.partial_order[src]['level']
if edge_len < 0:
- self.links.__delitem__(i)
+ del self.links[i]
self.links.insert(i, (des, src))
self.transitions[src].remove(des)
self.transitions.setdefault(des, []).append(src)
def exchange(self, e, f):
"""Exchange edges to make feasible-tree optimized
- @param edge: edge with negative cut-value
- @param edge: new edge with minimum slack-value
+ :param e: edge with negative cut-value
+ :param f: new edge with minimum slack-value
"""
- self.tree_edges.__delitem__(self.tree_edges.index(e))
+ del self.tree_edges[self.tree_edges.index(e)]
self.tree_edges.append(f)
self.init_cutvalues()
def enter_edge(self, edge):
"""Finds a new_edge with minimum slack value to replace an edge with negative cut-value
- @param edge: edge with negative cut-value
+ @param edge edge with negative cut-value
"""
self.head_nodes = []
rest_edges = []
rest_edges += self.tree_edges
- rest_edges.__delitem__(rest_edges.index(edge))
+ del rest_edges[rest_edges.index(edge)]
self.head_component(self.start, rest_edges)
- if self.head_nodes.__contains__(edge[1]):
+ if edge[1] in self.head_nodes:
l = []
for node in self.result:
- if not self.head_nodes.__contains__(node):
+ if node not in self.head_nodes:
l.append(node)
self.head_nodes = l
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.edge_wt[edge]-1)):
+ if slack>(self.edge_wt[edge]-1):
slack = self.edge_wt[edge]-1
new_edge = (source_node, dest_node)
least_rank = min(map(lambda x: x['x'], self.result.values()))
- if(least_rank!=0):
+ if least_rank!=0:
for node in self.result:
self.result[node]['x']-=least_rank
"""
if not self.result[node]['y']:
self.result[node]['y'] = self.order[level]
- self.order[level] = self.order[level]+1
+ self.order[level] += 1
for sec_end in self.transitions.get(node, []):
- self.init_order(sec_end, self.result[sec_end]['x'])
+ if node!=sec_end:
+ self.init_order(sec_end, self.result[sec_end]['x'])
def order_heuristic(self):
def median_value(self, node, adj_rank):
"""Returns median value of a vertex , defined as the median position of the adjacent vertices
- @param node: node to process
- @param adj_rank: rank 1 less than the node's rank
+ @param node node to process
+ @param adj_rank rank 1 less than the node's rank
"""
adj_nodes = self.adj_position(node, adj_rank)
l = len(adj_nodes)
def adj_position(self, node, adj_rank):
"""Returns list of the present positions of the nodes adjacent to node in the given adjacent rank.
- @param node: node to process
- @param adj_rank: rank 1 less than the node's rank
+ @param node node to process
+ @param adj_rank rank 1 less than the node's rank
"""
pre_level_nodes = self.levels.get(adj_rank, [])
if pre_level_nodes:
for src in pre_level_nodes:
- if (self.transitions.get(src) and self.transitions[src].__contains__(node)):
+ if self.transitions.get(src) and node in self.transitions[src]:
adj_nodes.append(self.result[src]['y'])
return adj_nodes
l.reverse()
no = len(l)
- if no%2==0:
- first_half = l[no/2:]
- factor = 1
- else:
- first_half = l[no/2+1:]
- factor = 0
-
+ rest = no%2
+ first_half = l[no/2+rest:]
last_half = l[:no/2]
- i=1
- for child in first_half:
- self.result[child]['y'] = mid_pos - (i - (factor * 0.5))
- i += 1
+ for i, child in enumerate(first_half):
+ self.result[child]['y'] = mid_pos - (i+1 - (0 if rest else 0.5))
if self.transitions.get(child, False):
if last:
self.result[child]['y'] = last + len(self.transitions[child])/2 + 1
last = self.tree_order(child, last)
- if no%2:
+ if rest:
mid_node = l[no/2]
self.result[mid_node]['y'] = mid_pos
- if self.transitions.get((mid_node), False):
+ if self.transitions.get(mid_node, False):
if last:
self.result[mid_node]['y'] = last + len(self.transitions[mid_node])/2 + 1
- last = self.tree_order(mid_node)
+ if node!=mid_node:
+ last = self.tree_order(mid_node)
else:
if last:
self.result[mid_node]['y'] = last + 1
i=1
last_child = None
for child in last_half:
- self.result[child]['y'] = mid_pos + (i - (factor * 0.5))
+ self.result[child]['y'] = mid_pos + (i - (0 if rest else 0.5))
last_child = child
i += 1
if self.transitions.get(child, False):
if last:
self.result[child]['y'] = last + len(self.transitions[child])/2 + 1
- last = self.tree_order(child, last)
+ if node!=child:
+ last = self.tree_order(child, last)
if last_child:
last = self.result[last_child]['y']
if max_level%2:
self.result[self.start]['y'] = (max_level+1)/2 + self.max_order + (self.max_order and 1)
else:
- self.result[self.start]['y'] = (max_level)/2 + self.max_order + (self.max_order and 1)
+ self.result[self.start]['y'] = max_level /2 + self.max_order + (self.max_order and 1)
self.graph_order()
for start in self.start_nodes[:index]:
same = True
for edge in self.tree_list[start][1:]:
- if self.tree_list[self.start].__contains__(edge):
+ if edge in self.tree_list[self.start]:
continue
else:
same = False
for edge in largest_tree:
- if rem_nodes.__contains__(edge[0]):
+ if edge[0] in rem_nodes:
rem_nodes.remove(edge[0])
- if rem_nodes.__contains__(edge[1]):
+ if edge[1] in rem_nodes:
rem_nodes.remove(edge[1])
if not rem_nodes:
def rank(self):
"""Finds the optimized rank of the nodes using Network-simplex algorithm
-
- @param start: starting node of the component
"""
self.levels = {}
self.critical_edges = []
def order_in_rank(self):
"""Finds optimized order of the nodes within their ranks using median heuristic
-
- @param start: starting node of the component
"""
self.make_chain()
def process(self, starting_node):
"""Process the graph to find ranks and order of the nodes
- @param starting_node: node from where to start the graph search
+ @param starting_node node from where to start the graph search
"""
self.start_nodes = starting_node or []
#for flat edges ie. source an destination nodes are on the same rank
for src in self.transitions:
for des in self.transitions[src]:
- if (self.result[des]['x'] - self.result[src]['x'] == 0):
+ if self.result[des]['x'] - self.result[src]['x'] == 0:
self.result[src]['x'] += 0.08
self.result[des]['x'] -= 0.08
g.process(starting_node)
g.scale(radius*3,radius*3, radius, radius)
- import Image
- import ImageDraw
+ from PIL import Image
+ from PIL import ImageDraw
img = Image.new("RGB", (800, 600), "#ffffff")
draw = ImageDraw.Draw(img)
projects / odoo / odoo.git / blobdiff