Python关联矩阵 - 如何移除顶点？

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

对于你问题的第2和第3个，可以用enumerate来代替手动增加计数器。比如，你的showGraph方法：

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

可以简化成：

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

Answer 2

这是你请求的 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()    

需要注意的是，如果你放弃从1开始的索引，改用Python的从0开始的索引，你可以稍微简化一下代码（比如从 *enumerate() 中去掉 , 1，以及从索引查找中去掉 -1）。

另外，你可能还想考虑用 dict 来表示数据。这种方式更适合稀疏结构，并且可以让代码变得更简单、更快。