: Матрица инцидентности Python - Как удалить 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" в методах? Возможно, это может быть что-то еще, чтобы написать - но как?

Edit:

Теперь я видел, как удалить вершину. Я только что удалил столбцы, где эта вершина имеет 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, вы можете немного упростить код (удалив , 1 из * enumerate () и удалив -1 из индексированных поисков.

Кроме того, вы можете рассмотреть другое представление с использованием dict . Это больше подходит для разреженных структур и может несколько упростить / ускорить код.

Answer 2

Ответ на ваш вопрос 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