从邻接表中创建无向图

Question

我试图从邻接表中创建一个无向图来练习Karger的最小切割算法。下面是我的代码

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]。 我需要帮助来弄清楚发生了什么问题。

Answer 1

第一个错误来自Vertex init。当传递一个列表作为默认参数时，Python实例化一次，并将这个实例与未来的所有Vertex实例共享。 传递无，如果没有给出列表，则使用本地列表。

class Vertex(object): 
    def __init__(self,name,edgeIndices=None): 
     self.name = name 
     self.edgeIndices = edgeIndices if edgeIndices else [] 

在createGraph方法中，当图的顶点已经存在时，您需要使用它。查看增加的else: newVert = ... 你似乎也有一个ligne分裂的问题。请参阅elements[2].split(',')的迭代。

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) 
      else: 
       newVert = vertices[vertices.index(newVert)] 

      for verts in elements[2].split(','): 
       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) 

作为一个方面说明，我会尝试使用字典存储顶点（和边缘），并做了查找。 List.index被使用了很多，你可能会创建很多对象。

Answer 2

我建议看看Dict，OrderedDict，基于链表的图表实现。然后根据列表和索引更有效。 为了让你的代码工作，你可以做到以下几点：

改变一个顶点，以避免在前面的回答中描述的问题：

class Vertex(object): 
    def __init__(self,name, edgeIndices=None): 
     self.name = name 
     self.edgeIndices = edgeIndices or []  

让图形做了一些工作：

class Graph(object): 
    def __init__(self): 
     self.edges = [] 
     self.vertices = [] 

    def add_vertex(self, name): 
     vertex = Vertex(name) 
     if vertex not in self.vertices: 
      self.vertices.append(vertex) 

    def add_edge(self, *names): 
     self._add_vertices(names) 
     edge = self._add_edge(names) 
     self._update_vertices_links(edge, names) 

    def get_vertex_index(self, name): 
     vertex = Vertex(name) 
     return self.vertices.index(vertex) 

    def get_vertex(self, name): 
     return self.vertices[self.get_vertex_index(name)] 

    def _update_vertices_links(self, edge, names): 
     for name in names: 
      vertex = self.get_vertex(name) 
      vertex.addEdge(self.edges.index(edge)) 

    def _add_edge(self, names): 
     edge = Edge((self.get_vertex_index(names[0]), self.get_vertex_index(names[1]))) 
     if edge not in self.edges: 
      self.edges.append(edge) 
     return edge 

    def _add_vertices(self, names): 
     for name in names: 
      self.add_vertex(name) 

    def __repr__(self): 
     return "Vertices: %s\nEdges: %s" % (self.vertices, self.edges) 

创建图表：

def createGraph(filename): 
    with open(filename) as f: 
     graph = Graph() 
     for line in f: 
      elements = line.strip().split() 
      graph.add_vertex(elements[0]) 
      for element in elements[2].split(","): 
       graph.add_edge(elements[0], element) 
    return graph 

运行它：

graph = createGraph('input.txt') 
print graph 

输出您的输入：

Vertices: [<Name:1 Edges:[0, 1, 2]>, <Name:2 Edges:[0, 3]>, <Name:3 Edges:[1, 3, 4]>, <Name:4 Edges:[2, 4]>] 
Edges: [(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)]