∘Орграф, ациклический. Присвоение уровней узлам

Присвоение уровней узлам ациклического графа

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

Некоторые ациклические графы, например, термины классификатора с отношениями между ними, имеют строение напоминающее горы - внизу, у подножия много узлов, а вверху, вершин, мало. Мы предполагаем для определённости что стрелки идут снизу вверх - к вершинам.

Естественно ввести для каждого узла "высоту над уровнем моря". Для определённости источники будут иметь уровень 1. А стоки теперь считаются вершинами гор, ну или пиками.

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

Присвоив источникам уровень 1 мы их удаляем (естественно со всеми из них исходящими стрелками). В получившимся графе появятся новые источники, коим присвоим уровень 2... пока граф не кончится, т.к. он ациклический.

Таким образом по определению - узлы уровня 2 это узлы в которые есть стрелки только из узлов уровня 1...

Такое расположение на уровнях гарантирует (геометрически), что все стрелки идут вверх, но при этом рисунок "компактен" по вертикали. Например, если сток имеет стрелки только от источников, то он попадёт на уровень 2, т.е. мы получим "холмик".

Замечание. При удалении источников часть оставшихся вершин графа может оказаться изолированными, что следует учитывать при представлении графа например таблицей стрелок или предикатом инцидентности - arcs(nf,nt) тогда и только тогда когда из nf в nt идёт стрелка.

Детали

Граф задаётся предикатом arcs(nf,nt), который является рабочим, т.е. изменяется алгоритмом. При этом множество изолированных узлов (они могут появиться при обработке графа) не поддерживается.

Чтобы обнаружить источники и стоки для каждого узла подсчитывается количество входящих (ai) и исходящих (ao) стрелок. Источники помечаются.

Чтобы обнаружить стоки следующего уровня пересчитывается количество входящих в узел стрелок - стрелки из источников вычитаются для каждого узла. В результате сток следующего уровня будет иметь ai=0, ao=0. Таким стокам на текущем шаге номер step присваивается уровень step+1, т.к. после удаления строк предиката этих (изолированных) узлов в нём уже не будет!

Блок-схема

Пояснения

После завершения алгоритма функция nl содержит уровень узла. Именно её назначает, заполняет алгоритм. На каждом шаге заполняются вспомогательные функции (атрибуты узлов):

- на выходе из блока (2,1) ai содержит количество входящих в узел стрелок, а ao - исходящих.

- в блоке (3,2) источникам присваивается значение 1 функции sois - "является источником". Это нужно потому, что далее в этом блоке ai пересчитывается, чтобы обнаружить источники следующего уровня и проверить не будет ли среди них изолированных. Такие изолированные следующего шага получают свой уровень (step+1) на текущем шаге, т.к. удаление парочек узлов из предиката arcs удалит и всякое упоминание о них.

Оператор ai(nf)=|0 выполняет условное присвоение: если значение ai на узле nf уже существует, то он ничего с ним не делает, а вот если значения нет, то присваивает 0.

Аналогично оператор ao(nf)=++1|1 - если значение ao на узле nf уже существует, то он увеличивает его на 1, а вот если значения нет, то присваивает 1.

Если остальные операторы не очевидны, то они описаны в Об одном алгоритме разбиения графа на связные компоненты

Замечание

Блок (3,1) для ациклического графа не нужен и его можно выкинуть. Но лучше оставить, т.к. срабатывая на произвольном графе алгоритм проверит его на ацикличность.

Программа

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

Применение

Мы исследовали ациклическую часть ГКВ - граф категорий Википедии, так называемую "мантию". Она получается после удаления циклической части ("ядра"). При этом появились "ложные вершины" - на полном графе они упираются в ядро. Оказалось, что самая высокая (28) вершина мантии - ложная! А самый высокий сток ГКВ имеет высоту 24.

Чего только не бывает;-)

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

Алгоритм разметки узлов номером уровня даже более естественен чем удаление. Сначала источникам присваивается 1 и 2 становится рабочим номером общего шага. На общем шаге ищутся непомеченные узлы у которых все "дети" помечены. Таким узлам присваивается рабочий номер...

Алгоритм.

1. назначить источникам уровень 1.

2. найти вершину (В1) у которой все узлы на входящих стрелках имеют уровень. Если такой вершины нет то стоп. Взять у детей В1 максимальный уровень (МУ1). Присвоить В1 уровень МУ1+1. Идти на 2.

Лемма. На ациклическом графе если есть таким образом непомеченые вершины, то есть такая у которой все дети помечены.

Док-во удалением - если удалить уровень 1, то получится решётка у которой будут свои источники (плюс изолированные). Именно они были связаны с уровнем 1 раз остались не удалёнными...