k_hop_dom_set.py 10.5 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon May 18 18:44:09 2020

@author: mario
"""
import networkx as nx
import gurobipy as gp
from gurobipy import GRB
import datetime
import sys
import matplotlib.pyplot as plt
14
import lp_to_nx_graph
15
from itertools import combinations
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

    
class DominatingSet:
    
    def __init__(self, G, name = "DS"):
        self.G = G
        self.m = gp.Model(name)
        self.nodes = self.m.addVars(G.nodes, vtype = GRB.BINARY, name = "nodes")
        self.m.setObjective(gp.quicksum(self.nodes), GRB.MINIMIZE)
    
        # For each node in the graph the node itself or at least one of it's neighbors has to be part of the dominating set
        self.m.addConstrs(((gp.quicksum(self.nodes[n] for n in G.neighbors(v)) + self.nodes[v] )>= 1) for v in G.nodes)

    def solve(self):
        ds = {i for i,x_i in enumerate(self.m.getVars()) if x_i.x == 1}
        return ds
    
    def solve_and_draw(self):
        starttime = datetime.datetime.now()
        ds = self.solve()
        endtime = datetime.datetime.now()
        duration = endtime- starttime
        duration_sec = duration.total_seconds()
        color_map = ['red' if i in ds else 'green' for i in self.G.nodes]
        print(f"duration in seconds: {duration_sec}")
        nx.draw_kamada_kawai(self.G, node_color = color_map, with_labels = True)
        plt.show()
        
    
class KHopDominatingSet(DominatingSet):
    
    def __init__(self, G, k, name = "kDS"):
        super().__init__(KHopDominatingSet.make_closure(G,k), name)
        self.G = G

    def make_closure(G, k):
        G_prime = nx.Graph(G)
        for v in G.nodes:
            neighbors = set(G.neighbors(v))
            for i in range(k-1):
                neighbors.update([w for n in neighbors for w in G.neighbors(n)])
            
            G_prime.add_edges_from((v,n) for n in neighbors)
        
        return G_prime

class ConnectedKHopDominatingSet(KHopDominatingSet):
    
64
    def __init__(self, G, k, name = "CkDS", exclude = {}):
65
66
        self.G = G
        super().__init__(G, k, name)
67
68
69
70
71
72
        
        if exclude:
            self.m.addConstrs(self.nodes[v] <= gp.quicksum(self.nodes[w] for w in G.neighbors(v)) for v in G.nodes if v not in exclude)
        else:
            self.m.addConstrs(self.nodes[v] <= gp.quicksum(self.nodes[w] for w in G.neighbors(v)) for v in G.nodes)
        
73
74
75
76
77
78
79
80
81
82
83
84
85

        
    def min_ij_separator(G, i, j, C_i):
        N_ci = {v for c in C_i for v in G.neighbors(c)}
        G_prime = nx.Graph(G)
        C_i_prime = C_i.copy()
        C_i_prime.update(N_ci)
        G_prime.remove_edges_from(G.subgraph(C_i_prime).edges)
        # dijkstra
        R_j = nx.algorithms.dag.descendants(G_prime, j)
        return R_j.intersection(N_ci)
    
    def solve(self):
86
87
88
89
        self.m._vars = self.nodes
        self.m._G = self.G
        self.m.Params.lazyConstraints = 1
        self.m.optimize(RootedConnectecKHopDominatingSet.elim_unconnectivity)    
90
        # self.m.optimize()
91
        
92
93
        ds = {i for i,x_i in enumerate(self.m.getVars()) if x_i.x > 0.5}
        return ds
94
    
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
    def elim_unconnectivity(model, where):
        if where == GRB.Callback.MIPSOL:
            vals = model.cbGetSolution(model._vars)
            ds = {i for i in model._vars.keys() if vals[i] > 0.5}
            
            G_prime_prime = model._G.subgraph(ds)
            if(not nx.is_connected(G_prime_prime)):
                C = [c for c in nx.algorithms.components.connected_components(G_prime_prime)]
                for i in range(len(C)-1):
                    C_i = C[i]
                    for j in range(i+1, len(C)):
                        C_j = C[j]
                        h = next(iter(C_i))
                        l = next(iter(C_j))
                        min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(model._G, h, l, C_i)
                        model.cbLazy(gp.quicksum(model._vars[s] for s in min_ij_sep) >= model._vars[h] + model._vars[l] - 1)

112
113
114
115
        
class RootedConnectecKHopDominatingSet(ConnectedKHopDominatingSet):
    
    def __init__(self, G, k, root = 0, name = "RCkDS"):
116
        super().__init__(G, k, name, exclude = {root})
117
118
119
120
        self.root = root
        
        self.m.addConstr(self.nodes[root] >= 1)
        
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
        # for i in G.nodes:
        #     if(i not in G.neighbors(root) and i is not root):
        #         min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(G, i, root, {i})
        #         self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[i])
                
        # for i in G.nodes:
        #     for j in G.nodes:
        #         if i != j and j not in G.neighbors(i):
        #             min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(self.G, i, j, {i})
        #             self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[i] + self.nodes[j] - 1)
        
        
        # All Neighbor separators
        # for v in G.nodes:
        #     if v is not root and root not in G.neighbors(v) and v not in G.neighbors(root) and not set(G.neighbors(root)).intersection(set(G.neighbors(v))):
        #         for i in range(2,G.degree[v]):
        #             V = {w for w in G.neighbors(v)}
        #             V.update([v])
        #             # for i_neighborhood in combinations(V, 2):
        #             for i_neighborhood in combinations(V, i):
        #                 if v in i_neighborhood:
        #                     min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(G, v, root, set(i_neighborhood))
        #                     self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[v])
        
        # All separators from single root
        # for v in G.nodes:
        #     # if v is not root and root not in G.neighbors(v) and v not in G.neighbors(root) and not set(G.neighbors(root)).intersection(set(G.neighbors(v))):
        #     for i in range(2,len(G.nodes)):
        #         V = {w for w in G.neighbors(v)}
        #         V.update([v])
        #         # for i_neighborhood in combinations(V, 2):
        #         for i_neighborhood in combinations(V, i):
        #             if v in i_neighborhood:
        #                 min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(G, v, root, set(i_neighborhood))
        #                 if min_ij_sep:
        #                     self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[v])
                    
        # for v in G.nodes:
        #     # if v is not root and root not in G.neighbors(v) and v not in G.neighbors(root) and not set(G.neighbors(root)).intersection(set(G.neighbors(v))):
        #     for i in range(2,len(G.nodes)):
        #         V = {w for w in G.neighbors(v)}
        #         V.update([v])
        #         # for i_neighborhood in combinations(V, 2):
        #         for i_neighborhood in combinations(V, i):
        #             if v in i_neighborhood:
        #                 for h in G.nodes:
        #                     min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(G, v, h, set(i_neighborhood))
        #                     if min_ij_sep:
        #                         self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[v])
                    
        
    def add_single_root_separators(self):
        for i in self.G.nodes:
            min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(G, i, self.root, {i})
            if min_ij_sep:
                self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[i])
        
    # ToDo: refactor!
    def add_all_neighborhood_root_separators(self):
        for v in self.G.nodes:
            if v is not self.root and self.root not in self.G.neighbors(v) and v not in self.G.neighbors(self.root) and not set(self.G.neighbors(self.root)).intersection(set(self.G.neighbors(v))):
                for i in range(2,self.G.degree[v]):
                    V = {w for w in self.G.neighbors(v)}
                    V.update([v])
                    for i_neighborhood in combinations(V, i):
                        if v in i_neighborhood:
                            min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(self.G, v, self.root, set(i_neighborhood))
                            self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[v])
    
    def add_all_combinations_root_separators(self):
        for v in self.G.nodes:
            for i in range(2,len(self.G.nodes)):
                V = {w for w in self.G.neighbors(v)}
                V.update([v])
                for i_neighborhood in combinations(V, i):
                    if v in i_neighborhood:
                        min_ij_sep = ConnectedKHopDominatingSet.min_ij_separator(self.G, v, self.root, set(i_neighborhood))
                        if min_ij_sep:
                            self.m.addConstr(gp.quicksum(self.nodes[s] for s in min_ij_sep) >= self.nodes[v])
200
        
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
    def add_simple_path_length_constraint(self):
        self.m.addConstrs((self.nodes[v] * len(nx.algorithms.shortest_path(self.G, self.root, v))) <= gp.quicksum(self.nodes) for v in self.G.nodes)
        # self.m.addConstrs((self.nodes[v] * self.nodes[w] * len(nx.algorithms.shortest_path(self.G, v, w))) <= gp.quicksum(self.nodes) for v in self.G.nodes for w in self.G.nodes)

        
    def add_gausian_sum_formula_constraint(self):
        self.m.addConstr(gp.quicksum(self.nodes[v] * len(nx.algorithms.shortest_path(self.G, self.root, v)) for v in self.G.nodes) <= (gp.quicksum(self.nodes)+1)*gp.quicksum(self.nodes)/2)
        # self.m.addConstr(gp.quicksum(self.nodes[v] * self.nodes[w] * len(nx.algorithms.shortest_path(self.G, v, w)) for v in self.G.nodes for w in self.G.nodes) <= (gp.quicksum(self.nodes)+1)*gp.quicksum(self.nodes)/2)

    def add_neighbor_of_neighbors_constraint(self, exclude):
        self.m.addConstrs(self.nodes[v] <= gp.quicksum(self.nodes[w] * gp.quicksum(self.nodes[h] for h in self.G.neighbors(w) if h is not v) for w in self.G.neighbors(v)) for v in self.G.nodes if v not in exclude)

    def intermediate_node_constraint(self, exclude):
        self.m.addConstrs(2 * self.nodes[v] <= gp.quicksum(self.nodes[w] for w in G.neighbors(v)) for v in G.nodes if v not in exclude)


217
218
if __name__ == '__main__':
    G = lp_to_nx_graph.read(sys.argv[1])
219
    
220
221
222
223
    if(len(sys.argv) > 2):
        k = int(sys.argv[2])
    else:
        k = 1
224
        
225
226
227
    
    # G = lp_to_nx_graph.read("/home/mario/Dokumente/Uni/Bachelorarbeit/git_repo/bachelor-mario-surlemont/python/lp graphs/asymmetric.lp")
    # k = 2
228
229
    dsProb = RootedConnectecKHopDominatingSet(G, k, 0)
    dsProb.solve_and_draw()