from collections import defaultdict
from pprint import pprint
class Graph:
def init(self):
self.inc_dct = defaultdict(list)
def __repr__(self):
return repr(self.inc_dct.items())
def get_nodes(self):
"""Returns set of vertices(keys of the dict)"""
return list(self.inc_dct.keys())
def get_children(self, node):
"""Returns children of the given vertice`s"""
return self.inc_dct[node]
def get_children_nodes(self, node):
"""Returns children of the given vertice`s"""
return list(map(lambda x: x[0], self.get_children(node)))
def get_parents(self, node):
parents = []
for nd in self.get_nodes():
if node in self.get_children_nodes(nd):
parents.append(nd)
return parents
def get_edge(self, nd1, nd2):
for nd in self.inc_dct[nd1]:
if nd[0] == nd2:
return nd[1]
def get_graph_algo(self, proc_a):
n_vertex = len(self.get_nodes())
n_edges = sum([len(i) for i in self.inc_dct.values()])
line_1 = str(n_vertex) + str(proc_a)
lst_1 = ['{} '.format(i.computation) * 3 for i in self.inc_dct.keys()]
lst_2 = [[-1 for _ in range(n_vertex)] for l in range(n_vertex)]
for num, i in enumerate(self.get_nodes()):
for inc_v in self.inc_dct[i]:
lst_2[num][self.get_nodes().index(inc_v[0])] = inc_v[1]
f=open('c:/test python/example_4.txt', 'wb')
f.write(line_1 + '\n ')
for i in lst_1: f.write(i + '\n')
for j in lst_2:
a = [str(i) for i in j]
f.write(' '.join(a) + '\n')
f.close()
def dijkstra(self, start):
visited = {start: 0}
path = dict()
nodes = self.get_nodes()
while nodes:
min_n = None
for node in nodes:
if node in visited:
if min_n is None:
min_n = node
elif visited[node] < visited[min_n]:
min_n = node
if min_n is None:
break
nodes.remove(min_n)
cur_weight = visited[min_n]
for edge in self.get_children(min_n):
weight = cur_weight + edge[0].computation + edge[1]
if edge[0] not in visited or weight < visited[edge[0]]:
visited[edge[0]] = weight
path[edge[0]] = min_n
return path
def get_cpn_list(self):
fst, lst = self.get_nodes()[0], self.get_nodes()[1]
path = self.dijkstra(fst)
last_item = self.get_nodes()[-1]
cpn_list = [last_item]
while last_item != fst:
last_item = path[last_item]
cpn_list.append(last_item)
return cpn_list[::-1]
def get_ibn_list(self):
cpn = self.get_cpn_list()
ibn = []
def check_ibn(graph, node, cpn):
for nd in graph.get_children_nodes(node):
if nd in cpn:
return True
if check_ibn(graph, nd, cpn):
return True
return False
for node in self.get_nodes():
if node not in cpn and check_ibn(self, node, cpn):
ibn.append(node)
return ibn
def get_obn_set(self):
nodes = set(self.get_nodes())
nodes -= set(self.get_cpn_list())
nodes -= set(self.get_ibn_list())
return list(nodes)
def topological_sort(self):
visited = defaultdict(bool)
nodes = []
def topological_sort_util(self, v, visited, nodes):
visited[v] = True
for i in self.get_children_nodes(v):
if visited[i] == False:
topological_sort_util(self, i, visited, nodes)
nodes.insert(0, v)
for i in self.get_nodes():
if visited[i] == False:
topological_sort_util(self, i, visited, nodes)
return nodes
class Node:
def init(self, ind, comp, trans):
self.index = ind
self.computation = comp
self.tranfering = trans
def __repr__(self):
return "Node( " + str(self.index) + ", " + str(
self.computation) + ', ' + str(self.tranfering) + " )"
def __cmp__(self, other):
if self.index == other.index and self.computation == other.computation:
return True
return False