grafo.py

# coding=utf-8


class Grafo:
    '''
    crea una instancia de grafos
    '''

    __vertices = []
    __aristas = []

    def addVertice(self, vertice):
        '''
        añade un vertice al grafo
        '''
        self.__vertices.append(vertice)

    def verticeByNombre(self, nombre):
        '''
        encuentra un vertice por el nombre de la ciudad sin tener en cuenta
        maysculas o minusculas
        '''

        matches = filter(
            lambda item: item.nombre().lower() == nombre.lower(),
            self.__vertices
        )

        assert matches, 'No se encuentra ninguna ciudad con ese nombre'

        return matches[0]

    def conectar(self, origen, destino):
        '''
        conecta 2 vertices mediante una arista
        '''

        if not origen in self.__vertices:

            self.__vertices.append(origen)

        if not destino in self.__vertices:

            self.__vertices.append(destino)

        self.__aristas.append(Arista(origen, destino))

    def rutaByNames(self, origen_nombre, destino_nombre):
        '''
        devuelve la ruta dado el nombre de la ciudad de origen y la de destino
        '''
        return self.ruta(
            self.verticeByNombre(origen_nombre),
            self.verticeByNombre(destino_nombre)
        )

    def ruta(self, origen, destino):
        '''
        encuentra la ruta dado el vertice de origen y el de destino,
        retornandola en una lista
        '''
        assert origen in self.__vertices, 'el vertice de origen no se encuentra'
        assert destino in self.__vertices, 'el vertice de destino no se encuentra'

        return [origen.nombre()] + origen.findVertice(destino)

    def __str__(self):

        return str(self.__listaVertices)


class Vertice:
    '''
    crea una instancia de vertice
    '''

    __aristas = []

    def __init__(self, nombre, poblacion, nivel_economico, booleano):
        self.__nombre = nombre
        self.__poblacion = poblacion
        self.__nivel_economico = nivel_economico

        # le puse booleano porque no se sabe para que puta es ese dato
        self.__booleano = booleano

    def nombre(self):
        '''
        devuelve el dato
        '''

        return self.__nombre

    def poblacion(self):
        '''
        devuelve la poblacion de la ciudad
        '''

        return self.__poblacion

    def nivel_economico(self):
        '''
        devuelve el nivel economico promedio de la poblacion de la ciudad
        '''

        return self.__nivel_economico

    def booleano(self):
        '''
        un booleano que no se sabe para que carajo es pero parecia importante
        '''

        return self.__booleano

    def aristas(self):
        '''
        retorna las lista de aristas
        '''

        return self.__aristas

    def adyacentes(self):
        '''
        retorna la lista de vertices adyacentes conectados mediante las aristas
        '''
        for arista in self.aristas():

            origen, destino = arista.vertices()

            yield arista, destino if self is origen else origen

    def findVertice(self, destino, visitados=[]):

        rutas = []

        for arista, adyacente in self.adyacentes():

            if adyacente is destino:

                return [self.nombre(), adyacente.nombre()]

            if not (arista, adyacente) in visitados:

                visitados.append((arista, adyacente))

                ruta = adyacente.findVertice(destino, visitados)

                if ruta:
                    rutas.append(ruta)

        if rutas:
            return min(rutas)

    def addArista(self, arista):
        '''
        añade una arista a la lista de aristas del vertice
        '''

        self.__aristas.append(arista)

    def __str__(self):

        return "{nombre}".format(nombre=self.__nombre)


class Arista:
    '''
    crea una instancia de arista
    '''

    def __init__(self, origen, destino):

        assert not origen is destino, 'El origen y el destino son el mismo'

        self.__origen = origen
        self.__destino = destino

        # añadimos la aristas a los vertices de los extremos
        self.__origen.addArista(self)
        self.__destino.addArista(self)

    def origen(self):
        '''
        devuelve el vertice de origen
        '''

        return self.__origen

    def destino(self):
        '''
        devuelve el vertice de destino
        '''

        return self.__destino

    def vertices(self):
        '''
        retorna el vertice destino de la arista
        '''

        return self.__origen, self.__destino

    def magnitud(self):
        '''
        retorna la magnitud de la arista
        '''

        return self.__magnitud

    def __str__(self):

        return "({origen} - {destino})".format(
            origen=self.__origen,
            destino=self.__destino,
        )

test.py

# coding=utf-8


from grafo import Grafo
from grafo import Vertice

prueba = Grafo()


# ciudades

ciudades = (
    ("Salta", 5000000, "medio", False),
    ("Mendoza", 10000000, "alto", True),
    ("Viedma", 500000, "medio", False),
    ("Santa Fe", 7500000, "medio", False),
    ("Corrientes", 5000000, "alto", True),
    ("Buenos Aires", 15000000, "alto", True),
    ("Cordoba", 10000000, "alto", False),
    ("Neuquen", 5000000, "bajo", True),
    ("Santa Rosa", 5000000, "bajo", False),
    ("Jujuy", 50000, "alto", True),
    ("Posadas", 500000, "alto", True),
    ("Tucuman", 5000000, "bajo", False),
    ("Catamarca", 5000000, "medio", True),
    ("La Rioja", 5000000, "medio", False),
    ("Santiago del Estero", 5000000, "alto", False),
    ("San Luis", 10000000, "medio", False),
    ("Formosa", 500000, "alto", True),
    ("Resistencia", 500000, "medio", False),
    ("San Juan", 500000, "medio", True),
    ("Parana", 500000, "medio", False),
    ("Rawson", 500000, "bajo", False),
    ("Ushuaia", 500000, "bajo", True),
    ("Rio Gallegos", 500000, "bajo", False)
)


# se agregan todas las ciudades al grafo

for ciudad in ciudades:
    prueba.addVertice(Vertice(*ciudad))

# adyacencias

adyacencias = {
    "salta": [
        "buenos aires", "mendoza", "cordoba", "neuquen", "tucuman", "la rioja",
        "rawson", "rio gallegos"
    ],
    "mendoza": [
        "viedma", "santa fe", "neuquen", "la rioja", "san luis", "resistencia",
        "san juan", "rawson", "santa rosa"
    ],
    "viedma": [
        "cordoba", "santa rosa", "jujuy", "catamarca", "la rioja", "san luis",
        "formosa"
    ],
    "santa fe": [
        "corrientes", "cordoba", "tucuman", "catamarca", "santiago del estero",
        "san juan"
    ],
    "corrientes": [
        "buenos aires", "santa rosa", "posadas", "tucuman", "san luis",
        "parana", "ushuaia", "rio gallegos", "jujuy"
    ],
    "buenos aires": [
        "neuquen", "jujuy", "la rioja", "resistencia", "san juan"
    ],
    "cordoba": ["tucuman", "catamarca"],
    "neuquen": ["salta", "mendoza", "parana"],
}

for ciudad_nombre, ciudades_adyacentes in adyacencias.items():

    for ciudad_adyacente in ciudades_adyacentes:

        prueba.conectar(
            prueba.verticeByNombre(ciudad_nombre),
            prueba.verticeByNombre(ciudad_adyacente)
        )


print prueba.rutaByNames("salta", "catamarca")