| 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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224 |
1×
29×
1×
1×
1×
1×
92×
1×
92×
1×
5×
1×
1×
1×
1×
1×
25×
25×
76×
92×
92×
25×
1×
27×
27×
97×
97×
86×
91×
91×
91×
70×
70×
27×
1×
26×
26×
26×
29×
26×
26×
1×
1×
1×
1×
1×
1×
1×
2×
2×
2×
1×
1×
1×
1×
1×
1×
1×
1×
2×
2×
3×
1×
1×
1×
1×
1×
1×
1×
1×
1×
1×
1×
1×
1×
1×
1×
2×
1×
1×
1×
1×
1×
1×
1×
1×
2×
2×
1×
1×
2×
1×
1×
1×
1×
1×
1×
| 'use strict'
var _Heap = require('heap')
var Heap = function (cmp) { return new _Heap(cmp) }
var LOG = false
module.exports = function (opts) {
var exports = {}
function getValueFromEdge(hops, j, v) {
return opts.add(hops[j], v)
}
function getNewValue(hops, j, k, v) {
return opts.min(hops[k], getValueFromEdge(hops, j, v))
}
function isUnchangedByEdge (hops, j, k, v) {
return hops[k] === opts.add(hops[j], v)
}
function isUnchanged (hops, j, k, v) {
return hops[k] === getNewValue(hops, j, k, v)
}
//"increment" is an edge that shortens graph distances
//adding a new edge always decreases hops, or decreasing
//the weight of an edge. (see the literature on dynamic graphs)
function isIncrement (value, old_value) {
return (
opts.isAdd(value) && (
opts.isRemove(old_value) || (opts.min(value, old_value) == value)
)
)
}
//take a graph, and return it's inverse
exports.reverse = function (g) {
var _g = {}
for(var k in g) {
for(var j in g[k]) {
_g[j] = _g[j] || {}
_g[j][k] = g[k][j]
}
}
return _g
}
function _loop (g, max, hops, next, _hops) {
Iif(!_hops) throw new Error('_hops must be provided')
while(!next.empty()) {
var j = next.pop()
if(opts.expand(hops[j], max))
for(var k in g[j]) {
var _h = getNewValue(hops, j, k, g[j][k])
Iif(isNaN(_h)) throw new Error('NaN')
if(_h != hops[k]) {
_hops[k] = hops[k] = _h
next.push(k)
}
}
}
return _hops
}
exports.traverse = exports.brute = function (g, _g, max, from) {
var hops = {}
hops[from] = opts.initial()
var next = Heap(function (a, b) {
return hops[a] - hops[b]
}, function (k) { return hops[k] })
next.push(from)
return _loop(g, max, hops, next, hops)
}
//find all nodes reachable via `from` with hops at > was
exports.uncertain = function (g, hops, max, start) {
var was = hops[start]
var maybe = {}
maybe[start] = true
var next = Heap(function (a, b) {
return hops[a] - hops[b]
})
next.push(start)
while(!next.empty()) {
var j = next.pop()
for(var k in g[j])
if(
isUnchangedByEdge(hops, j,k,g[j][k])
//hops[k] === opts.add(hops[j], g[j][k])
) {
Eif(!maybe[k]) {
maybe[k] = true
next.push(k)
}
}
}
return maybe
}
exports.sources = function (_g, hops, maybe) {
Iif(!_g) throw new Error('backlink graph must be provided')
var update = {}
for(var k in maybe)
Eif(hops[k])
for(var j in _g[k])
if(!maybe[j] && hops[j] != null)
update[j] = true
return update
}
function update_graphs(g, _g, from, to, value) {
g[from] = g[from] || {}
_g[to] = _g[to] || {}
g[from][to] = _g[to][from] = value
}
exports.update = function (g, _g, hops, max, start, from,to,value) {
var _hops = {}
Iif(hops[start] == null) hops[start] = opts.initial()
var old_value = g[from] && g[from][to]
//handle follow (aka increments)
//TODO: if number is greater, treat that is decrement
Iif(isIncrement(value, old_value)) {
update_graphs(g, _g, from, to, value)
//if from isn't within hops, then to won't be in hops either.
if(hops[from] == null || from == to) return {}
var h = getNewValue(hops, from, to, value)
//if destination is max or more, do not add edge
if(!opts.expand(hops[from], max)) return {}
if(h != hops[to]) {
_hops[to] = hops[to] = h
//if this edge is at the limit, we are done.
if(!opts.expand(hops[to], max)) return _hops
//setup heap and run dijkstra's algorithm
var next = Heap(function (a, b) { return hops[a] - hops[b] })
next.push(to)
return _loop(g, max, hops, next, _hops)
}
}
//handle unfollow and block (aka decrements)
else {
Iif(!value && !_g) throw new Error('expected increment:'+value)
var j = from, k = to, v = value, _v = g[from] && g[from][to]
//shortcut 1: detect cases that won't change the hops
Iif(
to === start || //can't block yourself, so don't update hops.
( //already closer
//if previous value was null, or previous didn't set the hops value anyway.
//and the hops value will be the same, then don't update hops.
(_v == null || !isUnchangedByEdge(hops, j, k, _v)) &&
isUnchanged(hops, j, k, v)
) || (
//if this edge _did_ set the hops value, check if there is another edge which also sets it.
//this catches the case when someone unfollows, but there is another follow path the same length.
//only applies when there was a previous edge.
(_v == null || isUnchangedByEdge(hops, j, k, _v)) &&
isUnchanged(hops, j, k, v) &&
//quickly check if any other edges set hops
(function () {
for(var _j in _g[k])
Iif(_j !== j && isUnchangedByEdge(hops, _j, k, g[_j][k]))
return true
}())
)
) {
//won't change hops, so update graph and return
update_graphs(g, _g, from, to, value)
return null
}
//shortcut 2. detect cases that will add exactly 1 element to hops
else Iif (v === null && hops[j] >= 0) {
//only adds the new item, but won't expand since this is a block.
update_graphs(g, _g, j,k,v)
if(opts.expand(hops[j], 3)) //XXX is this really where the default is set?
_hops[k] = hops[k] = opts.add(hops[j], v)
return _hops
}
//the long way. calculate all hops that may be changed by this edge and recalculate them.
else {
var next = Heap(function (a, b) {
return hops[a] - hops[b]
}, function (k) { return hops[k] })
var maybe = exports.uncertain(g, hops, max, to)
var sources = exports.sources(_g, hops, maybe)
update_graphs(g, _g, from, to, value)
sources[from] = true
var pre = {}
for(var _k in maybe) {
pre[_k] = hops[_k]
delete hops[_k]
}
var diff = exports.updateAll(g, hops, max, sources, _hops)
for(var k in pre)
Iif(diff[k] == pre[k])
delete diff[k]
return diff
}
}
}
exports.updateAll = function (g, hops, max, sources, _hops) {
var next = Heap(function (a, b) { return hops[a] - hops[b] })
for(var k in sources) next.push(k)
return _loop(g, max, hops, next, _hops)
}
return exports
}
|