-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSweepLine.py
99 lines (82 loc) · 3.9 KB
/
SweepLine.py
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
class SweepLineNetworkMonitor:
def __init__(self, G):
self.G = G
self.selected_monitors = set()
self.covered_nodes = set()
def solve(self):
coverage_map = self._generate_coverage_map()
if not coverage_map:
return self.selected_monitors
events = self._create_events(coverage_map)
remaining_nodes = set(self.G.nodes())
while remaining_nodes:
newly_covered = self._sweep_once(events, coverage_map, remaining_nodes)
if not newly_covered: # if no new nodes are covered handle the remaining nodes
for node in remaining_nodes:
self.selected_monitors.add(node)
self.covered_nodes.add(node)
break
remaining_nodes -= newly_covered
return self.selected_monitors
def _generate_coverage_map(self):
coverage_map = {}
for node in self.G.nodes():
coverage = self.get_neighbors_within_hops(node)
if coverage:
coverage_map[node] = coverage
return coverage_map
def _create_events(self, coverage_map):
events = []
for node, coverage in coverage_map.items():
nodes_list = sorted(list(coverage))
events.append((min(nodes_list), 0, node, coverage))
events.append((max(nodes_list), 1, node, coverage))
events.sort()
return events
def _sweep_once(self, events, coverage_map, remaining_nodes):
"""run the sweep line algorithm once and return newly covered nodes"""
active_intervals = {} # active intervals for each node
newly_covered = set()
for pos, event_type, node, coverage in events:
if not remaining_nodes: # all nodes are covered
break
if event_type == 0: # begin event
uncovered = coverage & remaining_nodes
if uncovered:
active_intervals[node] = uncovered
# choose the node with the maximum coverage
best_node = max(active_intervals,
key=lambda x: len(active_intervals[x]))
max_coverage = len(active_intervals[best_node])
# only when coverage is significantly larger than other nodes
if (best_node == node and
all(len(active_intervals[x]) < max_coverage
for x in active_intervals if x != node)):
self.selected_monitors.add(node)
newly_covered.update(uncovered)
remaining_nodes -= uncovered
# update active intervals
for interval_node in list(active_intervals.keys()):
active_intervals[interval_node] -= newly_covered
if not active_intervals[interval_node]:
del active_intervals[interval_node]
else: # end event
if node in active_intervals:
del active_intervals[node]
return newly_covered
def get_neighbors_within_hops(self, node, max_hops=2):
neighbors = set()
current_level = {node}
visited = {node}
for _ in range(max_hops):
next_level = set()
for n in current_level:
new_neighbors = set(self.G.neighbors(n)) - visited
next_level.update(new_neighbors)
visited.update(new_neighbors)
neighbors.update(next_level)
current_level = next_level
if not current_level:
break
neighbors.add(node)
return neighbors