-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDynGraph.py
179 lines (150 loc) · 6.69 KB
/
DynGraph.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
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
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
import heapq
from typing import Union
import numpy as np
from sssp import apsp
from SingleSinkDynGraph import FixSizeGraph, _new_2d_array
from internals import FTYPE, ITYPE
"""
We assume that the graphs have a fixed number of vertexes.
This allows to use an efficient 2d-array representation of the graph.
"""
class DynDijkstra(FixSizeGraph):
def insert_edge(self, a, b, length: FTYPE):
self.lengths[a, b] = length
def delete_edge(self, a, b):
self.lengths[a, b] = np.inf
def get_distances(self):
dists, _ = apsp(self.lengths)
spg = _getSpgtoSink(self.lengths, dists)
return dists, spg
class DynRR(FixSizeGraph):
"""
This maintains a graph of fixed number of vertexes (N_vertex)
and keeps an array with the single-sink-shortest-path distances and the predecessors.
Uses Ramalingam-Reps: https://www.sciencedirect.com/science/article/abs/pii/S0196677496900462
TODO: Check if it is better to keep the shortest past spg instead of recalculating it each time.
"""
def __init__(self, **kwargs):
super().__init__(**kwargs)
if "graph" in kwargs:
self.distances, _ = apsp(self.lengths)
else:
self.distances = _new_2d_array(self.N_vertex)
def delete_edge(self, v, w):
self.lengths[v, w] = np.inf
affectedSinks = _deleteUpdate(self.lengths.T, self.distances.T, w, v, v, onlyPhase1=True)
affectedSources = _deleteUpdate(self.lengths, self.distances, v, w, w, onlyPhase1=True)
for sink in affectedSinks.nonzero()[0]:
_deleteUpdate(self.lengths, self.distances, v, w, sink)
for source in affectedSources.nonzero()[0]:
_deleteUpdate(self.lengths.T, self.distances.T, w, v, source)
def insert_edge(self, v, w, c):
old_edge = self.lengths[v, w]
if c < old_edge:
self._insert_edge(v, w, c)
elif c > old_edge:
self.delete_edge(v, w)
self._insert_edge(v, w, c)
def _insert_edge(self, v, w, c):
self.lengths[v, w] = c
affectedSinks = _insertUpdate(self.lengths.T, self.distances.T.copy(), w, v, v)
affectedSources = _insertUpdate(self.lengths, self.distances, v, w, w)
for sink in affectedSinks.nonzero()[0]:
_insertUpdate(self.lengths, self.distances, v, w, sink)
for source in affectedSources.nonzero()[0]:
_insertUpdate(self.lengths.T, self.distances.T, w, v, source)
def get_distances(self):
spg = _getSpgtoSink(self.lengths, self.distances)
return self.distances, spg
def _deleteUpdate(lengths, distances, v, w, sink: int, onlyPhase1=False) -> Union[np.ndarray, None]:
N_vertex = lengths.shape[0]
affectedVertices = np.zeros(N_vertex, dtype=np.bool_)
sp_v = SP_all_heads(lengths, distances, v, sink)
if not sp_v.any():
workSet = {v}
# Phase 1: Identify vertices in AFFECTED (the vertices whose shortest distance to sink has increased).
while workSet:
u = workSet.pop()
affectedVertices[u] = True
xs = SP_all_tails(lengths, distances, u, sink)
tmp = []
for ix, x in enumerate(xs):
if x:
sp_y = SP_all_heads(lengths, distances, ix, sink)
if affectedVertices[sp_y].all():
tmp.append(ix)
workSet = workSet.union(tmp)
if onlyPhase1:
return affectedVertices
# Phase 2: Determine new distances to sink for all vertices in AffectedVertices.
priorityQueue = []
na = ~ affectedVertices
tmp = lengths[affectedVertices][:, na] + distances[na, sink]
dist_to_sink = np.min(tmp, axis=1, initial=np.inf)
distances[affectedVertices, sink] = dist_to_sink
for a in np.nonzero(affectedVertices)[0]:
heapq.heappush(priorityQueue, (distances[a, sink], a))
while priorityQueue:
dist_a_sink, a = heapq.heappop(priorityQueue)
c = (lengths[:, a] < np.inf) & (lengths[:, a] + distances[a, sink] < distances[:, sink])
for ix, x in enumerate(c):
if x:
distances[ix, sink] = lengths[ix, a] + dist_a_sink
heapq.heappush(priorityQueue, (distances[ix, sink], ix))
if onlyPhase1:
return affectedVertices
def _insertUpdate(lengths, distances, v, w, sink):
N_vertex = lengths.shape[0]
workSet = {(v, w)}
visitedVertices = np.zeros(N_vertex, dtype=np.bool_)
visitedVertices[v] = 1
affectedVertices = np.zeros(N_vertex, dtype=np.bool_)
while workSet:
x, u = workSet.pop()
temp_dist = lengths[x, u] + distances[u, sink]
if temp_dist < distances[x, sink]:
affectedVertices[x] = True
distances[x, sink] = temp_dist
sp = SP_all_tails(lengths, distances, x, v) & ~ visitedVertices
for iy, y in enumerate(sp):
if y:
workSet.add((iy, x))
visitedVertices[iy] = 1
return affectedVertices
def SP_all_tails(lengths: np.ndarray, distances: np.ndarray, head: int, sink: int) -> np.ndarray:
kk = (lengths[:, head] < np.inf) &\
(distances[:, sink] == lengths[:, head] + distances[head, sink]) &\
(distances[:, sink] < np.inf)
kk[head] = False
return kk
def SP_all_heads(lengths, distances, tail: int, sink: int) -> np.ndarray:
kk = (lengths[tail, :] < np.inf) &\
(distances[tail, sink] == lengths[tail, :] + distances[:, sink]) &\
(distances[tail, sink] < np.inf)
kk[tail] = False
return kk
def _getSpgtoSink(lengths: np.ndarray, distances: np.ndarray, sink=None):
"""
Reconstruct the shortest path matrix spg for a graph (lengths)
given the shortest path distances
:param lengths: np.ndarray(N_vertex, N_vertex)
:param distances: np.ndarray(N_vertex, N_vertex) or np.ndarray(N_vertex)
:param sink:
If sink is an integer, distances[i] is the shortest path distances array from every vertex to sink
if sink is not given, distances[i,j] is the shortest path distances array from i to j
:return: spg: np.ndarray(N_vertex, N_vertex, N_sinks)
"""
N_vertex = lengths.shape[0]
if sink:
N_sinks = 1
else:
N_sinks = N_vertex
sink = slice(None)
# Convert (N,) array in (1,N) array
distances = np.expand_dims(distances, axis=1)
spg = np.zeros((N_vertex, N_vertex, N_sinks), dtype=np.bool_)
for a in np.arange(N_vertex, dtype=ITYPE):
for b in np.arange(N_vertex, dtype=ITYPE):
c = (distances[a, sink] == lengths[a, b] + distances[b, sink]) & (lengths[a, b] < np.inf)
spg[a, b, c[0]] = True
return spg