Machen Sie ungerichteten Graphen aus der Adjazenzliste

Question

Ich versuche, einen ungerichteten Graphen aus einer Adjazenzliste zu machen, um den Karger's Min Cut Algorithmus zu üben. Hier finden Sie meinen Code

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) 

die Adjazenzliste Angenommen ist wie mit den Eckpunkten durch ganze Zahlen dargestellt folgt

1 -> 2,3,4 
2 -> 1,3 
3 -> 1,2,4 
4 -> 1,3 

Insgesamt wird dieser Graph fünf Kanten haben, so dass die Länge der Liste geführt Indizes Kanten Ein Scheitelpunkt ist mit nicht mehr als 5 Länge verbunden.

Zum Beispiel erwarte ich, dass der Eckpunkt '2' Indizes von nur zwei Kanten hat, d. H. Kanten mit den Eckpunkten 1 und 3. Stattdessen bekomme ich [0, 1, 2, 3, 0, 2, 1, 3]. Ich brauche Hilfe, um herauszufinden, was schief läuft.

Answer 1

Der erste Fehler kommt von der Vertex-Init. Wenn Python eine Liste als Standardargument übergibt, instanziiert es sie einmal und teilt diese Instanz mit allen zukünftigen Instanzen von Vertex. Führen Sie None aus und verwenden Sie eine lokale Liste, wenn keine Liste angegeben ist.

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

Im createGraph Verfahren, wenn der Scheitelpunkt bereits in der Grafik vorhanden ist, müssen Sie es verwenden. Siehe die hinzugefügte else: newVert = ... Sie scheinen auch ein Problem mit der Ligne Spaltung zu haben. Siehe die Iteration über 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) 

Als Randbemerkung, würde ich versuchen, einen dict zu verwenden, um die Ecken zu speichern (und Kanten) und die Lookup zu tun. wird oft verwendet, und Sie können viele Objekte für nichts erstellen.

Answer 2

Ich würde empfehlen, einen Blick auf Dict, OrderedDict, Linked-List-basierte Grafik-Implementierungen zu werfen. Sie sind weitaus effektiver als Listen und Indizes. Um Sie Code Arbeit machen Sie Folgendes tun:

Veränderung ein Vertex Problem in vorherigen Antwort beschrieben zu vermeiden:

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

die Grafik etwas Arbeit tun lassen:

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) 

Create Graph :

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 

Run it:

012.351.

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

Ausgang für Ihre Eingabe:

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