-
Notifications
You must be signed in to change notification settings - Fork 0
/
transportation.py
202 lines (187 loc) · 7.85 KB
/
transportation.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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
from typing import List, Self, Dict
from copy import deepcopy
from numpy import argmin, unravel_index, array, diff, inf, isinf, where
from math import isinf as misinf
from json import load
from os.path import exists
from sys import version_info
class Transportation:
def __diff_arr(self, arr: List) -> List:
if len(arr) > 1:
return diff(where(isinf(arr), 0.0, arr))
else:
return arr
def __init__(self) -> None:
self.matrix: List[List[int | float]] | None = None
self.is_balanced: bool = False
self.cost = 0
self.__verbose: bool = False
def input_file(self, json_path: str) -> Self:
if not exists(json_path):
print(f"Please make sure {json_path} exists")
with open(json_path, "r") as file:
data: Dict[str, List | Dict] = load(file)
keys = set(["suppliers", "buyers", "max_supplies", "max_demands", "costs"])
matrix = list()
if keys.issubset(data.keys()):
suppliers = data.get("suppliers", None)
buyers = data.get("buyers", None)
costs: Dict[str, List[float]] = data.get("costs", None)
max_supplies: List[float] = data.get("max_supplies", None)
max_demands: List[float] = data.get("max_demands", None)
self.is_balanced = sum(max_supplies) == sum(max_demands)
if not self.is_balanced and len(max_demands) != len(buyers):
print(
"Size of Supplies doesn't match the length of cost matrix"
if self.is_balanced
else "The demands and supplies aren't balanced"
)
return self
for sup, cost in costs.items():
idx = suppliers.index(sup)
cost.append(max_supplies[idx])
matrix.append(cost)
max_demands.append(inf)
matrix.append(max_demands)
self.matrix = deepcopy(matrix)
else:
print(f"All keys {keys} must be included")
return self
def input(
self,
cost_matrix: List[List[int | float]],
supplies: List[int | float],
demands: List[int | float],
) -> Self:
self.is_balanced = sum(supplies) == sum(demands)
if self.is_balanced and len(demands) == len(cost_matrix[0]) != 0:
for i, row in enumerate(cost_matrix):
row.append(supplies[i])
demands.append(inf)
cost_matrix.append(demands)
self.matrix = deepcopy(cost_matrix)
else:
print(
"Size of Supplies doesn't match the length of cost matrix"
if self.is_balanced
else "The demands and supplies aren't balanced"
)
return self
def __is_exhausted(self):
return all([row[-1] == 0 or misinf(row[-1]) for row in self.matrix]) and all(
[demand == 0 or misinf(demand) for demand in self.matrix[-1]]
)
def __north_west(self) -> None:
if self.__verbose:
print(array(self.matrix))
i, j = 0, 0
while (
not self.__is_exhausted()
and i < len(self.matrix) - 1
and j < len(self.matrix[0]) - 1
):
factor = min(self.matrix[i][-1], self.matrix[-1][j])
if self.__verbose:
print(f"({i}, {j}), Factor: {factor}, cost: {self.matrix[i][j]}")
self.cost = self.cost + self.matrix[i][j] * factor
self.matrix[i][-1] -= factor
self.matrix[-1][j] -= factor
if self.matrix[i][-1] == 0:
i += 1
if self.matrix[-1][j] == 0:
j += 1
def __least_cost(self):
if self.__verbose:
print(array(self.matrix))
arr = array(self.matrix)
arr = arr[0 : arr.shape[0] - 1, 0 : arr.shape[1] - 1]
while not self.__is_exhausted():
i, j = unravel_index(argmin(arr), arr.shape)
factor = min(self.matrix[i][-1], self.matrix[-1][j])
if self.__verbose:
print(f"({i}, {j}), Factor: {factor}, cost: {self.matrix[i][j]}")
self.cost = self.cost + self.matrix[i][j] * factor
self.matrix[i][-1] -= factor
self.matrix[-1][j] -= factor
arr[i][j] = inf
if self.matrix[i][-1] == 0:
arr[i, :] = inf
if self.matrix[-1][j] == 0:
arr[:, j] = inf
def __vojels_approx(self):
if self.__verbose:
print(array(self.matrix))
arr = array(self.matrix)
arr = arr[0 : arr.shape[0] - 1, 0 : arr.shape[1] - 1]
row_pens = array([0.0 for _ in range(arr.shape[0])])
col_pens = array([0.0 for _ in range(arr.shape[1])])
while not self.__is_exhausted():
for r in range(arr.shape[0]):
mins_row = sorted(set(arr[r, :]))[:2]
row_pens[r] = abs(self.__diff_arr(mins_row)[0])
for c in range(arr.shape[1]):
mins_col = sorted(set(arr[:, c]))[:2]
col_pens[c] = abs(self.__diff_arr(mins_col)[0])
i, j = 0, 0
rev_col = where(isinf(col_pens), -inf, col_pens)
rev_row = where(isinf(row_pens), -inf, row_pens)
if max(rev_row) < max(rev_col):
j = unravel_index(
where(isinf(col_pens), -inf, col_pens).argmax(), col_pens.shape
)
i = unravel_index(argmin(arr[:, j]), arr[:, j].shape)
i, j = i[0], j[0]
else:
i = unravel_index(
where(isinf(row_pens), -inf, row_pens).argmax(), row_pens.shape
)
j = unravel_index(argmin(arr[i, :][0]), arr[i, :][0].shape)
i, j = i[0], j[0]
factor = min(self.matrix[i][-1], self.matrix[-1][j])
if self.__verbose:
print(f"({i}, {j}), Factor: {factor}, cost: {self.matrix[i][j]}")
self.cost = self.cost + self.matrix[i][j] * factor
self.matrix[i][-1] -= factor
self.matrix[-1][j] -= factor
if self.matrix[i][-1] == 0:
arr[i, :] = inf
row_pens[i] = inf
if self.matrix[-1][j] == 0:
arr[:, j] = inf
col_pens[j] = inf
def solve(self, method: str = "NW", verbose: bool = False) -> Self:
__methods = {
"NW": self.__north_west,
"LC": self.__least_cost,
"VA": self.__vojels_approx,
}
self.__verbose = verbose
self.cost = 0
if self.matrix is not None:
print("Calling solve, method: ", method)
if version_info.major == 3 and version_info.minor >= 10:
match method:
case "NW":
self.__north_west()
case "LC":
self.__least_cost()
case "VA":
self.__vojels_approx()
case _:
print(f"No {method} method found")
else:
method_f = __methods.get(method, None)
if method_f is not None:
method_f()
else:
print(f"No {method} method found")
return self
if __name__ == "__main__":
solver = Transportation()
print(solver.input_file("./q.json").solve("NW").cost)
print(solver.input_file("./q.json").solve("LC").cost)
print(solver.input_file("./q.json").solve("VA").cost)
print("=============================================")
print(solver.input_file("./q2.json").solve("NW").cost)
print(solver.input_file("./q2.json").solve("LC").cost)
print(solver.input_file("./q2.json").solve("VA").cost)