Python Making possible paths for x and y points

Question

I have a list of X and Y points that are going to be imported into the program. I was wondering if it is possible to make a directory for how to connect them? Almost like a tree graph, but instead of using the edge it would use the x and y points.

The [0] in the example will be the starting point and the numbers will be the points from the imported file.

For Example

                           ----4------5
                           |
8------7-----6----[0]------1-------2-----3
       |
    9---

I found an algorithm called Breadth-first search to be able to determine the best path if given a start and an end point. I know that algorithm is for searching the possible paths but not determining the paths. If given the points from the example above..

point    X    Y
  0      0    0
  1      1    0
  2      2    0
  3      3    0
  4      1.5  0.5
  5      2.5  0.5
  6      -1   0
  7      -2   0
  8      -3   0
  9      -2.5 -0.5

I would like the points above to produce a directory like..

graph = {
        '0': ['1', '6'],
        '1': ['2', '4'],
        '2': ['3'],
        '4': ['5'],
        '6': ['7'],
        '7': ['8','9']
        }

I found a great example here for the Breadth-first Search, but it needs the directory structor already made. Any help or advice is appreciated.

Breadth-First Search.py

def bfs(graph, start, end):
    queue = []
    queue.append([start])
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print(bfs(graph, '0', '5'))

Ajax1234 · Answer 1 · 2019-04-28T03:14:16.897

Assuming you meant to include 5 as a key in your result, you can use recursion to create the desired dictionary:

import math, collections
data = {0.0: [0.0, 0.0], 1.0: [1.0, 0.0], 2.0: [2.0, 0.0], 3.0: [3.0, 0.0], 4.0: [1.5, 0.5], 5.0: [2.5, 0.5], 6.0: [-1.0, 0.0], 7.0: [-2.0, 0.0], 8.0: [-3.0, 0.0], 9.0: [-2.5, -0.5]}
def group(d, start, seen = []):
   x, y = d[start]
   r = [a for a, [j, k] in d.items() if a != start and a not in seen and math.hypot(abs(x-j), abs(y-k)) <= 1]
   if not r:
     return {}
   result = {start:r}
   for i in r:
     result.update(group(d, i, seen+[start, *r]))
   return result

result = group(data, 0)

Output:

{0: [1.0, 6.0], 1.0: [2.0, 4.0], 2.0: [3.0, 5.0], 4.0: [5.0], 5.0: [3.0], 6.0: [7.0], 7.0: [8.0, 9.0]}

Converting values to strings:

new_result = {str(int(a)):list(map(str, map(int, b))) for a, b in result.items()}

Output:

{'0': ['1', '6'], '1': ['2', '4'], '2': ['3', '5'], '4': ['5'], '5': ['3'], '6': ['7'], '7': ['8', '9']}

This is great and thank you for your response, but I actually meant to leave `5` out because it was the end of that run and is not connected to anything down stream. Just like `3`,`8`,and `9, — laxer, Apr 28 '19 at 03:20
@laxer Thank you for your comment. Can you clarify how you wish to associate different values? `3`, `8`, and `9` are not present because they do not have a path with any node `<= 1`, however, could not `5` have a path to `2`, and vice versa? — Ajax1234, Apr 28 '19 at 03:45

score 0 · Answer 2 · answered Apr 28 '19 at 03:34

As you said, the breadth-first-search is not an algorithm to find the best path given two nodes, it only tells you if there is a path connecting them. If you want the best path there are three famous algorithms for that : Dijkstra, Bellman-Ford and Floyd-Warshall. In your case I believe Dijkstra would be the best choice.

There is an easy to use and wonderful library in Python to work with graphs, it's called Networkx. It has a lot of methods for almost every problem related to graphs, including the algorithms I mentioned. Here's a link for Dijkstra's algorithm implemented on this library.

Python Making possible paths for x and y points

2 Answers2