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