python - :Python incidence matrix - How to remove Vertex?

Question

这是我的代码:

class incidenceMatrix:
    def __init__(self, vertexNumber):
        self.matrix = []
        for k in range(0, vertexNumber):
            self.matrix += [[]]
            #print self.matrix

    def showGraph(self):
        i = 1
        for row in self.matrix:
            print i, row
            i += 1

    def isEdge(self, v1, v2):
        i = 1
        for row in self.matrix:
            if i == v1:
                r1 = row
            if i == v2:
                r2 = row
            i += 1
        print r1, r2
        for x in range(len(r1)):
            if r1[x] == r2[x] and r1[x] + r2[x] > 0:
                return True
        return False

    def addEdge(self, v1, v2):
        i = 1
        for row in self.matrix:
            if i == v1:
                row.append(1)
            elif i == v2:
                row.append(1)
            else:
                row.append(0)
            i += 1

    def removeEdge(self, v1, v2):
        i = 1
        for row in self.matrix:
            if i == v1:
                r1 = row
            if i == v2:
                r2 = row
            i += 1
        for x in range(len(r1)):
            if r1[x] == r2[x] and r1[x] + r2[x] > 0:
                col = x
                r1[x] = 0
                r2[x] = 0
        for row in self.matrix:
            if i == v1:
                row = r1
            if i == v2:
                row = r2
            i += 1
        for row in self.matrix:
            row[col] = 'X'
            row.remove('X')

def removeVertex(self, id):
    pass

if __name__ == '__main__':
    GrafIM = incidenceMatrix(5) #verticesNumber
    GrafIM.addEdge(2,3)
    GrafIM.addEdge(1,3)
    GrafIM.addEdge(2,1)
    GrafIM.addEdge(5,2)
    print GrafIM.isEdge(2,4)
    GrafIM.showGraph()
    print "-------"
    GrafIM.removeEdge(2,5)
    GrafIM.showGraph()

这是关联矩阵 我有几个问题:

1) 如何移除顶点 - 方法？

2)如何让代码更加Python风格？参见问题3)

3)我必须在方法中使用“i”增量吗？也许这可以写成别的东西 - 但怎么写呢？

编辑:

我现在看到了如何删除顶点。 我刚刚删除了该顶点为 1 的列。

但一直在等待有关代码质量的建议

Answer 1

这是您请求的 removeVertex() 方法。此外，代码还使用 any()、enumerate() 和 zip() 进行了一些收紧:

class incidenceMatrix:
    def __init__(self, vertexNumber):
        self.matrix = [[] for k in range(vertexNumber)]

    def showGraph(self):
        for i, row in enumerate(self.matrix, 1):
            print i, row

    def isEdge(self, v1, v2):
        return any(x and y for x, y in zip(self.matrix[v1-1], self.matrix[v2-1]))

    def addEdge(self, v1, v2):
        for i, row in enumerate(self.matrix, 1):
            row.append(int(v1==i or v2==i))

    def removeEdge(self, v1, v2):
        num_edges = len(self.matrix[0])
        for j in range(num_edges):
            if self.matrix[v1-1][j] and self.matrix[v2-1][j]:
                for row in self.matrix:
                    del row[j]
                return
        raise Exception('Edge(%d, %d) not found' % (v1, v2))

    def removeVertex(self, v):
        targetrow = self.matrix.pop(v-1)    # fetch and delete the target vertex
        for col, selector in reversed(list(enumerate(targetrow))):
            if selector:                    # find columns that had an edge on the target row
                for row in self.matrix:
                    del row[col]            # remove that column (because the edge is gone)

if __name__ == '__main__':
    GrafIM = incidenceMatrix(5) #verticesNumber
    GrafIM.addEdge(2,3)
    GrafIM.addEdge(1,3)
    GrafIM.addEdge(2,1)
    GrafIM.addEdge(5,2)
    print GrafIM.isEdge(2,4)
    for pair in [(2,3), (1,3), (2,1), (5,2)]:
        print GrafIM.isEdge(*pair)
    GrafIM.showGraph()
    print "-------"
    GrafIM.removeEdge(2,5)
    GrafIM.showGraph()
    print "-------"
    GrafIM.removeVertex(2)
    GrafIM.showGraph()    

请注意，如果您放弃从一开始的索引，转而使用 Python 从零开始的索引，则可以稍微简化代码(从 *enumerate() 中删除 , 1 并删除 -1 来自索引查找。

此外，您可能需要考虑使用字典的不同表示形式。这更适合稀疏结构，并且可以在一定程度上简化/加速代码。