Раскраска вершин питоном - Хроматическое число X (G) - PullRequest
Новая
       47

Раскраска вершин питоном - Хроматическое число X (G)

2 голосов
/ 21 марта 2012

Я пытаюсь написать небольшой код на python, чтобы раскрасить вершины графа и посчитать количество используемых цветов, чтобы никакие две соединенные вершины не имели одинаковый цвет.это мой код, и я не знаю, что с ним не так, любая помощь w?это не домашняя работа! 

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()

colors = ['Red', 'Blue', 'Green', 'Yellow',  'Black','Pink','Orange','White','Gray','Purpul','Brown','Navy']

G.nodes = [1,2,3,4,5]
G.edges= [{1,5},{1,3},{1,2},{1,4},{4,5}]
colors_of_nodes={}

def coloring(node, color):
   for neighbor in G.edges:
       color_of_neighbor = colors_of_nodes(neighbor)
       if color_of_neighbor == color:
          return False

   return True

def get_color_for_node(node):
    for color in colors:
       if coloring(node, color):
          return color

def main():
    for node in G.nodes:
        colors_of_nodes[node] = get_color_for_node(node)

    print colors_of_nodes


main()

Ответы [ 2 ]

3 голосов
/ 26 марта 2012

Несколько ошибок в этом коде:

  1. небольшая орфографическая ошибка Purpul -> Purple
  2. Синтаксическая ошибка: colors_of_nodes словарь, поэтому он не вызываетсякак функция.поэтому colors_of_nodes(neighbor) потерпит неудачу.Вы можете индексировать словарь двумя способами colors_of_nodes[node] или colors_of_nodes.get(node, default_value_if_node_is_not_a_key).Вы хотите сделать второе.
  3. Логическая ошибка: для соседа установлено значение ребра, а не узел.Вы хотите переключаться между узлами, которые являются соседями или определенным узлом.К счастью, у networkx есть простая функция: G.neighbors(node).Кроме того, ребро - это set, которое не может быть хешируемым, поэтому не может быть словарным ключом.
  4. Семантическая ошибка: вы не использовали правильную семантику для создания и доступа к графу networkx.Посмотрите на веб-сайт для сетиx .G.add_nodes_from([1,2,3,4,5]), G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(4,5)]), G.nodes()

Ниже приведен отредактированный код в рабочем формате.

author = 'brent' 

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()

colors = ['Red', 'Blue', 'Green', 'Yellow',  'Black', 'Pink', 'Orange', 'White', 'Gray', 'Purple', 'Brown', 'Navy']

G.add_nodes_from([1,2,3,4,5])
G.add_edges_from([(1,5),(1,3),(1,2),(1,4),(4,5)])
colors_of_nodes={}


def coloring(node, color):
   for neighbor in G.neighbors(node):
       color_of_neighbor = colors_of_nodes.get(neighbor, None)
       if color_of_neighbor == color:
          return False

   return True

def get_color_for_node(node):
    for color in colors:
       if coloring(node, color):
          return color

def main():
    for node in G.nodes():
        colors_of_nodes[node] = get_color_for_node(node)

    print colors_of_nodes


main()

Обратите внимание, что это жадная техника для раскрашивания графа и не обязательно дает вам оптимальную раскраску графа.

0 голосов
/ 21 марта 2012

Вы должны опубликовать ошибки, которые вы получаете, что вы ожидаете и что на самом деле происходит.

Минимально, это: 

color_of_neighbor = colors_of_nodes(neighbor)

Возникнет ошибка TypeError: 'dict' object is not callable.

...