∘Граф. Разбиение на связные компоненты

Разбиение графа на связные компоненты

Алгоритм и программа

Если граф получен из некоторой системы, конструкции, сущего... для анализа свойств, то первый вопрос к нему - является ли он связным? Или - из каких связных компонент он состоит? Иногда для системы связность (односвязность) не так уж существенна и даже не обязательна.

Приводится алгоритм который за один проход по стрелкам строит множество узлов и приписывает каждый узел его связной компоненте. Прелесть этого алгоритма в том что он не ходит вдоль стрелок (или дуг). Оказалось что это не нужно для разбиения множества узлов на связные компоненты!

Введение

Здесь со временем может появиться сравнение с алгоритмами перечисленными в http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Сам же алгоритм можно считать вариацией на тему "Система непересекающихся множеств" см. http://en.wikipedia.org/wiki/Disjoint-set_data_structure

<11.07.2011>А идейно это алгоритм Борувки (http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm) и надо будет добавить построение остовного дерева (деревьев), т.к. некоторые программы 3D визуализации (Walrus, например) требуют остовное дерево.

Уточнение задачи

Пусть граф изначально представлен предикатом <arcs>(nf,nt), где nf - номер исходящего узла стрелки, nt - номер входящего узла стрелки. Для неориентированных графов это просто номера узлов окончаний дуги. Представимость предикатом означает, что в графе нет параллельных стрелок (дуг). Кои на связность графа не влияют.

Задача. Построить по <arcs> функцию <cn>(ni), где ni - номер узла из предиката <arcs>, cn - возвращает номер связной компоненты, которой принадлежит узел.

Замечание. В самом общем случае в графе могут быть и изолированные вершины, которые следует перечислять в дополнение к <arcs> и каждая из них образует отдельное связное множество.

Идея алгоритма

Мы последовательно проходим таблицу <arcs>, обрабатывая каждую стрелку.

Обработка первой стрелки.

Добавить оба узла (а в случае петли - один узел) в новую компоненту.

Общий шаг.

Пусть пришла очередная стрелка с узлами nf, nt, а мы уже накопили сведения о принадлежности компонентам узлов предыдущих стрелок.

С узлами nf, nt (которые в случае петли совпадают) возможны следующие варианты по отношению к уже имеющимся компонентам:

1. Оба узла не попадают ни в одну из компонент. Тогда из них надо организовать новую компоненту.

2. Один из узлов попадает в компоненту, а другой - нет. Тогда этот другой надо добавить к компоненте попавшего.

3. Оба узла попадают в какие-то компоненты. Здесь возможны два варианта:

3.1. Оба уза попали в одну и ту же компоненту. Тогда ничего делать не надо.

3.2. Узлы попали в разные компоненты. Тогда следует объединить компоненты в одну.

Блок-схема

Пояснения

cc - текущий номер для новой компоненты. Начинаем с 1.

Хранимые (persistent) объекты аналогичны таблицам, но мы различаем предикаты - они возвращают True, False и функции (обычно частичные), которые возвращают значение, которое было присвоено.

Идентификаторы хранимых объектов помещаются в угловые скобки для наглядности.

<arcs>(fn,tn) равен True, если из узла fn в узел tn идёт стрелка. Предполагается, что дублирующих стрелок в графе нет.

<cn>(ni) - функция возвращающая номер компоненты к которой приписан узел ni. Собственно назначение значений этой функции на узлах графа заданного <arcs> и есть цель алгоритма.

Если функция частичная, а <cn> в начале даже пуста, то для некоторого значения аргумента значения функции может и не быть. И здесь очень полезен оператор в примере

fn_cn=<cn>(fn)|0

- если <cn> имеет значение на fn, то fn_cn его получит, а если значения нет, то получит 0.

<cn>(fn)=cc назначает значение функции на fn равным cc.

Оператор

for any <cn>(ni)=fn_cn do <cn>(ni)=tn_cn

вводит локальную переменную ni, которая "пробегает" по области определённости функции <cn>.

Прагматика

Блок (6,1) мог бы и наоборот присваивать fn_cn узлам tn_fn значение. В программе применена оптимизация - меньшей по объёму компоненте присваивается номер большей.

Программа

В прикреплении есть программа get_components.pgc. Прога заполняет (предварительно почистив) таблицу components(ni,cn:integer).

На входе у неё таблица arcs(nf,nt:integer).

Прога написана на ECPG.

Запуск: ./get_components.sh

#!/bin/sh

ecpg get_components.pgc

cc get_components.c -o get_components -lecpg

./get_components

Прога выдаёт довольно подробный протокол, т.к. сообщает о каждом слиянии, что может быть и утомительно и поучительно.

Использование

Граф категорий Wikipedia

Прога использована на графе узлов категорий Wikipedia, любезно предоставленном Антоном Коршуновым из ИСП РАН после его доклада на SIGMOD Moscow http://synthesis.ipi.ac.ru/sigmod/seminar/s20110428.

Результат её работы выложен в Google Fusion tables: http://www.google.com/fusiontables/DataSource?dsrcid=1023087

Таблица, аналог <arcs>, также полученная (в двух смыслах этого слова) из запасов Антона Коршунова также выложена: http://www.google.com/fusiontables/DataSource?dsrcid=916674

Оказалось что граф содержит 1987 связных компонент!

Александр Шкотин

ashkotin@acm.org

Лето 2011

Page updated

Google Sites

Report abuse