Проверьте правильность раскраски случайного графа (Python) - PullRequest
Новая
       51

Проверьте правильность раскраски случайного графа (Python)

0 голосов
/ 20 января 2019

Так что я пытаюсь использовать другой подход к раскраске графа, в основном я назначаю случайные цвета узлам графа, и я хочу после назначения этих цветов проверить правильность окраски (нет другими словами, проходя через узлы и соответствующие цвета, и убедитесь, что соседние узлы не имеют такого цвета.

Вот что я сделал до сих пор: 

def approx_color(graph):
      colors = [1,2,3,4,5,6,7,8,9]
      xr = random.randint(0, len(graph.nodes))
      s_c = []
      for i in range(len(graph.nodes)):
          s_c.append(random.choice(colors))
      colored = dict(zip(graph.nodes,s_c))
      print(colored)

РЕДАКТИРОВАТЬ:

Переменная «graph» - это граф, сгенерированный библиотекой networkx, а graph.nodes() graph.edges() - список узлов и ребер графа

1 Ответ

0 голосов
/ 20 января 2019

Для первой части вы можете напрямую использовать random.choices () 

def approx_color(graph):
    colors = [1,2,3,4,5,6,7,8,9]
    s_c = random.choices(colors, k=graph.order())
    colored = dict(zip(graph.nodes(), s_c))

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

for u in graph.nodes():
    for v in graph.neighbors(u):
        if colored[u] == colored[v]:
            return False
return True
...