1

tengo este programa de un grafo, el problema se encuentra en el metodo "Transpuesta", este programa forma un grafo en relacion a lo que le llegue en un archivo txt, debo sacar la transpuesta de ese grafo, por ello primero creo un nuevo objeto tipo grafo, que posteriormente regresara, la trans[uesta deberia ser los arcos del grafo invertidos segun el nodo, por ejemplo si el arco va a -> b , en la transpuesta deberia ir a <- b, por lo que tomo el valor de las adyacencias y formo el nuevo arco, el problema que me esta dadndo es que en vez de formar una nueva lista de adyacencias, esta escribiendo sobre las adyacencias del grafo principal, al cual se pretencde voltear. Agradeceria mucho el poder ver cual es mi error, gracias. Les comparto mi codigo.

Clase Graph:

from Arch import Arch
from Node import Node


class Graph:
    nodes = {}
    arch = []
    time=0


def __init__(self, name):
    self.name = name

def addNode(self, node):
    if node not in self.nodes:
        self.nodes[node] = Node(node)

def addArch(self, origin, destiny, cost):
    origin = self.nodes[origin]
    destiny = self.nodes[destiny]
    self.arch.append(Arch(origin, destiny, cost))
    origin.addAdyacent(destiny)

def __str__(self):
    string = self.name + '\n' + str(len(self.nodes)) + '\n' + str(len(self.arch)) + '\n'
    for a in self.nodes.values():
        string += a.__str__() + '\n'
    return string

def BFS(self, s):
    for nodo in self.nodes.values():
        nodo.d=float("Inf")
        nodo.p=None
        nodo.color="Blanco"

    s=self.nodes[s]
    s.color="Gris"
    s.d=0
    Q=[]
    Q.append(s)
    while (len(Q) > 0):
        u = Q.remove(0)
        for v in u.ady:
            if v.color == "Blanco":
                v.color= "Gris"
                v.d = u.d + 1
                v.p = u
                Q.append(v)

        u.color="Negro"


def DFS(self):
    for u in self.nodes.values():
        u.color = "white"
        u.parent = None
    self.time = 0
    for u in self.nodes.values():
        if u.color == "white":
            self.DFSvisit(u)

def DFSvisit(self, node):
    self.time += 1
    node.color = "gray"
    node.d = self.time
    for v in node.ady:
        if v.color == "white":
            v.p =  node
            self.DFSvisit(v)
    node.color = "black"
    self.time += 1
    node.f = self.time


def transpuesta(self):
    T = Graph("Transpuesta")
    for u in self.nodes.values():
        print(u)

        for v in u.ady:
            origin=v.name
            print(f'Origen: {origin}')
            destiny=u.name
            print(f'destino: {destiny}')
            cost=1
            T.addNode(origin)
            T.addNode(destiny)
            T.addArch(origin, destiny,cost)
            print(T)
            print()

    return T

Main:

from Graph import Graph

G = Graph("Graph 4")
archive = open("data/graph4.txt")
lines = archive.readlines()
nodes = int(lines[0])
archs = int(lines[1])
for i in range(2, archs + 2):
    line = lines[i]
    origin, destiny, cost = line.split()
    G.addNode(origin)
    G.addNode(destiny)
    G.addArch(origin, destiny, cost)

G.DFS()
print(G)

A= G.transpuesta()
print(A)

Node:

class Node:

def __init__(self, name):
    self.name = name
    self.color = "Blanco"
    self.parent = None
    self.discover = 0
    self.ady = []
    self.p=None
    self.d=0
    self.f=0


def addAdyacent(self, ady):
    self.ady.append(ady)

def getAdy(self):
    return self.ady

def __str__(self):
    string = f"{self.name}  (d:{self.d}/{self.f})"
    for a in self.ady:
        string += a.name + " "
    return string

Arch:

class Arch:
def __init__(self, origin, destiny, cost):
    self.origin = origin
    self.destiny = destiny
    self.cost = cost

1 respuesta 1

1

Me costó entender el problema (ni se que es un grafo xD), pero creo haber captado el error.

Explicación

El problema empieza aquí:

class Graph:
    nodes = {}
    arch = []
    time=0

    ...

Al diseñar así la clase, ésta es inicializada con los atributos de clase nodes, arch y time. Estos atributos se crean una sola vez y se guardan en la clase, no en la instancia. Cuando Python busca un atributo en una instancia, en realidad busca no solo en la instancia, si no en todo su "arbol familiar".

Te explicaré que pasa usando el atributo arch:

Cuando haces self.arch, primero se busca si la instancia en sí tiene el atributo. Como no lo tiene, hace Graph.arch (es decir, accede al atributo en la clase padre). Y obtiene esa lista.

Por lo tanto, si tus instancias no tienen el atributo arch, no importa desde cual instancia accedas a dicho atributo, en el fondo, estarás haciendo Graph.arch.

Esto produce un comportamiento en el cual los nodos, los arcos, y el tiempo son "compartidos" por todas las instancias de Graph.

Solución

Tengo entendido que lo que realmente querías es que cada grafo tuviera sus propios nodos, arcos y tiempo, que no se comparta nada.

Para eso, debes establecer estos atributos directamente al incializar la instancia.

class Graph:
    def __init__(self, name):
        self.name = name
        self.nodes = {}
        self.arch = []
        self.time=0

    ...
2
  • 1
    Gracias! Lo habia "resuelto"volviendo a inicializar los valores de nodes, arch y time despues de la instancia, pero considero que esta es la solucion definitiva, te lo agradezco! el 7 feb. a las 1:48
  • De nada! Espero también hayas aprendido algo nuevo c:
    – Dante S.
    el 7 feb. a las 2:40

Tu Respuesta

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

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