• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 27th, 2020 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from enum import IntEnum, auto
2. from typing import Dict, List, Union, Any, Tuple
3.
4. import numpy as np
5. from PyQt5.QtGui import QColor
6.
7. from graph.graph import Graph
8. from graph.vertex import Vertex
9.
10. viewed_color = QColor(56, 230, 255)
11.
12.
13. class Flags(IntEnum):
14.     FOUND = auto()
15.     NOT_FOUND = auto()
16.
17.
18. def clear_color(graph: Graph):
19.     for v in graph.vertexes_coordinates.values():
20.         v.color = None
21.
22.
23. def __get_path(parents: dict, v_to: str) -> List[str]:
24.     path = []
25.     vertex = v_to
26.     while vertex is not None:
27.         if vertex not in path:
28.             path.append(vertex)
29.         vertex = parents[vertex]
30.     return path
31.
32.
33. def __get_edges(path: list, edges: Dict[str, Vertex], oriented: bool) -> Dict:
34.     res = {}
35.     path = list(reversed(path))
36.     for i in range(len(path) - 1):
37.         key = f'{path[i]}_{path[i + 1]}'
38.         res[key] = edges[key]
39.         if not oriented:
40.             old_key = key
41.             key = f'{path[i + 1]}_{path[i]}'
42.             res[key] = edges[old_key]
43.     return res
44.
45.
46. def after_work(graph: Graph, end: str, edges: Dict, parents: Dict, distance: np.array):
47.     if distance[int(end) - 1] < np.inf:
48.         p = __get_path(parents, end)
49.         graph.path = p
50.         graph.edge_path = __get_edges(p, edges, graph.oriented)
51.         for v in graph.path:
52.             graph.vertexes_coordinates[v].color = QColor(68, 133, 255)
53.     else:
54.         graph.path = []
55.         graph.edge_path = {}
56.     return distance[int(end) - 1]
57.
58.
59. def BFS(graph: Graph, begin: str, end: str) -> Union[None, int]:
60.     """
61.    Поиск пути
62.    (a) Breadth-First Search для пары указанных вершин;
63.    """
64.     size = graph.size()
65.     if size <= 0 or begin not in graph.vertexes or end not in graph.vertexes:
66.         return None
67.
68.     clear_color(graph)
69.     queue = [begin]
70.     viewed = np.zeros(size, dtype=int)
71.     distance = np.repeat(np.inf, size)
72.     distance[int(begin) - 1] = 0
73.     parents = {begin: None}
74.     edges = {}
75.
76.     while queue:
77.         current_vertex = queue.pop(0)
78.         if current_vertex == end:
79.             break
80.         graph.vertexes_coordinates[current_vertex].color = viewed_color
81.         current_vertex = int(current_vertex) - 1
82.         if viewed[current_vertex]:
83.             continue
84.         viewed[current_vertex] = True
85.
86.         for v_to, to_list in graph.vertexes[str(current_vertex + 1)].items():
87.             v_to = int(v_to) - 1
88.             edge = to_list[0][0]
89.             if not viewed[v_to] and v_to not in queue:
90.                 queue.append(str(v_to + 1))
91.
92.             if distance[current_vertex] + edge < distance[v_to]:
93.                 distance[v_to] = distance[current_vertex] + edge
94.                 parents[str(v_to + 1)] = str(current_vertex + 1)
95.                 edges[f'{current_vertex + 1}_{v_to + 1}'] = to_list[0][1]
96.
97.     return after_work(graph, end, edges, parents, distance)
98.
99.
100. def __euclid_distance(x1: float, y1: float, x2: float, y2: float) -> float:
101.     return np.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
102.
103.
104. def __cost(graph: Graph, v1: str, v2: str) -> float:
105.     v1 = graph.vertexes_coordinates[v1]
106.     v2 = graph.vertexes_coordinates[v2]
107.     return __euclid_distance(v1.x, v1.y, v2.x, v2.y)
108.
109.
110. def A_star(graph: Graph, begin: str, end: str) -> Union[None, int]:
111.     def get_min(d: dict):
112.         key = min(d.items(), key=lambda el: el[1] + __cost(graph, el[0], end))[0]
113.         d.pop(key)
114.         return key
115.
116.     size = graph.size()
117.     if size <= 0 or begin not in graph.vertexes or end not in graph.vertexes:
118.         return None
119.
120.     clear_color(graph)
121.     opened, closed, parents, edges, queue = {}, {}, {}, {}, {}
122.     opened[begin] = True
123.     distance = np.repeat([np.inf], size)
124.     distance[int(begin) - 1] = 0
125.     parents[begin] = None
126.     queue[begin] = 0
127.
128.     while queue:
129.         current_vertex = get_min(queue)
130.         graph.vertexes_coordinates[current_vertex].color = viewed_color
131.
132.         if current_vertex == end:
133.             p = __get_path(parents, end)
134.             graph.path = p
135.             graph.edge_path = __get_edges(p, edges, graph.oriented)
136.             return after_work(graph, end, edges, parents, distance)
137.
138.         for v_to in graph.vertexes[current_vertex]:
139.             new_cost = distance[int(current_vertex) - 1] + graph.vertexes[current_vertex][v_to][0][0]
140.             if v_to in closed and new_cost >= distance[int(v_to) - 1]:
141.                 continue
142.             if v_to not in queue or new_cost < distance[int(v_to) - 1]:
143.                 parents[v_to] = current_vertex
144.                 distance[int(v_to) - 1] = distance[int(current_vertex) - 1] + graph.vertexes[current_vertex][v_to][0][0]
145.                 edges[f'{current_vertex}_{v_to}'] = graph.vertexes[current_vertex][v_to][0][1]
146.                 if v_to not in queue:
147.                     queue[v_to] = distance[int(v_to) - 1]
148.
149.         closed[current_vertex] = True
150.
151.     return after_work(graph, end, edges, parents, distance)
152.
153.
154. def __find_edge(graph: Graph, path: List):
155.     edges = {}
156.     for i in range(len(path) - 1):
157.         key = f'{path[i]}_{path[i + 1]}'
158.         node = graph.vertexes[path[i]][path[i + 1]][0][1]
159.         edges[key] = node
160.         if not graph.oriented:
161.             key = f'{path[i + 1]}_{path[i]}'
162.             node = graph.vertexes[path[i + 1]][path[i]][0][1]
163.             edges[key] = node
164.     return edges
165.
166.
167. def __get_distance(graph: Graph, path: List):
168.     d = 0
169.     for i in range(1, len(path)):
170.         d += graph.vertexes[path[i - 1]][path[i]][0][0]
171.     return d
172.
173.
174. def IDA_star(graph: Graph, begin: str, end: str) -> Union[None, int]:
175.     def successors(g, d: Dict[str, List[Tuple[int, Any]]], b: int) -> List[Tuple[str, int]]:
176.         names = list(d.keys())
177.         return sorted(list([
178.             (name, g + int(__cost(graph, name, end))) for name in names  # if g + int(__cost(graph, name, end)) < b
179.         ]), key=lambda el: el[1])
180.
181.     def IDA_search(p: List, g: int, b: int, finish: str) -> int:
182.         node = p[-1]
183.         graph.vertexes_coordinates[node].color = viewed_color
184.
185.         f = g + int(__cost(graph, node, finish))
186.         if f > 1.25 * bound:
187.             return f
188.
189.         if node == finish:
190.             return Flags.FOUND
191.         less = np.inf
192.         found = False
193.
194.         for v_to, _ in successors(g, graph.vertexes[node], b):
195.             if v_to not in p and v_to not in visited:
196.                 p.append(v_to)
197.                 t = IDA_search(p, g + graph.vertexes[node][v_to][0][0], b, finish)
198.                 if t == Flags.FOUND:
199.                     return Flags.FOUND
200.                 if t < less:
201.                     less = t
203.                 p.pop()
204.         return Flags.FOUND if found else less
205.
206.     size = graph.size()
207.     if size <= 0 or begin not in graph.vertexes or end not in graph.vertexes:
208.         return None
209.
210.     clear_color(graph)
211.     bound = int(__cost(graph, begin, end))
212.     path = [begin]
213.     visited = {begin}
214.
215.     status = None
216.     while status is None:
217.         try:
218.             t = IDA_search(path, 0, bound, end)
219.         except Exception as e:
220.             print(e)
221.         if t == Flags.FOUND:
222.             status = Flags.FOUND
223.         if t == np.inf:
224.             status = Flags.NOT_FOUND
225.         bound = t
226.
227.     if status == Flags.NOT_FOUND:
228.         return None
229.     else:
230.         graph.path = path
231.         for v in graph.path:
232.             graph.vertexes_coordinates[v].color = QColor(68, 133, 255)
233.         graph.edge_path = __find_edge(graph, path)
234.         return __get_distance(graph, path)
235.
236.
237. def dijkstra(graph: Graph, begin: str, end: str):
238.     clear_color(graph)
239.
240.     weights: Dict[str, int] = {name: np.inf for name in graph.vertexes}
241.     weights[begin] = 0
242.     parents = {begin: None}
243.     viewed = {begin}
244.
245.     for v_to, to_list in graph.vertexes[begin].items():
246.         weight = to_list[0][0]
247.         weights[v_to] = weights[begin] + weight
248.         parents[v_to] = begin
249.
250.     for i in range(graph.size()):
251.         min_weight = np.inf
252.         min_vertex = None
253.
254.         for name, weight in weights.items():
255.             if weight < min_weight:
256.                 if name in viewed:
257.                     continue
258.                 min_weight = weight
259.                 min_vertex = name
260.
261.         for v_to, to_list in graph.vertexes[min_vertex].items():
262.             weight = to_list[0][0]
263.             if weights[v_to] > weights[min_vertex] + weight:
264.                 weights[v_to] = weights[min_vertex] + weight
265.                 parents[v_to] = min_vertex
266.
267.         graph.vertexes_coordinates[min_vertex].color = viewed_color
269.         if min_vertex == end:
270.             break
271.
272.     p = end
273.     graph.path = []
274.     while p is not None:
275.         graph.path.append(p)
276.         p = parents[p]
277.
278.     graph.path.reverse()
279.     for v in graph.path:
280.         graph.vertexes_coordinates[v].color = QColor(68, 133, 255)
281.
282.     return weights
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top