Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.73 KB | None | 0 0
  1. class NetXGraph:
  2.     def __init__(self, custom_points=[]):
  3.         self.graph = nx.Graph()
  4.         self.points = set(custom_points)
  5.         self.generate_nodes()
  6.         self.generate_relationships()
  7.  
  8.     def generate_nodes(self):
  9.         self.graph.add_nodes_from(self.points)
  10.  
  11.     def generate_relationships(self):
  12.         jump_list = []
  13.         for k in [-32, -16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16, 32]:
  14.             for p in [-32, -16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16, 32]:
  15.                 if k != 0 and p != 0:
  16.                     jump_list.append((p, k))
  17.         for point in self.points:
  18.             for k, p in jump_list:
  19.                 if (point[0]+k, point[1]+p) in self.points and (point[0]+k, point[1]+p) != (point[0], point[1]):
  20.                     self.graph.add_edge((point[0], point[1]), (point[0]+k, point[1]+p))
  21.  
  22.     def delete_all(self):
  23.         self.graph.clear()
  24.  
  25.     def delete_extra_points(self, points):
  26.         delete_points = self.points - set(points)
  27.         self.points = points
  28.         self.graph.remove_nodes_from(delete_points)
  29.  
  30.  
  31.     def add_points(self, points):
  32.         points = set(points)
  33.         new_points = points - self.points
  34.         self.points = points
  35.         self.graph.add_nodes_from(new_points)
  36.         jump_list = []
  37.         for k in [-16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16]:
  38.             for p in [-16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16]:
  39.                 if k != 0 and p != 0:
  40.                     jump_list.append((p, k))
  41.         for point in new_points:
  42.             for k, p in jump_list:
  43.                 if (point[0]+k, point[1]+p) in self.points and (point[0]+k, point[1]+p) != (point[0], point[1]):
  44.                     self.graph.add_edge((point[0], point[1]), (point[0]+k, point[1]+p))
  45.  
  46.  
  47.     def shortest_path(self, point1, point2):
  48.         try:
  49.             return nx.shortest_path(self.graph, point1, point2)
  50.         except:
  51.             return []
  52.  
  53.  
  54. if __name__ == '__main__':
  55.     #asdf = read_dst('praire.jpg.dst')
  56.     available_points = []
  57.     for i in range(100):
  58.         for j in range(100):
  59.             available_points.append((i, j))
  60.     nGraph = NetXGraph(available_points)
  61.     shortest_path = nGraph.shortest_path((2,2), (50,50))  # should return path with 0 problems
  62.     print(shortest_path)
  63.     available_points = []
  64.     for i in range(50):
  65.         for j in range(100):
  66.             available_points.append((i, j))
  67.     for i in range(60, 100):
  68.         for j in range(100):
  69.             available_points.append((i, j))
  70.     nGraph = NetXGraph(available_points)
  71.     shortest_path = nGraph.shortest_path((2,2), (80,80))  # should return empty list due to gap in the graph and not allowed to cross over points
  72.     print(shortest_path)
  73.     import pdb; pdb.set_trace()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement