Grafo busca em amplitude e profundidade

grafo_busca.py

"""Algoritmos de busca em grafos escolhidos para o projeto."""


class BuscaEmProfundidade(object):
    def algoritmo(self, grafo, inicio, objetivo):
        def buscaprofundidade(grafo, inicio, objetivo):
            pilha = [(inicio, [inicio])]
            while pilha:
                (vertice, caminho) = pilha.pop()
                for next in grafo[vertice] - set(caminho):
                    if next == objetivo:
                        yield caminho + [next]
                    else:
                        pilha.append((next, caminho + [next]))

        try:
            return next(buscaprofundidade(grafo, inicio, objetivo))
        except StopIteration:
            return None


class BuscaEmAmplitude(object):
    def algoritmo(self, grafo, inicio, objetivo):
        def buscaamplitude(grafo, inicio, objetivo):
            fila = [(inicio, [inicio])]
            while fila:
                (vertice, caminho) = fila.pop(0)
                for next in grafo[vertice] - set(caminho):
                    if next == objetivo:
                        yield caminho + [next]
                    else:
                        fila.append((next, caminho + [next]))

        try:
            return next(buscaamplitude(grafo=grafo, inicio=inicio, objetivo=objetivo))
        except StopIteration:
            return None


class Busca(object):
    def __init__(self, grafo=None, inicio=None, objetivo=None):
        if grafo is None or inicio is None or objetivo is None:
            raise Exception('Verifique se os parametros foram informados corretamente.')
        self.grafo = grafo
        self.inicio = inicio
        self.objetivo = objetivo

    def profundidade(self):
        profundidade = BuscaEmProfundidade()
        return profundidade.algoritmo(grafo=self.grafo, inicio=self.inicio, objetivo=self.objetivo)

    def amplitude(self):
        amplitude = BuscaEmAmplitude()
        return amplitude.algoritmo(grafo=self.grafo, inicio=self.inicio, objetivo=self.objetivo)