python 贪心着色

Question

我制作了一个脚本，我在其中生成了一个图表，然后用四种颜色为它着色。然后使用 networkx 绘制着色图。该程序不应将两种颜色彼此相邻，但是当您运行程序时，您可以看到它确实如此。我真的不知道问题出在哪里，我最好的猜测是我将生成的图 d 错误地传递给函数 coloring 这是我的代码：

import networkx as nx
import matplotlib.pyplot as plt
from random import sample,  randrange

#function that colors graph with four colors
def coloring(adj, V):
     
    result = [-1] * V
 
   
    result[0] = 0
 
 
    available = [False] * V
 
    
    for u in range(1, V):
         
     
        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = True
        cr = 0
        while cr < V:
            if (available[cr] == False):
                break
             
            cr += 1
             
        result[u] = cr

        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = False

    for u in range(V):
        print("Vertex", u, " --->  Color", result[u])
    global options

    options = {
        'node_color': result,
        'node_size': 4,
        'width': .1,
    }


#creating random graph
q = [0,1,2,3,4]
d = {i: sample([j for j in q if i != j], randrange(1, len(q) -1)) for i in q}

coloring([node for node in d.values()], 5)

G = nx.Graph()


#adding graph d to networkx 
def passToNx():
    for k in d:
        G.add_node(k)
        for j in d[k]:
            G.add_edge(k, j)


passToNx()

#drawing graph
subax1 = plt.subplot(121)
nx.draw(G, **options)
plt.show()

Answer 1

您的着色代码非常好。您的随机图形生成器似乎有问题：

d = {i: sample([j for j in q if i != j], randrange(1, len(q) -1)) for i in q}

以下是上述代码生成的图表示例：

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

如您所见，它没有创建适当的邻接矩阵（3 与 1 相连，但 1 不在其邻接矩阵中）。

解决该问题的一种方法是编写适当的图形生成器。我的解决方案在保持相同生成器的同时更改了着色函数：

def coloring(adj, V):
    result = [-1] * V
    result[0] = 0
    available = [False] * V
    # add values to adj matrices
    for y in range(0, V):
        for x in adj[y]:
            if y not in adj[x]:
                adj[x].append(y)

    for u in range(1, V):
        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = True
        cr = 0
        while cr < V:
            if (available[cr] == False):
                break

            cr += 1

        result[u] = cr

        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = False

    for u in range(V):
        print("Vertex", u, " --->  Color", result[u])
    global options

    options = {
        'node_color': result,
        'node_size': 100,
        'width': 0.1,
    }

此外，您必须更改图表的颜色，因为它不会按顺序分配颜色。因此手动遍历图形的所有节点以对节点着色。

q = [0,1,2,3,4]
d = {0: [1], 1: [4, 3], 2: [4], 3: [4], 4: [0, 2]}

coloring([node for node in d.values()], 5)

G = nx.Graph()

color = [x for x in options['node_color']]
color_use = [x for x in color]

#adding graph d to networkx 
def passToNx():
    for k in d:
        G.add_node(k)
        for j in d[k]:
            G.add_edge(k, j)


passToNx()

# add color to nodes
for i, node in enumerate(G):
    color_use[node] = color[i]

#drawing graph
subax1 = plt.subplot(121)
nx.draw(G, node_color= color_use, with_labels = True)
plt.show()

python 贪心着色

python greedy coloring

python

arrays

matplotlib

graph

graph-coloring