-
Notifications
You must be signed in to change notification settings - Fork 3
/
algo.js
53 lines (43 loc) · 1.3 KB
/
algo.js
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
import { binaryheap } from "./binaryheap";
function solvedata(data) {
//no of nodes
const sz = data["nodes"].length;
const netvaluearr = Array(sz).fill(0);
for (let i = 0; i < data["edge"].length; i++) {
const edge = data["edge"][i];
// + -> take money - -> give money
netvaluearr[edge["to"] - 1] += parseInt(edge["label"]);
netvaluearr[edge["from"] - 1] -= parseInt(edge["label"]);
}
let posheap = new binaryheap();
let negheap = new binaryheap();
for (let i = 0; i < sz; i++) {
if (netvaluearr[i] > 0) {
posheap.insertvalue([netvaluearr[i], i]);
} else if (netvaluearr[i] < 0) {
negheap.insertvalue([-netvaluearr[i], i]);
netvaluearr[i] *= -1;
}
}
const newedge = [];
while (!posheap.empty() && negheap.empty()) {
let max = posheap.extractmax();
let min = negheap.extractmax();
let to = max[1];
let from = min[1];
let amt = Math.min(max[0], min[0]);
newedge.push({ from: from + 1, to: (to = 1), label: String(amt) });
netvaluearr[to] -= amt;
netvaluearr[from] -= amt;
if (max[0] > min[0]) {
posheap.insertvalue([netvaluearr[to], to]);
} else if (max[0] < min[0]) {
negheap.insertvalue([netvaluearr[from], from]);
}
}
data = {
nodes: data["nodes"],
edges: newedge,
};
return data;
}