Algorithme de recherche des cas de défaillance dans une "toile" de communication

Question

J'essaie d'énumérer un certain nombre de cas de défaillance pour un système sur lequel je travaille afin de faciliter l'écriture des cas de test. En gros, j'ai un groupe de "points" qui communiquent avec un nombre arbitraire d'autres points par le biais de "chemins" de données. Je veux trouver des cas de défaillance dans les trois ensembles suivants...

• Ensemble 1 - Cassez chaque chemin individuellement (trivial)
• Ensemble 2 - Pour chaque point P du système, briser les chemins de façon à ce que P soit complètement coupé du reste du système (également trivial)
• Ensemble 3 - Pour chaque point P du système, interrompre les chemins de sorte que le système soit divisé en deux groupes de points (A et B, à l'exclusion du point P), de sorte que le seul moyen d'aller du groupe A au groupe B soit de passer par le point P (c'est-à-dire que je veux forcer tout le trafic de données dans le système à passer par le point P afin de m'assurer qu'il peut suivre le rythme). Si cela n'est pas possible pour un point particulier, il faut l'ignorer.

C'est la série 3 qui me pose problème. En pratique, les systèmes auxquels j'ai affaire sont suffisamment petits et simples pour que je puisse probablement trouver une solution par "force brute" (en général, j'ai environ 12 points, chaque point étant relié à 1 à 4 autres points). Cependant, j'aimerais trouver un algorithme plus général pour ce type de problème, si quelqu'un a des suggestions ou des idées sur la façon de commencer.

Answer 1

Il existe des algorithmes généraux pour "colorer" (avec ou sans u selon que vous souhaitez des articles britanniques ou américains) les réseaux. Cependant, ces algorithmes sont excessifs pour le problème relativement simple que vous décrivez.

Il suffit de diviser les nœuds en deux ensembles, puis en 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()

Soit vous utilisez rand pour choisir un lien cassé à rétablir, soit vous en rétablissez systématiquement un à la fois.

Répétez pour b (ou structurez vos bords de manière à ce qu'une rupture dans une direction affecte l'autre).

Answer 2

Voici un peu de psuedocode, en remplaçant le code commun théorie des graphes en termes de "nœuds" pour les "points" et d'"arêtes" pour les "chemins", en supposant qu'un chemin relie deux 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

Sauf erreur de ma part, le problème semble relativement simple tant que l'on dispose d'une méthode pour générer les sous-ensembles de nœuds-{P}. Cela testera chaque partition [A,B] deux fois à moins que vous n'y mettiez une autre vérification.