Даже после вашего второго редактирования я все еще не уверен, какова ваша цель на самом деле. Этому мешает ваш выбор терминологии. SCC, поскольку большинство людей подразумевают, что они являются максимальными наборами вершин, которые все достижимы друг от друга, и какие пути могут возникать просто не имеет значения.
Кто-нибудь знает способ найти SCC в SCC?
По обычным определениям, в SCC нет такой вещи, как SCC, потому что SCC максимален.
Вы ищете что-то еще: вы начинаете с подключенного графа и хотите найти определенные наборы ребер, которые вы не охарактеризовали. Я сильно подозреваю, что если вы четко охарактеризуете то, что хотите, алгоритм потерпит неудачу.
Мое первое предположение состояло в том, что для данного связного графа вам нужны множества ребер всех возможных комбинаций всех путей, соединяющих каждую пару. Если это так, то простой способ сделать это: для каждой пары найти все пути, затем найти все комбинации и устранить дубликаты. Однако при этом генерируется больше наборов, чем указано в вашем примере, поскольку использование всех ребер, безусловно, возможно.
Вместо этого, кажется, вы хотите, чтобы все минимальные наборы ребер все еще позволяли исходным вершинам оставаться SCC. В этом случае каждый элемент набора мощности исходного набора ребер представляет возможного кандидата, и вы хотите, чтобы все кандидаты были связаны с графом, но без надлежащего подмножества, которое все еще подключено.
Это дает простой алгоритм обхода этой решетки множеств и проверки этого условия. Проверить, подключен ли график, просто, как удалить или добавить ребра. Тем не менее, похожие графы имеют в основном одинаковую структуру, поэтому вы захотите использовать то, что можете из предыдущих задач.
Некоторые ссылки, которые могут помочь:
Особенно с точки зрения связи глобальной информации графа с локальной информацией о ребрах и вершинах.
Ваш начальный граф G имеет множество вершин V и ребер E и является сильно связным.
Цель состоит в том, чтобы вывести все «минимальные» наборы ребер E 'так, чтобы удаление любого ребра из E разбивало график на несколько SCC. Мы можем сделать это путем поиска всех возможных наборов ребер.
Прямо это:
for E' in powerset(E):
if (V, E') strongly connected:
for e in E':
if (V, E' - e) strongly connected:
try next E' # Not minimal
add G' = (V, E') to list of minimal subsets.
Однако это невероятно расточительно: очевидно, не связанные графики
проверено, и связность каждого графа проверена много раз.
Мы можем исключить первое путем поиска возможных ребер
в гораздо более хорошем порядке, расположение этих ребер в решетке. каждый
у ребра есть «прямые потомки», заданные этим ребром за вычетом одного ребра.
Как только мы столкнемся с графиком, который не является SCC, нам не нужно проверять
его подмножества, поскольку они также не могут быть SCC. Самый простой способ выразить
это как график поиска. Хотя поиск в глубину часто
путь, так как он использует меньше памяти, я собираюсь сначала выбрать ширину
поиск, потому что в дальнейшем мы будем использовать порядок обхода. (Глубина
первый поиск изменяет очередь в стек).
push starting node on queue
while queue not empty:
pop node from queue
for c in suitable children, not on queue:
push c on queue
deal with node
Часть «не в очереди» имеет решающее значение, иначе каждый узел может быть посещен
много раз. Это превращает наш алгоритм в:
push E on queue
while queue not empty:
pop E' from queue
if (V, E') strongly connected:
minimal = true
for e in E':
if (V, E' - e) strongly connected:
push E' - e on queue if not on queue
minimal = false
if minimal:
add G' = (V, E') to list of minimal subsets.
Теперь он пропускает все наборы ребер, которые не могут быть сильно связаны,
потому что суперсеты тоже нет. Недостатком является то, что он может
возможно использовать много места. Это все еще, однако, неоднократно проверяет
подключение. Однако мы можем кэшировать эту информацию.
check_or_add_cached_connected(E)
push E on queue
while queue not empty:
pop E' from queue
connected = cached (E')
if connected:
minimal = true
for e in E':
child_connected = check_or_add_cache(E' - e)
if child_connected:
push E' - e on queue if not on queue
minimal = false
if minimal:
add G' = (V, E') to list of minimal subsets.
remove E' from cache
Теперь, когда мы начали кеширование, мы можем кешировать еще больше. Если
удаление ребра ломает график, оно также ломает любой подграф.
Это означает, что мы можем отслеживать «необходимые ребра» на графике и
распространять их вниз на любой подграф. И мы можем проверить эти необходимыекрая, чтобы избежать проверки подграфов.
check_or_add_cached_connected(E)
push E on queue
while queue not empty:
pop E' from queue
(connected, required_edges) = cached (E')
if connected:
minimal = true
for e in E' and not in required_edges:
child_connected = check_or_add_cached_connected(E' - e)
if child_connected:
push E' - e on queue if not on queue
minimal = false
else:
add e to required_edges
if minimal:
add G' = (V, E') to list of minimal subsets.
else:
for e in E' and not in required_edges:
merge_cache(E' - e, required_edges)
remove E' from cache
Структура кэша и очереди требует некоторой работы, чтобы гарантировать, что используемые операции могут быть выполнены эффективно, но это довольно просто.