ASONAM2019/Greedy.py at master · PolynomialTime/ASONAM2019 · 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
import networkx as nx
import copy

INF = float("inf")

class Greedy:

    # initialization
    def __init__(self, graph, d, rho1, rho2, heuristic):
        self.G = graph
        self.d = d
        self.rho1 = rho1
        self.rho2 = rho2
        self.D1 = []
        self.D2 = []
        self.heuristic = heuristic

    # cimpute intersectio of two sets
    def intersection(self, lst1, lst2):
        lst3 = [value for value in lst1 if value in lst2]
        return lst3

    # compute cover set of a given node in a given set with a given distance rho
    # Pass Test
    def cover_set(self, node, rho, target_set):
        cover_set = []
        cover = nx.dfs_successors(self.G, node, rho)
        # print(cover)
        for x in cover.keys():
            for n in cover[x]:
                # print(n)
                if n in target_set:
                    cover_set.append(n)
        return cover_set


    # heuristic Max
    def Max(self, U, rho):
        max = -1
        node = 0

        for u in U:
            if  self.G.out_degree(u) > max:
                max = self.G.out_degree(u)
                node = u

        return node

    # heuristic Min
    def Min(self, U, rho):
        min = INF
        leaf = 0
        node = 0

        for u in U:
            if self.G.in_degree(u) < min:
                min = self.G.out_degree(u)
                leaf = u

        i = 0
        current = leaf
        while i <= rho:
            i += 1
            neigh = self.intersection(U, list(self.G.predecessors(current)) )
            if len(neigh) == 0:
                return current
            current = self.Max(neigh, 0)
        return current

    # heuristic Btw
    def Btw(self, U, rho):
        max = -1
        node = 0
        btw = nx.betweenness_centrality_subset(self.G, U, self.G.nodes(), False, None)
        for u in U:
            if btw[u]> max:
                max = btw[u]
                node = u
        return node

    # compute (D1,D2)
    def run(self):
        U =  list(copy.deepcopy(self.G.nodes()))
        # print(U)
        heu =''
        if self.heuristic == 'Max':
            heu = self.Max
        elif self.heuristic == 'Btw':
            heu = self.Btw
        else:
            heu = self.Min

        while len(self.D2) < self.d and len(U) > 0:
            s = heu(U, self.rho2)
            # print(s)
            self.D2.append(s)
            U.remove(s)
            cover = self.cover_set(s, self.rho2, U)
            # print(cover)
            # print(U)
            for c in cover:
                U.remove(c)

        while len(U) > 0:
            s = heu(U, self.rho1)
            self.D1.append(s)
            U.remove(s)
            cover = self.cover_set(s, self.rho1, U)
            for c in cover:
                U.remove(c)


#--------test 1------------
# G = nx.DiGraph([(1, 2), (2, 3), (1,3), (3,4), (2,4), (5,1), (2,5), (6,3), (7, 4), (5,7), (1,8), (8,5)])
# G = nx.DiGraph([(1,2), (1,3), (2,3)])
# g = Greedy(G, 1, 1, 2, 'Btw')
# g.run()
# print(g.D1, g.D2)


#--------test 2------------
# dic={1:[1,2],2:[2],3:[3],4:[0]}
# print (sorted(dic.items(),key= lambda d:d[1],reverse=False))
#distances = nx.shortest_path_length(G, 2, None, None, 'dijkstra')

#print(distances)


# 1 dict element
# 2 source not in return of DFS, remove from U


#--------test 3------------

#dic = {1:[1], 'r': [2]}
#print(dic)
#a = [1,2,3]
#print(str(a[0]) + ' ' + str(a[1]))