Calculate Pattern route with python

Question

I've got a graph defined like this:

graph = {
    'A': ['H', 'B'],
    'B': ['H'. 'A', 'C', 'D', 'F'],
    'C': ['B', 'D'],
    'D': ['H', 'B', 'C', 'F', 'E'],
    'E': ['F', 'D'],
    'F': ['E', 'D', 'B', 'H', 'G'],
    'G': ['F', 'H'],
    'H': ['A', 'B', 'D', 'F', 'G'],
}

and i was wondering what's the best way to calculate the route from A to itself, using all the edges but without passing on the same edge.

Probably there's no solution to the problem explained above but i was curious about the Python implementation for this type of problem.

Thanks

Try to find this book "Python Algorithms: Mastering Basic Algorithms in the Python Language" where are a lot information about implementation graph in python. — Denis, Aug 19 '13 at 15:21

score 1 · Answer 1 · answered Aug 19 '13 at 15:53

It's totally possible, if not a bit difficult. Here's how I would approach the problem.

graph = {
    'A': ['H', 'B'],
    'B': ['H', 'A', 'C', 'D', 'F'],
    'C': ['B', 'D'],
    'D': ['H', 'B', 'C', 'F', 'E'],
    'E': ['F', 'D'],
    'F': ['E', 'D', 'B', 'H', 'G'],
    'G': ['F', 'H'],
    'H': ['A', 'B', 'D', 'F', 'G'],
}

def is_goal(path): 
    states_visited = set(path);
    for state in graph.keys():
        if state not in states_visited:
            return False
    return path[-1] == 'A'

def successors(state):
    return graph[state]

def sps(start, is_goal, successors):
    explored_paths = set((start,))
    explored_edges = {}
    explored_edges[(start,)] = set()
    frontier = [[start]]
    while frontier:
        #breadth first search
        path = frontier.pop(0)
        s = path[-1]
        for state in successors(s):
            new_path = path + [state]
            #cast to tuple for hashing
            hashable_path = tuple(path)
            hashable_new_path = tuple(new_path)
            if hashable_new_path not in explored_paths:
                edge = tuple(sorted(new_path[-2:]))
                new_set = set()
                new_set.add(edge);
                if edge not in explored_edges[hashable_path]:
                    explored_paths.add(hashable_new_path)
                    explored_edges[hashable_new_path] = explored_edges[hashable_path].union(new_set)
                    if is_goal(new_path):
                        return new_path
                    else: 
                        frontier.append(new_path)

    return "No path found"

if __name__ == '__main__':
    print(sps('A', is_goal, successors))

Execute in the terminal

$ python3 sps.py 
['A', 'H', 'B', 'C', 'D', 'H', 'F', 'B', 'A']

Just realized that you asked for all edges to be visited, not all states. I'll leave it to you to modify is_goal to create a shortest path search for that situation. — Madison May, Aug 19 '13 at 16:00

Calculate Pattern route with python

1 Answers1