eg:原来A→B，更改为A⬅️B，并写出测试代码
比如现在是
(0,1,5)
(0,5,2)
(1,2,4)
(2,3,9)
(3,4,7)
(3,5,3)
(4,0,1)
(5,4,8)
调用transpose之后变成
(1,0,5)
(5,0,2)
(2,1,4)
(3,2,9)
(4,3,7)
(5,3,3)
(0,4,1)
(4,5,8)
import sys
import os
import unittest
class Graph:
def __init__(self):
self.vertices = {}
self.numVertices = 0
def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertices[key] = newVertex
return newVertex
def getVertex(self,n):
if n in self.vertices:
return self.vertices[n]
else:
return None
def __contains__(self,n):
return n in self.vertices
def addEdge(self,f,t,cost=0):
if f not in self.vertices:
nv = self.addVertex(f)
if t not in self.vertices:
nv = self.addVertex(t)
self.vertices[f].addNeighbor(self.vertices[t],cost)
def getVertices(self):
return list(self.vertices.keys())
def __iter__(self):
return iter(self.vertices.values())
class Vertex:
def __init__(self,num):
self.id = num
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0
# def __lt__(self,o):
# return self.id < o.id
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def setColor(self,color):
self.color = color
def setDistance(self,d):
self.dist = d
def setPred(self,p):
self.pred = p
def setDiscovery(self,dtime):
self.disc = dtime
def setFinish(self,ftime):
self.fin = ftime
def getFinish(self):
return self.fin
def getDiscovery(self):
return self.disc
def getPred(self):
return self.pred
def getDistance(self):
return self.dist
def getColor(self):
return self.color
def getConnections(self):
return self.connectedTo.keys()
def getWeight(self,nbr):
return self.connectedTo[nbr]
def __str__(self):
return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
def getId(self):
return self.id
if __name__ == '__main__':
# build a graph
g = Graph()
for i in range(6):
g.addVertex(i)
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
print ('Before transpose:\n')
for v in g:
for w in v.getConnections():
print ("( %s , %s, %d )" % (v.getId(), w.getId(), v.getWeight(w)))
print ('After transpose:\n')
for v in g:
for w in v.getConnections():
print ("( %s , %s, %d )" % (v.getId(), w.getId(), v.getWeight(w)))
import sys
import os
import unittest
class Graph:
def __init__(self):
self.vertices = {}
self.numVertices = 0
def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertices[key] = newVertex
return newVertex
def getVertex(self,n):
if n in self.vertices:
return self.vertices[n]
else:
return None
def __contains__(self,n):
return n in self.vertices
def addEdge(self,f,t,cost=0):
if f not in self.vertices:
nv = self.addVertex(f)
if t not in self.vertices:
nv = self.addVertex(t)
self.vertices[f].addNeighbor(self.vertices[t],cost)
self.vertices[t].addrevNeighbor(self.vertices[f],cost)
def getVertices(self):
return list(self.vertices.keys())
def __iter__(self):
return iter(self.vertices.values())
def transpose(self):
for n in self.vertices:
v=self.vertices[n]
v.connectedTo,v.revconnectedTo = v.revconnectedTo,v.connectedTo
class Vertex:
def __init__(self,num):
self.id = num
self.connectedTo = {}
self.revconnectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0
# def __lt__(self,o):
# return self.id < o.id
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def addrevNeighbor(self,nbr,weight=0):
self.revconnectedTo[nbr] = weight
def setColor(self,color):
self.color = color
def setDistance(self,d):
self.dist = d
def setPred(self,p):
self.pred = p
def setDiscovery(self,dtime):
self.disc = dtime
def setFinish(self,ftime):
self.fin = ftime
def getFinish(self):
return self.fin
def getDiscovery(self):
return self.disc
def getPred(self):
return self.pred
def getDistance(self):
return self.dist
def getColor(self):
return self.color
def getConnections(self):
return self.connectedTo.keys()
def getWeight(self,nbr):
return self.connectedTo[nbr]
def __str__(self):
return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
def getId(self):
return self.id
if __name__ == '__main__':
# build a graph
g = Graph()
for i in range(6):
g.addVertex(i)
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
print ('Before transpose:\n')
for v in g:
for w in v.getConnections():
print ("( %s , %s, %d )" % (v.getId(), w.getId(), v.getWeight(w)))
g.transpose()
print ('After transpose:\n')
for v in g:
for w in v.getConnections():
print ("( %s , %s, %d )" % (v.getId(), w.getId(), v.getWeight(w)))
g.transpose()
print ('After transpose back:\n')
for v in g:
for w in v.getConnections():
print ("( %s , %s, %d )" % (v.getId(), w.getId(), v.getWeight(w)))
#Before transpose:
#
#( 0 , 1, 5 )
#( 0 , 5, 2 )
#( 1 , 2, 4 )
#( 2 , 3, 9 )
#( 3 , 4, 7 )
#( 3 , 5, 3 )
#( 4 , 0, 1 )
#( 5 , 4, 8 )
#( 5 , 2, 1 )
#After transpose:
#
#( 0 , 4, 1 )
#( 1 , 0, 5 )
#( 2 , 1, 4 )
#( 2 , 5, 1 )
#( 3 , 2, 9 )
#( 4 , 3, 7 )
#( 4 , 5, 8 )
#( 5 , 0, 2 )
#( 5 , 3, 3 )
#After transpose back:
#
#( 0 , 1, 5 )
#( 0 , 5, 2 )
#( 1 , 2, 4 )
#( 2 , 3, 9 )
#( 3 , 4, 7 )
#( 3 , 5, 3 )
#( 4 , 0, 1 )
#( 5 , 4, 8 )
#( 5 , 2, 1 )
#