fork download
copy 
  1. from copy import deepcopy
  2. from datetime import datetime
  3.  
  4. class Node:
  5.     def __init__(self, coord = (), lenght = 0, turn = 0, asx = None):
  6.         self.coord = coord //координаты ячейки
  7.         self.lenght = lenght //длина пути
  8.         self.turn = turn //количество поворотов
  9.         self.asx = asx //идет ли движение по оси Х
  10.  
  11. class Graph:
  12.     def __init__(self, data = {}):
  13.         self.__hash = data
  14.         self.__node_hash = {}
  15.         self.__stackhash = {}
  16.         self.__new_edges = []
  17.         self.__added_vertex = []
  18.         self.__data2 = deepcopy(data)
  19.         for j in self.__data2.keys():
  20.             edges = self.__data2[j]
  21.             self.__added_vertex.append(j)
  22.             for edge in edges:
  23.                 if edge[0] not in self.__added_vertex:
  24.                     self.add_edge_weight(j, edge[0], edge[1])
  25.                     self.__new_edges.append(((j, edge[0]), edge[1]))
  26.  
  27.  
  28.     def width_search(self, i, j):
  29.         queue = []
  30.         if self.mtx_labels[i][j]:
  31.             return
  32.         mtx_value = self.matrix[i][j]
  33.         queue.append((i, j))
  34.         while len(queue) != 0:
  35.             queue_value = queue.pop(0)
  36.             i = queue_value[0]
  37.             j = queue_value[1]
  38.             mtx_value = self.matrix[i+1][j]
  39.             if mtx_value == 0:
  40.                 queue.append((i+1, j))
  41.                 self.matrix[i+1][j] = 1
  42.                 self.mtx_labels[i+1][j] = True
  43.  
  44.             mtx_value = self.matrix[i-1][j]
  45.             if mtx_value == 0:
  46.                 queue.append((i-1, j))
  47.                 self.matrix[i-1][j] = 1
  48.                 self.mtx_labels[i-1][j] = True
  49.  
  50.             mtx_value = self.matrix[i][j+1]
  51.             if mtx_value == 0:
  52.                 queue.append((i, j+1))
  53.                 self.matrix[i][j+1] = 1
  54.                 self.mtx_labels[i][j+1] = True
  55.  
  56.             mtx_value = self.matrix[i][j-1]
  57.             if mtx_value == 0:
  58.                 queue.append((i, j-1))
  59.                 self.matrix[i][j-1] = 1
  60.                 self.mtx_labels[i][j-1] = True
  61.  
  62.     def print_matrix(self):
  63.         for line in self.matrix:
  64.         	print(line)
  65.  
  66.     def add_vertex(self, index):
  67.     	self.__hash[index] = [] 
  68.  
  69.     def add_edge_weight(self, vertex1, vertex2, weight):
  70.         if vertex1 not in self.__hash.keys():
  71.             self.add_vertex(vertex1)
  72.  
  73.         if vertex2 not in self.__hash.keys():
  74.             self.add_vertex(vertex2)
  75.  
  76.         self.__hash[vertex1].append((vertex2, weight))
  77.         self.__hash[vertex2].append((vertex1, weight))
  78.  
  79.     def add_edge(self, vertex1, vertex2):
  80.         if vertex1 not in self.__hash.keys():
  81.             self.add_vertex(vertex1)
  82.  
  83.         if vertex2 not in self.__hash.keys():
  84.             self.add_vertex(vertex2)
  85.  
  86.         self.__hash[vertex1].append(vertex2)
  87.         self.__hash[vertex2].append(vertex1)
  88.  
  89.     def delete_edge(self, vertex1, vertex2):
  90.         self.__hash[vertex1].remove(vertex2)
  91.         self.__hash[vertex2].remove(vertex1)
  92.  
  93.     def delete_vertex(self, index):
  94.         edges = self.__hash[index]
  95.         for edge in edges:
  96.             self.delete_edge(edge, index)
  97.         del self.__hash[index]
  98.  
  99.     def print(self):
  100.     	for item in self.__hash:
  101.             print('{0} => {1}'.format(item, self.__hash[item]))
  102.  
  103.     def _deep_search(self, index, labels, graph):
  104.         edges = self.__hash[index]
  105.         for edge in edges:
  106.         	if not labels[edge-1]:
  107.                     labels[edge-1] = True
  108.                     graph.add_edge(edge, index)
  109.                     if not labels[index-1]:
  110.                         labels[index-1] = True
  111.                         graph = self._deep_search(edge, labels, graph)
  112.         return graph
  113.  
  114.     def get_min_frame(self):
  115.         frame = Graph()
  116.         components = {}
  117.         for vertex in self.__hash.keys():
  118.             frame.add_vertex(vertex)
  119.             components[vertex] = vertex
  120.         sortedEdges = sorted(self.__new_edges, key=lambda edge: edge[1])
  121.         edgesCount = len(components) - 1
  122.         count = 0
  123.         for edge in sortedEdges:
  124.             if(count == edgesCount):
  125.                 break
  126.             if(components[edge[0][0]] != components[edge[0][1]]):
  127.                     frame.add_edge(edge[0][0], edge[0][1])
  128.                     count = count + 1
  129.                     comp1 = components[edge[0][0]]
  130.                     comp2 = components[edge[0][1]]
  131.                     for comp in components.keys():
  132.                         if(components[comp] == comp2):
  133.                             components[comp] = comp1
  134.         return frame
  135.  
  136.  
  137. print('Start')
  138. print(datetime.now())
  139. my_data = {1:[(2, 10), (6, 12)], 2:[(1, 10), (3, 11), (6, 3)], 3:[(2, 11), (4, 4), (5, 5), (6, 1)], 4:[(3, 4), (5, 3)], 5:[(3, 5), (4, 3), (6, 8)], 6:[(1, 12), (2, 3), (3, 1), (5, 8)], 7:[(8, 1), (9, 5), (10, 6)], 8:[(7, 1), (9, 4), (10, 2)], 9:[(7, 5), (8, 4), (10, 3)], 10:[(7, 6), (8, 2), (9, 3)]}
  140. graph = Graph(my_data)
  141. frame = graph.get_min_frame()
  142. frame.print()
  143. print(datetime.now())
  144. print('Finish')
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class, interface, or enum expected
from copy import deepcopy
^
Main.java:1: error: '.' expected
from copy import deepcopy
                         ^
Main.java:2: error: ';' expected
from datetime import datetime
    ^
Main.java:2: error: '.' expected
from datetime import datetime
                             ^
Main.java:4: error: ';' expected
class Node:
     ^
Main.java:4: error: class, interface, or enum expected
class Node:
          ^
Main.java:5: error: class, interface, or enum expected
    def __init__(self, coord = (), lenght = 0, turn = 0, asx = None):
    ^
Main.java:11: error: '{' expected
class Graph:
           ^
Main.java:12: error: class, interface, or enum expected
    def __init__(self, data = {}):
                                ^
Main.java:101: error: unclosed character literal
            print('{0} => {1}'.format(item, self.__hash[item]))
                  ^
Main.java:101: error: unclosed character literal
            print('{0} => {1}'.format(item, self.__hash[item]))
                             ^
Main.java:137: error: unclosed character literal
print('Start')
      ^
Main.java:137: error: unclosed character literal
print('Start')
            ^
Main.java:144: error: unclosed character literal
print('Finish')
      ^
Main.java:144: error: unclosed character literal
print('Finish')
             ^
15 errors
stdout
copy 
Standard output is empty
https://ideone.com/ADrNTx
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!