∘Орграф. Выделение ядра

Выделение ядра ориентированного графа

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

Ядро орграфа есть объединение всех его контуров (ор-циклов) и ор-путей между ними.

И хорошо оно тем, что его просто выделить: удаляя из графа источники (нет входящих) и стоки (нет исходящих) пока они есть или пока граф не кончится.

В первом случае мы получили ядро. Во втором - граф ацикличен.

См. [САОД] Гл. 4. Представление графов и деревьев. Перед рисунком “Рис. 4.26. Поиск циклов в графе”.

Замечание. Утверждение авторов "Все оставшиеся вершины обязательно принадлежат циклам." не верно.

Так два кольца соединённые ор-путём есть одно ядро. Если у соединяющего два кольца пути есть внутренние вершины, то никаким циклам они не принадлежат.

Алгоритм

Алгоритм работает с предикатом arcs(nf,nt), который равен True тогда и только тогда когда из узла nf в узел nt есть стрелка.

Алгоритм удаляет строки предиката и в конце предикат содержит стрелки ядра.

Блок-схема

Пояснения

ai(), ao() - предикаты, которым можно (и нужно) назначать значения на аргументе. В конце блока (1,1) они для каждого узла содержат True если в него есть входящие стрелки (ai) и/или из него есть исходящие стрелки (ao).

Оператор

for any <формула> do <цепочка действий> .

обычно содержит в формуле, свободные переменные. Формула задаёт критерий того для какого набора значений переменных надо выполнять цепочку действий. Так оператор

for any <arcs>(nf,nt) do ao(nf)=True, ai(nt)=True.

имеет в формуле две свободные переменные: nf, nt.

В формуле "(Exist not ai(x) & ao(x)) or (Exist not ao(x) & ai(x))" действие кванторов существования (Exist) задаётся включающими их скобками. Так что в формуле две связанных переменных - первое вхождение x, не имеет никакого отношения ко второму вхождению x.

Имена собственные True, False могут двояко употребляться в контексте действий. Это может быть:

- оператор "обнуляющий" предикат. Так "False ai, ao." делает так, что предикаты ai, ao будут возвращать False на любом значении аргумента.

- константа, используемая для присвоения значения предикату.

Оператор "for any not ai(x) & ao(x) do <arcs>(x,y)=False." интересен тем, что свободная переменная "y" не участвует в формуле, что означает, что на её "пробег" нет никаких ограничений.

Программа

Программа get_core.pgc (см. прикреп) написана на ECPG.

Вход:

- таблица wiki_arcs(cat_from,cat_to:integer) содержит предикат <arcs>.

- таблицы wiki_ai, wiki_ao, wiki_ai_ao, wiki_ao_ai; все строения (ni:integer). Их содержимое не важно, но они должны быть.

Выход:

- таблица wiki_arcs содержит стрелки ядра или пуста.

В таблицах wiki_ai, wiki_ao оказываются узлы ядра, если оно есть (в этом случае таблицы равны по составу).

Оптимизация.

Для ускорения работы у wiki_arcs созданы индексы на каждую колонку:

CREATE INDEX "from" ON wiki_arcs USING btree (cat_from);

CREATE INDEX "to" ON wiki_arcs USING btree (cat_to);

Программа работает с БД "CA" СУБД PostgreSQL, схема public.

Заполнить wiki_arcs можно так:

- очистить: truncate wiki_arcs;

- загрузить из csv-файла: psql -d CA -c "\copy wiki_arcs from links_table_all.csv delimiter ',' csv header"

Где links_table_all.csv файл с заголовком и разделитель - ",".

Предикаты ai, ao реализованы таблицами wiki_ai, wiki_ao. Кроме того таблица wiki_ai_ao содержит not ao(x) and ai(x), а таблица wiki_ao_io - not ai(x) and ao(x).

Все 4 таблицы пересоздаются заново в начале каждого шага.

Запустить прогу можно из терминальной сессии:

./get_core.sh - скрипт делает препроцессинг, компиляцию Си и выполнение:

#!/bin/sh ecpg get_core.pgc cc get_core.c -o get_core -lecpg ./get_core

Программа выдаёт на терминал довольно подробный протокол. Пример части протокола см. в прикрепе get_core_protocol.txt. Начальное количество стрелок было 1221133.

После выполнения программы самым ценным являются конечно ядро в таблице wiki_arcs.

Его стоит сохранить в файл:

psql -d CA -c "\copy wiki_arcs to wiki_arcs_.csv delimiter ',' csv header"

А можно использовать для дальнейшего анализа ядра, например, выделения связных компонент.

Так же важен состав узлов ядра в wiki_ni(ni), который можно отметить в таблице характеристик узлов графа (wiki_nodes_stats) например так

Update wiki_nodes_stats set level=0 from wiki_ni co where node_id=co.ni;

Особенности проги

Кривизна ECPG выразилась в том, что препроцессор упал на операторах

EXEC SQL delete from wiki_arcs using wiki_nodest n where cat_from = n.ni and n.ai=0;

EXEC SQL delete from wiki_arcs using wiki_nodest n where cat_to = n.ni and n.ao=0;

и пришлось вставлять в этих местах прямой вызов ECPGdo;-)

Замечание. В новой версии программы операторы delete немного другие, но кажется препроцессор напрягает using, так что я не стал проверять пройдут ли они через него.

Есть программа (get_core_pm), которая выполняет ещё одну работу:

- назначает каждому узлу мантии (т.е. не входящему в ядро) номер уровня (в мантии): если на очередном шаге, имеющем номер L1, узел удаляется как источник, то ему присваивается уровень -L1, если как сток, то L1. Узлам ядра присваивается в конце уровень 0.

Но этот подход симпатичный, но труден в дальнейшей обработке. Победил подход присвоения узлам мантии (стрелки после удаления ядра) уровней снизу вверх, начиная с 1, т.к. узлам ядрам (пока) присваивается 0.

Применение

Граф катекорий Википедии (ГКВ). Было выделено ядро ГКВ. Все подробности см. Wikipedia category graph. Прога потратила на это 5 минут времени портала Геология;-)

Программа get_core_pm работает так, что категории нижнего уровня (листья ГКВ) получат уровень -1, а категории верхнего уровня ("вершины" ГКВ) получат уровень 1.

Конечно сразу становятся интересны стрелки у которых начало имеет отрицательный уровень, а окончание - положительный.

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

ashkotin@acm.org

Лето 2011

Литература

[САОД] Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В.Структуры и алгоритмы обработки данных - Апатиты, КФ ПетрГУ, 2000. - 80 с.

http://khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/guap/index4.htm