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
  202.                 visited.add(v_to)
  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
  268.         viewed.add(min_vertex)
  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. OK, I Understand
Top