最小团覆盖问题：如何生成测试用例？

Question

最小团覆盖问题：如何生成测试用例？

algorithmgraph-theoryclique-problem

3

如何为最小团覆盖算法生成非平凡的测试用例？

换句话说，我想生成一个图，其中最小数量的团和每个节点分配到一个团的情况事先已知。

谢谢！

- MarcoM

1

我会从找到算法来检查解决方案与算法本身的输出开始。仔细观察可能会提供一些见解。 - undefined

这取决于你对“非平凡”一词的理解。最简单的团是由三个顶点组成的三角形。一个包含三个团且囊括所有顶点的图是一个由3个三角形组成的9个顶点的图。假设你想要比这更复杂的东西。但是，你想要什么呢？ - undefined

你能否对你正在探索的图的大小发表评论：顶点范围和边密度是多少？ - undefined

给个概念：100个顶点和几千条边 - undefined

2个回答

2

我在Rust中对团体发现做了很多工作。

总的来说，我发现当团体的大小大致相等时，寻找大小为k的覆盖是最困难的，所以在我的测试中，我生成了这样的团体。基本的方法是：

输入：

number of vertices (call this n), 
number of cliques in the cover (call this k), 
and the fraction of potential edges that exist (call this p).

步骤：

Generate k approximately equal sized cliques (approximate in that some will be larger by 1 vertex if n%k != 0)
Calculate the remaining edges: p*choose(n, 2) - (edges used up by k cliques)
Randomly assign remaining edges to pairs of nonadjacent vertices.

这是我用来生成具有指定数量团的随机图的Rust代码：

fn get_random_graph_with_k_cliques(
  num_vertices: usize,
  cliques_ct: usize,
  edge_probability: f64,
) -> Graph {
  if cliques_ct == 0 {
    return get_random_graph(num_vertices, edge_probability);
  }

  let mut ret_graph = Graph::new(num_vertices);
  let mut edge_candidates_remaining = num_vertices * (num_vertices - 1) / 2;
  let mut edges_remaining = (edge_candidates_remaining as f64 * edge_probability) as usize;

  let reserved_edges = cliques_ct * (num_vertices / cliques_ct) * (num_vertices / cliques_ct - 1)
    / 2
    + (num_vertices % cliques_ct) * (num_vertices / cliques_ct);
  edge_candidates_remaining -= reserved_edges;
  if reserved_edges > edges_remaining {
    edges_remaining = 0;
  } else {
    edges_remaining -= reserved_edges;
  }

  for i in 0..(ret_graph.size - 1) {
    for j in (i + 1)..(ret_graph.size) {
      if i % cliques_ct == j % cliques_ct {
        ret_graph.vertices[i].neighbors_bv.set(j, true);
        ret_graph.vertices[j].neighbors_bv.set(i, true);
      } else if fastrand::f64() < (edges_remaining as f64) / (edge_candidates_remaining as f64) {
        edges_remaining -= 1;
        ret_graph.vertices[i].neighbors_bv.set(j, true);
        ret_graph.vertices[j].neighbors_bv.set(i, true);
      }

      if i % cliques_ct != j % cliques_ct {
        edge_candidates_remaining -= 1;
      }
    }
  }
  for i in 0..(ret_graph.size) {
    if ret_graph.vertices[i].neighbors_bv.any() {
      ret_graph.vertices[i].has_neighbors = true;
    }
  }
  ret_graph.conform_cliques_to_vertices();
  ret_graph
}

这是模拟一个具有已知团覆盖和已知边比率（边数/潜在边数==不同顶点对数）的图。

它创建了k个相等大小的团，然后添加随机边以达到所需的总边数。

您可以忽略conform_cliques_to_vertices()这一行。对于我的目的，当一个顶点被添加到一个团中时，我将其“合并”，将该团视为一个顶点，并取出团之间的边的交集，但您的需求可能不同。

虽然这样生成了一个具有大小为k的已知团覆盖的图，但并不能保证不存在更好的团覆盖，并且在随机性的影响下，特别是在较大的边概率情况下，可能存在更好的团覆盖。

如果要实际寻找团，我建议研究迭代贪婪和禁忌方法。有一篇总结了几种不同方法的好论文：《用于图着色的局部搜索方法综述》，作者是Galinier和Hertz。

- Dave

1

我要补充一点，似乎在找到图中的团伙时存在着一种“困难的障碍”，这与图中的团伙数量和额外边的数量有关。如果额外边太少，找到所有的团伙非常容易。如果额外边太多，就会有很多解决方案，并且很容易找到其中一个（也可能通过随机性找到一个比生成的覆盖方案中团伙更少的解决方案）。在这两者之间，存在一个区域，我尝试的随机技术通常无法重新创建已知的最佳覆盖方案。 - undefined

1

这会生成k个相同大小的团，然后添加随机边以获得所需的总边数。这似乎可能会在两个团之间添加足够的边，使它们变成一个团，从而得到错误的交集数量。 - undefined

1

@ravenspoint 是的。如果原帖作者在意的话，可以通过坚持在每对团体之间选择一个随机的非边缘边来轻松避免这个问题。在处理完团体后，更难避免的是在图中仍然密集的情况下（即团体之间的边缘密集），创建足够多的全新团体，以便存在一个替代的、更小的覆盖。 - undefined

1

例如，对于你的解决方案来说，找到团是很容易的，因为几乎每个顶点的几乎每个邻居都在同一个团中。迭代贪婪算法只需要很少的迭代就能找到这些团。也就是说，虽然你的方法能够完美地生成具有已知最小团覆盖的图，但我不认为它对于测试 OP 的团检测算法会有用。 - undefined

1

好主意。我会在团队成员之间增加额外的联系，但不会减少交集数量。 - undefined

显示剩余12条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ravenspoint · Accepted Answer

算法

输入I，即交叉数（即覆盖图中每个顶点所需的最小团数）。
输入ni个数字，表示I个团中每个团的顶点数。每个数字必须大于等于3。
构建I个顶点{ VI }，并将它们连接成一个环，使得每个顶点与其他两个顶点相连。
循环i，遍历I个团：
- 构建ni - 1个顶点{ ni }
- 将{ ni }中的每个顶点与{ ni }中的其他顶点以及{ VI }中的第i个顶点相连
随机化顶点和连接的顺序（以隐藏构造过程）

C++实现

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "../PathFinder/src/cGraph.h"   // https://github.com/JamesBremner/PathFinder

int intersectionNumber;
std::vector<int> vCliqueCount;
raven::graph::cGraph g;

void input()
{
    std::cout << "Intersection Number: ";
    std::cin >> intersectionNumber;
    std::cout << "clique counts:\n";
    for (int i = 0; i < intersectionNumber; i++)
    {
        int cc;
        std::cout << "#" << i+1 << ": ";
        std::cin >> cc;
        vCliqueCount.push_back(cc);
    }
}

void generate()
{
    std::string previs;
    std::vector<std::string> vsclique;
    for (int i = 0; i < intersectionNumber; i++)
    {
        auto is = std::to_string(i);
        auto is0 = is+"_0";
        if (i > 0)
            g.add(is0, previs);
        previs = is0;

        vsclique.clear();
        for( int c1 = 0; c1 < vCliqueCount[i]-1; c1++ ) {
            vsclique.push_back(is+"_"+std::to_string(c1+1));
            g.add( is0,vsclique.back());
        }
        for( int c1 = 0; c1 < vsclique.size(); c1++ )
        {

            for( int c2 = c1+1; c2 < vsclique.size(); c2++ )
                g.add(vsclique[c1],vsclique[c2]);
        }
    }
    if( intersectionNumber>2)
        g.add("0_0", previs);

}

void output()
{
    std::ofstream ifs("gengraph.txt");
    if( ! ifs.is_open())
        throw std::runtime_error("Cannot open output");

    auto vl = g.edgeList();

    // this outputs vertex names that reveal the clique each vertex belongs to
    // for( auto& l : vl )
    // {
    //     ifs << "l " << g.userName(l.first)
    //          <<" "<<g.userName(l.second)<< "\n";
    // }

    // this outputs obscured graph construction
    std::random_shuffle( vl.begin(),vl.end());
    std::map<int,int>  obvertex;
    int kv = 0;
    for( auto& l : vl )
    {
        obvertex.insert(std::make_pair(l.first,kv++));
        obvertex.insert(std::make_pair(l.second,kv++));
        ifs << std::to_string(obvertex.find(l.first)->second)
             <<" "<<std::to_string(obvertex.find(l.second)->second)<< "\n";
    }

}

main()
{
    input();
    generate();
    output();

    return 0;
}

测试运行

输入

Intersection Number: 3
clique counts:
#1: 3
#2: 4
#3: 5

输出（已隐藏）

输出（vizgraph布局）

Windows版本：https://github.com/JamesBremner/genclique/releases/tag/v1.0.0

额外的边

为了进一步混淆团建设，我们可以在不降低交集数量的情况下，在不同团的顶点之间添加边。(@Dave的建议)

每个团中的顶点都有一个索引号。顶点标签的格式如下："X_Y"，其中X是团的索引，Y是团中的顶点索引，所有索引都从零开始计数。第零个顶点是在初始构建过程中与其他两个团的第零个顶点相连的顶点。现在，我们在其他顶点之间添加边，除了索引为0（已经与其他团相连）和1（为了防止交集数量减少）的顶点与其他团的顶点之间。

如果您查看GitHub存储库中的代码输出的未混淆图，可能更容易理解正在发生的情况。

以下是代码：

void extraEdges()
{
    // loop over all cliques
    for (int c1 = 0; c1 < intersectionNumber; c1++)
    {
        auto is = std::to_string(c1) + "_1";

        // loop over other cliques, not already connected to c1
        for (
            int c2 = c1 + 1;
            c2 < intersectionNumber;
            c2++)
        {
            // loop over vertices on other clique, except numbers 0 and 1
            for (int v = 2; v < vCliqueCount[c2]; v++)
            {
                auto sv2 = std::to_string(c2) + "_" + std::to_string(v);
                g.add(is, sv2);
            }
        }
    }
}

这是最简单的构造布局，没有遮挡。

2 3 3

这是一个更大的构造布局（有遮挡）。

3 3 4 5

完整的代码，包括额外的边和vizgraph布局，请参见https://github.com/JamesBremner/genclique。