SnippetBox

Content

Shell
Raw URL 
from collections import deque

class Graph:

    def __init__(self, directed=True):
        self.edges = {}
        self.directed = directed

    def add_edge(self, node1, node2, reversed=False):
        try:
            neighbors = self.edges[node1]
        except KeyError:
            neighbors = set()

        neighbors.add(node2)
        self.edges[node1] = neighbors

        if not self.directed and not reversed:
            self.add_edge(node2, node1, True)

    def neighbors(self, node):
        try:
            return self.edges[node]
        except KeyError:
            return []

    def breadth_first_search(self, start, goal):

        found, fringe, visited, came_from = (
            False,
            deque([start]),
            set([start]),
            {start: None}
        )

        print('{:11s} | {}'.format('Expand Node', 'Fringe'))
        print(' ' * 11 + '|')
        print('{:11s} | {}'.format('-', start))

        while not found and len(fringe):

            current = fringe.pop()

            print('{:11s}'.format(current), end=' | ')

            if current == goal:
                found = True
                break

            for node in self.neighbors(current):
                if node not in visited:
                    visited.add(node)
                    fringe.appendleft(node)
                    came_from[node] = current

            print(', '.join(fringe))

        if found:
            print()
            return came_from
        else:
            print('No path from {} to {}'.format(start, goal))

    @staticmethod
    def print_path(came_from, goal):

        parent = came_from[goal]

        if parent:
            Graph.print_path(came_from, parent)
        else:
            print(goal, end='')
            return

        print(' ->', goal, end='')

    def __str__(self):
        return str(self.edges)


graph = Graph(directed=False)

graph.add_edge('A', 'B')
graph.add_edge('A', 'S')
graph.add_edge('S', 'G')
graph.add_edge('S', 'C')
graph.add_edge('C', 'F')
graph.add_edge('G', 'F')
graph.add_edge('C', 'D')
graph.add_edge('C', 'E')
graph.add_edge('E', 'H')
graph.add_edge('G', 'H')

start, goal = 'A', 'H'

traced_path = graph.breadth_first_search(start, goal)

if traced_path:
    print('Path:', end=' ')
    Graph.print_path(traced_path, goal)
    print()