生成随机字典并为关联图着色

Question

我想从一个包含 5 个元素的数组开始生成一个随机字典。该字典将代表一个平面图。我如何生成一个随机字典，它是一个平面图，其值和键是数组的 5 个元素？这是我试过的：

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}

这是它生成的图形的示例：

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

如您所见，问题在于它没有创建适当的邻接矩阵（3 与 1 相连但 1 不在其邻接矩阵中）你们中的一些人向我提出了一个已经问过的问题，但是这个问题的答案非常复杂，因为它会生成一个非常大的平面图，我在这里要做的是一个简单的代码，它生成一个有 5 个顶点的小平面图.请记住，始终可以使用 networkx 中的 checkplanarity 检查图形的平面性，更多关于 here，我需要解决的问题是矩阵的邻接性。

我这样做的原因是然后使用以下名为 coloring 的函数用四种颜色为生成的图形着色，而矩阵问题阻止我正确着色，因此相同的颜色永远不会接触。要使用创建的图形提供函数 coloring，我执行以下操作：

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])

要将创建的图形 d 提供给函数 coloring，我执行以下操作：

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

Answer 1

让我们用 numpy 来做这个。

让我们创建一个随机数在 0 到 9 之间的随机矩阵，大小为 nxn = 5x5
接下来，我们将矩阵与其转置求和以确保它是对称的
修正对角线 with np.fill_diagonal 以移除自环
定义一个条件connectivity，条件越大，随机图中的连接数越少。
最后把矩阵转成字典
情节。

import numpy as np
import networkx as nx

def random_graph(vertices, connectivity):
    #Creates random symmetric graph
    arr = np.random.randint(0,10,(vertices,vertices))
    sym = (arr+arr.T)
    
    #removing self loops with fixing diagonal
    np.fill_diagonal(sym,0)
    
    #connectivity of graph -> 0 for highest connections, 9 for least connections
    mat = (sym>connectivity).astype(int)
    
    #convert to dictionary
    G = {k:[i for i,j in enumerate(v) if j==1] for k,v in enumerate(mat)}
    return G

正在生成具有高连接度的图（连接度 = 0）-

G = random_graph(5, 0)
g = nx.Graph(G)
print(G)
nx.draw(g)

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

正在生成连接数较低的图（连接数 = 8）-

G = random_graph(5, 8)
g = nx.Graph(G)
print(G)
nx.draw(g)

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

Answer 2

对您的代码稍作修改，您就可以对称化您的图表：

import random
random.seed(0)

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

现在对称：

for node in d:
    for link_target in d[node]:
        d[link_target].add(node)

这样节点就不会连接到它们自己，就像在您的代码中一样。您还需要验证图形是否是平面的。

设置边数

如果您希望将边数固定为 k，您可以执行以下操作：

生成对角线为零的三角矩阵，使用零 (false) 和一 (true) 表示边之间的连通性。您可以通过随机洗牌 k 个和 N*(N-1)/2 个零并将它们分布到三角矩阵的 non-diagonal 个位置来实现。
将矩阵的转置添加到自身
将矩阵转换为您喜欢的字典格式。

注意：还是要确认图形是否是平面的

生成随机字典并为关联图着色

Generating a random dictionary and coloring associated graph

python

arrays

random

dictionary

graph

设置边数