从邻接列表中创建无向图

我试图从邻接列表中创建一个无向图来练习Karger的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] . 我需要帮助来弄清楚出了什么问题 .

回答(2)

3 years ago

第一个错误来自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)

作为旁注,我会尝试使用dict来存储顶点(和边)并进行查找 . List.index 使用了很多,你可以创造很多物品 .

3 years ago

我建议看看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)]