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