0

tengo mi programa de implementacion de grafos. El asunto esta en que quisiera probar otros grafos con las mismas clases pero al declarar mas grafos siempre me imprime el mismo. Pero no tengo idea de como se realiza esto en Python, podria alguien asesorarme?

class Vertice:
    def __init__(self,n):
        self.nombre = n
        self.vecinos = list()
        self.distancia = 9999
        self.color = 'white'
        self.pred = -1

    def agregarVecino(self, v):
        if v not in self.vecinos:
            self.vecinos.append(v)
            self.vecinos.sort()

class Grafo:
vertices = {}

def agregarVertice(self, vertice):
    if isinstance(vertice, Vertice) and vertice.nombre not in self.vertices:
        self.vertices[vertice.nombre] = vertice
        return True
    else:
        return False

def agregarArista(self, u, v):
    if u in self.vertices and v in self.vertices:
        for key, value in self.vertices.items():
            if key == u:
                value.agregarVecino(v)
            if key == v:
                value.agregarVecino(u)
        return True
    else:
        return False

def bfs(self, vert):
    vert.distancia = 0
    vert.color = 'gray'
    vert.pred = -1
    q = list()

    q.append(vert.nombre)

    while len(q) > 0:

        u = q.pop()
        node_u  = self.vertices[u]
        for v in node_u.vecinos:
            node_v = self.vertices[v]
            if node_v.color == 'white':
                node_v.color = 'gray'
                node_v.distancia = node_u.distancia + 1
                node_v.pred = node_u.nombre
                q.append(v)
        self.vertices[u].color = 'black'        

def imprimeGrafo (self):
    for key in sorted(list(self.vertices.keys())):
        print ("Vertice " + key + " sus vecinos son "+ str(self.vertices[key].vecinos) )
        print("La distancia de A a " + key + " es: "+ str(self.vertices[key].distancia))
        print()
class Controladora:
def main(self):
    g = Grafo()
    a = Vertice('A')
    g.agregarVertice(a)

    for i in range(ord('A'), ord('K')):
        g.agregarVertice(Vertice(chr(i)))


    edges = ['AB','AE','BF','CG','DE','DH','EH','FG','FI','FJ','GJ']

    for edge in edges:
        g.agregarArista(edge[:1], edge[1:])
    g.bfs(a)
    g.imprimeGrafo()    

obj = Controladora()
obj.main()

2 respuestas 2

1

No se si he entendido correctamente tu pregunta, creo que lo que deseas es saber como puedes crear varios grafos distintos(con diferentes nodos y aristas) y trabajar con ellos. Basándome en esto voy a intentar contestar.

En tu código creas un solo grafo que es instanciado en tu clase Controladora, esta clase tal y como está tiene poco sentido. Para crear varios grafos simplemente tienes que crear varios objetos de la clase Grafo con nombres y atributos distintos como haces con los vértices. Para no modificar mucho tu código he añadido dos métodos a tu clase Grafo:

  • agregarVertices permite crear los vertices que queramos a partir de una lista o conjuntos con los nombres, instancia para cada uno un objeto de la clase Vertice y luego llama a tu método crearVertice. Se podria unir todo en un solo método, he preferido hacerlo así para tocar lo menos posible tu código.

  • agregarAristas crea las aristas que le pasemos en forma de lista o conjunto de cadenas de la forma 'AB' donde A es el nombre de un vertice y B el otro. Si decides crear vertices de más de un carácter como nombre te aconsejo modificar esto y pasar las arista en forma de tuplas: [('A', 'B'), ('AA', 'BB')].

He modificado el método bfs, ahora recive como parámetro el nombre del nodo al que se quiere calcular las distancias, no la instancia en si. En general tu clase principal, sobre la que deberias trabajar deberia ser la clase Grafo y que sea esta la que instancie y maneje los vertices. El código podría quedar así:

class Vertice:

    def __init__(self, n):
        self.nombre = n
        self.vecinos = list()
        self.distancia = 9999
        self.color = 'white'
        self.pred = -1

    def agregarVecino(self, v):
        if v not in self.vecinos:
            self.vecinos.append(v)
            self.vecinos.sort()

