Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class NetXGraph:
- def __init__(self, custom_points=[]):
- self.graph = nx.Graph()
- self.points = set(custom_points)
- self.generate_nodes()
- self.generate_relationships()
- def generate_nodes(self):
- self.graph.add_nodes_from(self.points)
- def generate_relationships(self):
- jump_list = []
- for k in [-32, -16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16, 32]:
- for p in [-32, -16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16, 32]:
- if k != 0 and p != 0:
- jump_list.append((p, k))
- for point in self.points:
- for k, p in jump_list:
- if (point[0]+k, point[1]+p) in self.points and (point[0]+k, point[1]+p) != (point[0], point[1]):
- self.graph.add_edge((point[0], point[1]), (point[0]+k, point[1]+p))
- def delete_all(self):
- self.graph.clear()
- def delete_extra_points(self, points):
- delete_points = self.points - set(points)
- self.points = points
- self.graph.remove_nodes_from(delete_points)
- def add_points(self, points):
- points = set(points)
- new_points = points - self.points
- self.points = points
- self.graph.add_nodes_from(new_points)
- jump_list = []
- for k in [-16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16]:
- for p in [-16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16]:
- if k != 0 and p != 0:
- jump_list.append((p, k))
- for point in new_points:
- for k, p in jump_list:
- if (point[0]+k, point[1]+p) in self.points and (point[0]+k, point[1]+p) != (point[0], point[1]):
- self.graph.add_edge((point[0], point[1]), (point[0]+k, point[1]+p))
- def shortest_path(self, point1, point2):
- try:
- return nx.shortest_path(self.graph, point1, point2)
- except:
- return []
- if __name__ == '__main__':
- #asdf = read_dst('praire.jpg.dst')
- available_points = []
- for i in range(100):
- for j in range(100):
- available_points.append((i, j))
- nGraph = NetXGraph(available_points)
- shortest_path = nGraph.shortest_path((2,2), (50,50)) # should return path with 0 problems
- print(shortest_path)
- available_points = []
- for i in range(50):
- for j in range(100):
- available_points.append((i, j))
- for i in range(60, 100):
- for j in range(100):
- available_points.append((i, j))
- nGraph = NetXGraph(available_points)
- 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
- print(shortest_path)
- import pdb; pdb.set_trace()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement