用于在通信“网络”中查找故障案例的算法

Question

我试图列举我正在开发的系统的一些失败案例，以便更轻松地编写测试用例。基本上，我有一组“点”，它们通过数据“路径”与任意数量的其他点进行通信。我想提出以下三组中的失败案例...

• 第 1 组 - 单独断开每条路径（微不足道）
• 第 2 组 - 对于系统中的每个点 P，断开路径，以便 P 与其余点完全切断系统（也是微不足道的）
• Set 3 - 对于系统中的每个点 P，断开路径，使系统分为两组点（A 和 B，不包括点 P），以便从 A 组到B组是通过P点（即我想强制系统中的所有数据流量通过P点以确保它能够跟上）。如果这对于特定点来说是不可能的，那么应该跳过它。

第 3 组是我遇到的麻烦。在实践中，我正在处理的系统足够小且简单，我可能可以“强力”找到一个解决方案（通常我有大约 12 个点，每个点连接到 1-4 个其他点）。但是，如果有人对从哪里开始有任何建议或想法，我有兴趣为此类问题找到更通用的算法。

Answer 1

这是一些伪代码，用常见的图论术语“节点”替换“点”和“假设一条路径连接两点，则“路径”的“边”。

for each P in nodes:
    for each subset A in nodes - {P}:
        B = nodes - A - {P}
        for each node in A:
            for each edge out of A:
                if the other end is in B:
                    break edge
        run test
        replace edges if necessary 

除非我误解了什么，否则只要你有一种生成节点子集 - {P} 的方法，问题看起来就相对简单。这将测试每个分区 [A,B] 两次，除非您在那里进行其他检查。

Answer 2

有一些用于“着色”网络的通用算法（有或没有 au，具体取决于您想要英国还是美国的文章）网络。然而，对于您描述的相对简单的问题来说，这太过分了。

只需将节点划分为两组，然后使用伪代码：

foreach Node n in a.Nodes
     foreach Edge e in n.Edges
         if e.otherEnd in b then 
               e.break()
               broken.add(e)

broken.get(rand(broken.size()).reinstate()

要么使用 rand 选择要恢复的断开链接，要么一次系统地恢复一个

重复 b （或构建边缘，使一个方向的中断影响另一个方向）