-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithms.py
106 lines (84 loc) · 2.63 KB
/
algorithms.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
import numpy as np
from heapq import heappush, heappop
from itertools import chain
from collections import deque, defaultdict
from tqdm import tqdm
def GraphGenerator(V, E, DMAX=200, signed=False, weighted=True):
weights = np.random.choice(DMAX, E)
nodes = np.random.choice(V-1, 3*E)
nodes = [(u, v) for u, v in zip(nodes[::2], nodes[1::2]) if u != v]
if signed:
weights = map(lambda x: x - (DMAX >> 4), weights)
if weighted:
return [
(u, v, w)
for (u, v), w in tqdm(zip(nodes, weights))
]
else:
return [
(*nodes[i], 1)
for i in range(V)
]
def GraphConverter(T, V, E, returnType="dict", inType="tuple", weighted=True, INF=10000001):
if inType == "tuple":
if returnType == "dict":
G = defaultdict(list)
for src, dst, dist in T:
G[src].append((dist, dst))
return G
elif returnType == "matrix":
G = [[INF] * V for _ in range(V)]
for src, dst, dist in T:
G[src-1][dst-1] = min(dist, G[src-1][dst-1])
return G
elif inType == "matrix":
if returnType == "dict":
G = defaultdict(list)
for src in range(V):
for dst in range(V):
G[src].append((T[src][dst], dst))
return G
def Dijkstra(G, V, src, Gtype="dict", DMAX=10000001):
D = [DMAX] * (V + 1)
D[src] = 0
H = [(0, src)]
while H:
d, src = heappop(H)
for dist, dst in G[src]:
if 0 <= D[dst] <= d + dist:
continue
D[dst] = dist + d
heappush(H, (d + dist, dst))
return D
def BellmanFord(G, V, src, Gtype="dict", DMAX=10000001):
D = [DMAX] * (V + 1)
D[src] = 0
update = True
for i in range(V):
if not update:
break
update = False
for s, dist, d in chain((s, dist, d) for s in G for dist, d in G[s]):
if D[s] < DMAX and D[s] + dist < D[d]:
update = True
D[d] = D[s] + dist
return D
def BFS(G, V, src, Gtype="dict"):
D = [-1] * (V + 1)
D[src] = 0
Q = deque([(src, 0)])
while Q:
src, d = Q.popleft()
for _, dst in G[src]:
if D[dst] < 0:
D[dst] = d + 1
Q.append((dst, d+1))
return D
def Floyd(G, V, Gtype="matrix", display=False):
N = V
for n in range(N):
for i in range(N):
for j in range(N):
if i != n and j != n:
G[i][j] = min(G[i][j], G[i][n] + G[n][j])
return G