Algorithm for finding failure cases in a communication "web"

Question

I am trying to enumerate a number of failure cases for a system I am working on to make writing test cases easier. Basically, I have a group of "points" which communicate with an arbitrary number of other points through data "paths". I want to come up with failure cases in the following three sets...

• Set 1 - Break each path individually (trivial)
• Set 2 - For each point P in the system, break paths so that P is completely cut off from the rest of the system (also trivial)
• Set 3 - For each point P in the system, break paths so that the system is divided into two groups of points (A and B, excluding point P) so that the only way to get from group A to group B is through point P (i.e., I want to force all data traffic in the system through point P to ensure that it can keep up). If this is not possible for a particular point, then it should be skipped.

Set 3 is what I am having trouble with. In practice, the systems I am dealing with are small and simple enough that I could probably "brute force" a solution (generally I have about 12 points, with each point connected to 1-4 other points). However, I would be interested in finding a more general algorithm for this type of problem, if anyone has any suggestions or ideas about where to start.

Answer 1

There are general algorithms for 'coloring' (with or without a u depending on whether you want UK or US articles) networks. However this is overkill for the relatively simple problem you describe.

Simply divide the nodes between two sets, then in pseudo-code:

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

Either use rand to chosse a broken link to reinstate, or systematically reinstate one at a time

Repeat for b (or structure your edges such that a break in one direction affects the other)

Answer 2

Here's some psuedocode, substituting the common graph theory terms of "nodes" for "points" and "edges" for "paths" assuming a path connects two points.

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

Unless I'm misunderstanding something, the problem seems relatively simple as long as you have a method of generating the subsets of nodes-{P}. This will test each partition [A,B] twice unless you put some other check in there.