Матрица смежности python (раскраска графа) - PullRequest
Новая
       81

Матрица смежности python (раскраска графа)

0 голосов
/ 08 декабря 2018

Я пытаюсь создать из следующего примера графа матрицу смежности, где, если существует, ребро между 2 узлами будет истинным, но если оно не существует ложным.

graph (5:1-2,1-3,1-4,1-5,2-3,3-4,4-5)

Код выглядит так: 

for x in range(self.n_nodes):
            matriu.append([])
            for y in range(n_colors):
                matriu[x].append(color)

где self.n_nodes - это список [1,2,3,4,5], matriu - это матрица, color - это логическое значение, инициализированное в false, а n_colors - это количество цветов (в данном случае 5).Матрица после этого кода выглядит следующим образом: 

[[False, False, False, False, False], 
[False, False, False, False, False], 
[False, False, False, False, False], 
[False, False, False, False, False], 
[False, False, False, False, False]]

Также у меня есть словарь со следующим содержимым: 

{1: [4, 2, 5, 3], 2: [3, 1], 3: [4, 2, 1], 4: [3, 1, 5], 5: [4, 1]}

, где ключ - это узел, а значение - это массив сузлы, которые существуют ребром.

Как я могу изменить матрицу (где строки являются узлами, а столбцы окрашены), чтобы иметь только один цвет по узлу, и если у узла есть ребро с другим узлом, цветдругой узел другого цвета.

Цель состоит в том, чтобы получить такую ​​матрицу: 

[[True, False, False, False, False], 
 [False, False, True, False, False], 
 [False, False, False, True, False], 
 [False, True, False, False, False], 
 [False, False, False, False, True]]
...