Michael Michael - 1 year ago 69
Python Question

Python - finding all paths between points of arbitrary shape

My goal for the program is the following:

Given any shape (represented as enumerated points and their connections to other points), return a list containg all possible paths (as strings/lists/...). A path is a 'drawing' of the given shape, in which:

  • no connection has been used more than once and

  • the 'pen' hasn't been lifted (example included below).

  • animation of a house being drawn as described above

    The following code is essentially what I've come up with so far. It's not the code of the actual program, but the basic semantics are the same (i.e. if this code will work, my program will work too).

    Example used:

    / \
    / \
    / \

    from copy import deepcopy

    points = {1: [2,3],
    2: [1,3],
    3: [1,2]}

    def find_paths(prev_point, points):
    for current_point in points[prev_point]:
    return [prev_point] + find_paths(current_point, points)
    return [prev_point]

    def collect(points):
    results = []
    for first_point in points:
    result = find_paths(first_point, deepcopy(points))
    return results


    My struggle has been to make it return all paths. As of now, it lists only 3 (out of 6). I do understand that the issue arises from the
    -loop in
    being executed exactly once each time it is called (and it's being called 3 times), since the execution is terminated by
    each time. However, I have up until now failed to find a way to avoid this - I played around with making
    a generator but this has given me a list of generators as the end result, no matter how I tried to change it.

    Any help is appreciated!

    EDIT: The generator-version I had simply replaced the
    s in
    So the last two lines look like:

    yield [prev_point] + find_paths(current_point, points)
    yield [prev_point]

    Additionally, I played around with a 'flattener' for generators, but it didn't work at all:

    def flatten(x):
    if callable(x):
    for i in x:
    yield flatten(i)
    yield x

    def func():
    yield 1
    lis = [1,2,func]

    for f in flatten(lis):

    Answer Source

    I think the following works. I based it off of your original code, but did a few things (some necessary, some not):

    1. Rename parameters in find_paths to make more sense for me. We are working with the current_point not the previous_point, etc.
    2. Add an end condition to stop recursion.
    3. Make a copy of points for every possible path being generated and return (yield) each one of those possible paths. Your original code didn't have logic for this since it only expected one result per call to find_paths, but that doesn't really make sense when using recursion like this. I also extend my final result for the same reason.

    Here is the code:

    from copy import deepcopy
    points = {1: [2,3],
              2: [1,3],
              3: [1,2]}
    def find_paths(current_point, points):
        if len(points[current_point]) == 0:
            # End condition: have we found a complete path? Then yield
            if all(not v for v in points.values()):
                yield [current_point]
            for next_point in points[current_point]:
                new_points = deepcopy(points)
                paths = find_paths(next_point, new_points)
                for path in paths:
                    yield [current_point] + path
    def collect(points):
        results = []
        for first_point in points:
            result = find_paths(first_point, deepcopy(points))
        return results

    Results in:

    [1, 2, 3, 1]
    [1, 3, 2, 1]
    [2, 1, 3, 2]
    [2, 3, 1, 2]
    [3, 1, 2, 3]
    [3, 2, 1, 3]

    Your original example image should work with the following:

    points = {
        1: [2,3],
        2: [1,3,4,5],
        3: [1,2,4,5],
        4: [2,3,5],
        5: [2,3,4],
    Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download