從鄰接表中創建無向圖

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)]