ruby - 具有已知色数的图形生成器

Question

我已经将几种图形着色算法实现为一个类项目，我想测试和比较它们的性能。为此，我需要具有已知色数的测试图。

我曾预计这是一个非常普遍的要求，以便算法和/或库随时可用。结果我错了。经过相当广泛的搜索后，我找到的最好的是 paper from 1979 .¹ 在第 6 节中，描述了一种生成具有已知色数的图形的方法。在努力将其从数学转化为程序员之前，我想知道是否真的没有可用的实现来避免重新发明轮子。

---

¹ Leighton, F. T. (1979)。一种用于大型调度问题的图着色算法。 国家标准局研究杂志(第 489-506 页)。 http://doi.org/10.6028/jres.084.024

Answer 1

所以我不知道 ruby ，但是当我在看同一篇论文时遇到了这个问题并且也很困惑。我已经使用 link to playground 在 Rust ( petgraph ) 中实现了算法表示图形的库。

但基本思想是您要选择一些值:

• a:乘数(也称为因子)
• c:递增
• m:模数
• x[0]:一些种子或起始值

定义由递归关系定义的伪随机数生成器(特别是线性同余生成器 wikipedia):

x[i] = (x[i - 1] * a + c) % m

对于一些不错的属性，我们还需要满足条件的参数(Leighton 在论文中提到的第一步):

1. m 远大于n(节点数)
2. gcd(m, n) == k
3. gcd(m, c) == 1 或 m 和 c 互质
4. 对于任何素数p:如果m % p == 0 then (a-1) % p == 0<
5. 如果 m % 4 == 0 那么 (a-1) % 4 == 0

我相信这些标准使 Leighton 能够证明该程序有效，但我不确定。幸运的是，他在附录 C 中为 m、c、a 和 x[0] 提供了一些值。例如:

// Values taken from Leighton
let chromatic_number = 5;   // k
let modulus = 84_035;       // m
let increment = 6_859;      // c
let multiplier = 8_401;     // a
let mut x_i = vec![33_289]; // x[0]

之后，我们根据递归关系生成一个随机数向量x_i:

let num_rand_numbers = 100;
for i in (1..num_rand_numbers) {
    // x[i] = (x[i-1] * a + c) % m
    x_i.push((x_i[i - 1] * multiplier + increment) % modulus);
}

所以我们得到了随机数 x_i，但它们在区间 [0, m] 中，我们的节点在范围 [0 , n-1] 其中 m 比 n 大很多。所以创建一个向量 y_i 其中:

// Construct y_i in [0, n-1] such that y_i = x_i % n
let y_i = x_i.iter()  // Convert x_i to an iterator
             .map(|x| x % num_nodes) // y_i = x_i % n
             .collect::<Vec<_>>();   // convert iterator to vector

所以有很多工作只是为了有效地选择一些随机向量，但是一旦选择了它们，算法就会变成这样:

1. 用 num_nodes 个节点创建一个新的无向图。在我的测试中，Leighton 的方法产生了许多岛屿，其中一些节点完全无法从其他节点到达。所以在这里我将它们全部连接成一条线，这样我们就没有任何孤岛节点。

let mut graph = UnGraph::new_undirected();
let mut prev;
let mut curr = graph.add_node(Node {});

for n in 1..num_nodes {
    prev = curr;
    curr = graph.add_node(Node {});
    graph.add_edge(prev, curr, Edge {});
}

1. 缓存节点索引，这样我们就不必每次都查找它们

let node_indices = graph.node_indices().collect::<Vec<_>>();

现在将一个 h-clique 定义为一组完全连接到的节点彼此，这样每个节点都有 h-1 条边来自它。这对应于为该集团着色所需的 h 种颜色。

我们创建多个度数递减的派系:从度数高的派系开始，循环直到连接度数为 2 的派系。

let mut y_idx = 0;
// This for-loop takes the b-vector (which contains how many 2-cliques, 3-cliques, 4-cliques, ..., k-cliques there should be and converts it into multiple tuples like (number of cliques, size of those cliques)
'make_cliques: for (num_cliques, clique_degree) in b_vec.into_iter().zip((1..(k + 1)).into_iter()).rev() {
    if clique_degree <= 1 {
        break;
    }

对于我们要创建的每个大小为 clique_degree 的集团:

    for clique_idx in 0..num_cliques {
        // Create a clique with nodes indexed y_idx to y_idx+clique_degree
        for i in 0..clique_degree {
            for j in (i + 1)..clique_degree {

遍历随机选择的节点，并尝试将它们连接在一起

                let a = node_indices[y_i[y_idx + i]];
                let b = node_indices[y_i[y_idx + j]];

如果我们已经添加了这条边 => 不要再次添加

                if graph.contains_edge(a, b) {
                    continue;
                }

请注意，在我的测试中，Leighton 的方法会向节点添加边，即使它已经具有最大边数。所以在这里我检查是否有任何一个候选节点已经拥有最大数量的邻居，如果是，我不添加这条边。

                if graph.neighbors(b).count() == k || graph.neighbors(a).count() == k {
                    continue;
                }

现在我们知道它是一条有效边，实际添加它:

                graph.add_edge(a, b, Edge {});

如果我们已经达到最大边数 => 停止添加边

                if graph.edge_count() == num_edges {
                    print!("Have enough edges, exiting");
                    break 'make_cliques;
                }
            }
        }
        y_idx += clique_degree;
    }
}

希望对您有所帮助!也许有人可以将铁锈转化为 ruby 。完整的运行代码可在 playground 上获得。 .

示例输出 m=84035, n=10, k=5, c=6859, a=8401, b_vec: [0, 1, 1, 3, 6]

Link to Dotgraph visualisation

Values: m=84035, n=10, k=5, c=6859, a=8401, b_vec: [0, 1, 1, 3, 6]
Making 6 cliques of degree 5
Making 3 cliques of degree 4
Making 1 cliques of degree 3
Making 1 cliques of degree 2
Making 0 cliques of degree 1
Dotstring of graph:
graph {
    0 [ label = "Node" ]
    1 [ label = "Node" ]
    2 [ label = "Node" ]
    3 [ label = "Node" ]
    4 [ label = "Node" ]
    5 [ label = "Node" ]
    6 [ label = "Node" ]
    7 [ label = "Node" ]
    8 [ label = "Node" ]
    9 [ label = "Node" ]
    0 -- 1 [ ]
    1 -- 2 [ ]
    2 -- 3 [ ]
    3 -- 4 [ ]
    4 -- 5 [ ]
    5 -- 6 [ ]
    6 -- 7 [ ]
    7 -- 8 [ ]
    8 -- 9 [ ]
    9 -- 3 [ ]
    9 -- 7 [ ]
    9 -- 1 [ ]
    9 -- 0 [ ]
    3 -- 7 [ ]
    3 -- 1 [ ]
    7 -- 1 [ ]
    8 -- 2 [ ]
    8 -- 0 [ ]
    2 -- 0 [ ]
    4 -- 6 [ ]
    4 -- 0 [ ]
    5 -- 2 [ ]
    4 -- 8 [ ]
}