Я пытаюсь сделать неориентированный граф из списка смежности, чтобы попрактиковаться в алгоритме Min Cut Каргера. Ниже приведен мой код
class Vertex(object):
'''Represents a vertex, with the indices of edges
incident on it'''
def __init__(self,name,edgeIndices=[]):
self.name = name
self.edgeIndices = edgeIndices
def getName(self):
return self.name
def addEdge(self,ind):
self.edgeIndices.append(ind)
def getEdges(self):
return self.edgeIndices
def __eq__(self,other):
return self.name == other.name
class Edge(object):
'''Represents an edge with the indices of its endpoints'''
def __init__(self,ends):
self.ends = ends
def getEnds(self):
return self.ends
def __eq__(self,other):
return (self.ends == other.ends)\
or ((self.ends[1],self.ends[0]) == other.ends)
class Graph(object):
def __init__(self,vertices,edges):
self.edges = edges
self.vertices = vertices
def createGraph(filename):
'''Input: Adjacency list
Output: Graph object'''
vertices = []
edges = []
with open(filename) as f:
for line in f:
elements = line.split()
newVert = Vertex(elements[0])
if newVert not in vertices:
vertices.append(newVert)
for verts in elements[1:]:
otherVert = Vertex(verts)
if otherVert not in vertices:
vertices.append(otherVert)
end1 = vertices.index(newVert)
end2 = vertices.index(otherVert)
newEdge = Edge((end1,end2))
if newEdge not in edges:
edges.append(newEdge)
newVert.addEdge(edges.index(newEdge))
return Graph(vertices,edges)
Предположим, что список смежности выглядит следующим образом с вершинами, представленными целыми числами.
1 -> 2,3,4
2 -> 1,3
3 -> 1,2,4
4 -> 1,3
Всего в этом графе будет пять ребер, поэтому длина списка, содержащего индексы ребер, с которыми связана вершина, не может превышать 5.
Например, я ожидаю, что вершина «2» будет иметь индексы только двух ребер, то есть ребер с вершинами 1 и 3. Вместо этого я получаю [0, 1, 2, 3, 0, 2, 1, 3]. Мне нужна помощь, чтобы понять, что происходит не так.
