Алгоритм поиска случаев отказа в коммуникационной «сети»

Question

Я пытаюсь перечислить несколько случаев сбоев для системы, над которой я работаю, чтобы упростить написание контрольных примеров. По сути, у меня есть группа «точек», которые связываются с произвольным числом других точек через «пути» данных. Я хочу придумать случаи сбоев в следующих трех сетах ...

• Набор 1 - Разбить каждый путь индивидуально (тривиально)
• Набор 2 - Для каждой точки P в системе разделите пути так, чтобы P полностью отрезался от остальной части системы (также тривиально)
• Набор 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

Существуют общие алгоритмы «раскраски» (с или без u в зависимости от того, хотите ли вы статьи в Великобритании или США). Однако это является излишним для относительно простой проблемы, которую вы описываете.

Просто разделите узлы между двумя наборами, затем в псевдокоде:

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 (или структурируйте края так, чтобы разрыв в одном направлении влиял на другое)