Сделать неориентированный граф из списка смежности

Question

Я пытаюсь сделать неориентированный граф из списка смежности, чтобы применить алгоритм Min Cut от 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. При передаче списка в качестве аргумента по умолчанию Python запускает его один раз и передает этот экземпляр всем будущим экземплярам Vertex. Пропустить None и использовать локальный список, если список не указан.

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) 

Как примечание стороны, я хотел бы попробовать использовать Dict для хранения вершин (и ребер) и сделать поиск. List.index используется много, и вы можете создать много объектов для ничего.

Answer 2

Я бы порекомендовал взглянуть на Dict, OrderedDict, связанные графические реализации на основе Linked List. Они намного эффективнее, чем списки и индексы. Для того, чтобы вам код работу, которую вы можете сделать следующее:

Измени Vertex, чтобы избежать проблемы, описанной в предыдущем ответе:

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