-
Notifications
You must be signed in to change notification settings - Fork 0
/
utils.ts
150 lines (126 loc) · 4.71 KB
/
utils.ts
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
import Graph from "./dataStructures/graph"
import Node from "./dataStructures/node"
import Arc from "./dataStructures/arc"
/**
* Retrieves the path from a node of the graph to the source node
* using the predecessors map. If there is a cycle return the cycle path.
* Time complexity: O(n).
* @param {Map<number, number>} The predecessor nodes.
* @param {number} The node to start from.
* @returns {number[]} The path from a node to the source node or a cycle path.
*/
export function retrievePath(predecessors: Map<number, number>, nodeId: number): number[] {
// Path starts from a node id.
const pathSet = new Set([nodeId])
let nextNodeId = predecessors.get(nodeId) as number
// The loop stops when the last path node is the source node.
while (nextNodeId !== -1 && !pathSet.has(nextNodeId)) {
pathSet.add(nextNodeId)
nextNodeId = predecessors.get(nextNodeId) as number
}
let path = Array.from(pathSet)
if (pathSet.has(nextNodeId)) {
// Removes all the nodes outside the cycle.
path = path.slice(path.indexOf(nextNodeId))
}
// Reverses the path.
return path.reverse()
}
/**
* Converts a graph in a residual graph, in which the new arc flow
* represent the residual capacity.
* Time complexity: O(m).
* @param {Graph} The original graph.
* @returns {Graph} The residual graph.
*/
export function getResidualGraph(graph: Graph): Graph {
const residualGraph = graph.copy()
for (const node of graph.getNodes()) {
for (const arc of node.getArcs()) {
if (arc.flow > 0) {
// Creates the reverse arc with the correct residual capacity.
const rAdjacentNode = residualGraph.getNode(arc.head)
rAdjacentNode.addArc(new Arc(node.id, -arc.cost, arc.capacity, arc.flow))
}
const rNode = residualGraph.getNode(node.id)
// Updates the residual capacity of the arc or removes it.
if (arc.capacity > arc.flow) {
const rArc = rNode.getArc(arc.head)
rArc.flow = arc.capacity - arc.flow
} else {
rNode.removeArc(arc.head)
}
}
}
return residualGraph
}
/**
* Returns the arc minimum residual capacity of the path.
* Time complexity: O(n).
* @param {Graph} Graph containing the path.
* @param {number[]} The path of the nodes.
* @returns {number} The minimum capacity.
*/
export function getResidualCapacity(graph: Graph, path: number[]): number {
let residualCapacity = Infinity
for (let i = 0; i < path.length - 1; i++) {
const node = graph.getNode(path[i])
const arc = node.getArc(path[i + 1])
if (arc.flow < residualCapacity) {
residualCapacity = arc.flow
}
}
return residualCapacity
}
/**
* Augments the path in the graph updating the flow of the arcs.
* Time complexity: O(n).
* @param {Graph} The graph containing the path.
* @param {number[]} The path of the nodes.
* @param {number} The flow to send in the path.
*/
export function sendFlow(graph: Graph, path: number[], flow: number) {
for (let i = 0; i < path.length - 1; i++) {
const node = graph.getNode(path[i])
const arc = node.getArc(path[i + 1])
const adjacentNode = graph.getNode(arc.head)
if (arc.flow === flow) {
node.removeArc(adjacentNode.id)
} else {
arc.flow -= flow
}
if (!adjacentNode.hasArc(node.id)) {
adjacentNode.addArc(new Arc(node.id, -arc.cost, arc.capacity, flow))
} else {
const reverseArc = adjacentNode.getArc(node.id)
reverseArc.flow += flow
}
}
}
/**
* Convert the residual graph in an optimal graph in which the
* residual capacity is converted in flow.
* Time complexity: O(m).
* @param {Graph} The graph to update.
* @returns {Graph} The optimal graph.
*/
export function getOptimalGraph(graph: Graph): Graph {
const optimalGraph = new Graph()
for (const node of graph.getNodes()) {
optimalGraph.addNode(new Node(node.id, node.balance))
}
for (const node of graph.getNodes()) {
for (const arc of node.getArcs()) {
const adjacentNode = graph.getNode(arc.head)
if (arc.cost < 0 || Object.is(arc.cost, -0)) {
const oAdjacentNode = optimalGraph.getNode(arc.head)
const reverseArc = new Arc(node.id, -arc.cost, arc.capacity, arc.flow)
oAdjacentNode.addArc(reverseArc)
} else if (!adjacentNode.hasArc(node.id)) {
const oNode = optimalGraph.getNode(node.id)
oNode.addArc(new Arc(arc.head, arc.cost, arc.capacity))
}
}
}
return optimalGraph
}