class Grafo:
    def __init__(self):
        self.vertices = dict()

    def agregarVertices(self, vertices):
        for v in vertices:
            n = Vertice(v)
            self.agregarVertice(n)

    def agregarAristas(self, aristas):
        for arista in aristas:
            self.agregarArista(arista[0], arista[1])

    def agregarVertice(self, vertice):
        if isinstance(vertice, Vertice) and vertice.nombre not in self.vertices:
            self.vertices[vertice.nombre] = vertice
            return True
        else:
            return False

    def agregarArista(self, u, v):
        if u in self.vertices and v in self.vertices:
            for key, value in self.vertices.items():
                if key == u:
                    value.agregarVecino(v)
                if key == v:
                    value.agregarVecino(u)
            return True
        else:
            return False

    def bfs(self, vert):
        vert = self.vertices[vert]
        vert.distancia = 0
        vert.color = 'gray'
        vert.pred = -1
        q = list()

        q.append(vert.nombre)

        while len(q) > 0:

            u = q.pop()
            node_u  = self.vertices[u]
            for v in node_u.vecinos:
                node_v = self.vertices[v]
                if node_v.color == 'white':
                    node_v.color = 'gray'
                    node_v.distancia = node_u.distancia + 1
                    node_v.pred = node_u.nombre
                    q.append(v)
            self.vertices[u].color = 'black'        

    def imprimeGrafo (self):
        for key in sorted(list(self.vertices.keys())):
            print ("Vertice " + key + " sus vecinos son "+ str(self.vertices[key].vecinos) )
            print("La distancia de A a " + key + " es: "+ str(self.vertices[key].distancia))
            print()



#Creamos un grafo como en tu ejemplo al que llamamos g1:
vertices = [chr(i) for i in range(ord('A'), ord('K'))]
edges = ['AB','AE','BF','CG','DE','DH','EH','FG','FI','FJ','GJ']
g1 = Grafo()
g1.agregarVertices(vertices)
g1.agregarAristas(edges)
g1.bfs('A')


#Creamos otro un grafo al que llamamos g2:
vertices = [chr(i) for i in range(ord('L'), ord('T'))]
edges = ['LM','LP','QT','MJ','NK','OQ','QT','TP']
g2 = Grafo()
g2.agregarVertices(vertices)
g2.agregarAristas(edges)
g2.bfs('L')

#Ahora tenemos dos grafos distintos y podemos trabajar con ellos usando sus nombres, vamos a imprimirlos:
print(print('='*50+'\nGRAFO G1:\n'+'='*50))
g1.imprimeGrafo()

print('='*50+'\nGRAFO G2:\n'+'='*50)
g2.imprimeGrafo()

Como ves en el ejemplo hemos creado dos grafos distintos llamados g1 y g2, podemos crear los que queramos y luego acceder a ellos usando esos nombres.

1
  • Creo que si no me di a entender muy bien pero si me habéis captado el problema, es justo lo que necesitaba. Muchas Gracias por tu tiempo. Commented el 21 mar. 2017 a las 11:51
1

En Python, múltiples nombres pueden vincularse al mismo objeto. Esto se conoce como aliasing. Normalmente el aliasing puede ignorarse sin problemas cuando se maneja tipos básicos inmutables (números, cadenas, tuplas). Sin embargo, el aliasing, o renombrado, tiene un efecto sorpresivo sobre la semántica de código Python que involucra objetos mutables como listas, diccionarios, y la mayoría de otros tipos.

obj = Controladora()
obj2 = obj

obj2 es la misma instancia que obj. Para obtener una instancia distinta es necesario hacer una copia

import copy

otro = copy.copy(obj)
2
  • 1
    Eso no funciona por la sencilla razón de que no existe el método copy implementado en la clase a copiar. Funciona con algunas clases preconstruidas en python 3.x (listas, diccionarios, conjuntos, etc) porque implementan ese método ellas mismas. Si queremos hacer esto en python 2.x con listas, conjuntos, etc o en python2-3 con clases propias o bién implementamos un método copy dentro de la clase o usamos la biblioteca copy. Saludos.
    – FJSevilla
    Commented el 21 mar. 2017 a las 9:42
  • tienes razón, gracias
    – ixi
    Commented el 21 mar. 2017 a las 14:30

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.