Michael Michael - 3 days ago 5
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:

    2
    / \
    / \
    / \
    1-------3
    """


    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]:
    points[current_point].remove(prev_point)
    points[prev_point].remove(current_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))
    results.append(result)
    return results

    print(collect(points))


    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
    for
    -loop in
    f
    being executed exactly once each time it is called (and it's being called 3 times), since the execution is terminated by
    return
    each time. However, I have up until now failed to find a way to avoid this - I played around with making
    f
    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
    return
    s in
    find_paths
    with
    yield
    s.
    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):
    print(f)

    Answer

    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]
        else:
            for next_point in points[current_point]:
                new_points = deepcopy(points)
                new_points[current_point].remove(next_point)
                new_points[next_point].remove(current_point)
                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))
            results.extend(list(result))
        return results
    
    print(collect(points))
    

    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],
        }
    
    Comments