Bubble-Scheduling/graph.py at master · Midren/Bubble-Scheduling · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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]
        with open('dag_v2.txt', 'w') as f:
            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')

    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