Порядковая функция графа

В этой статье рассмотрим введение порядковой функции на ориентированном графе. Будет приведено описание алгоритма порядковой функции и его реализация на языке программирования C#.

Описание алгоритма

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

Приведем описание алгоритма упорядочения графа:

  1. В подмножество нулевого уровня N0 включаются все вершины i, в которые нельзя попасть не из какой-либо другой вершины. В этом подмножестве проводится последовательная нумерация вершин 1, 2, …, m.
  2. В подмножество первого уровня N1 включаются все вершины i, в которые можно попасть только из вершин уровня N0. Проводится нумерация вершин m + 1, m + 2, …, m + r.
  3. В подмножество N2 включаются все вершины i, в которые можно попасть только из вершин более низких уровней и т.д. Подобная процедура продолжается до тех пор, пока не будут пронумерованы все вершины графа.

Рассмотрим пример. Пусть имеется граф, как на рисунке ниже.

Исходный граф для введения порядковой функции - vscode.ru

После введения порядковой функции на этом графе, получим следующее:

Порядковая функция графа - vscode.ru

Реализация алгоритма

Рассмотрим реализацию алгоритма введения порядковой функции на графе. Для разработки будет использоваться язык C#.

Пусть дуга графа представляет собой экземпляр класса Edge:

, где v1 – номер вершины, из которой дуга исходит, а v2 - номер вершины, в которую данная дуга заходит.

Иерархический уровень упорядоченного графа представим экземпляром класса HierarchicalLevel:

, где level – список номеров вершин, входящих в данный иерархический уровень.

Всё множество дуг и иерархических уровней упорядоченного графа будем хранить в виде соответствующих списков:

Приведем реализацию метода createHLevel(…), упорядочивающего граф.

Аргументы метода createHLevelHL – список иерархических уровней графа, numberV – количество вершин в графе, E – список дуг в графе.

Кратко опишем принцип работы метода createHLevel(). В начале все вершины считаются неиспользованными и заносятся в список notUsedV. Программа продолжает работу, пока список notUsedV не окажется пустым. На каждой итерации для данного иерархического уровня перебираются все вершины из списка notUsedV. Для каждой вершины из этого списка вычисляется ее полустепень захода (int k), затем из этого числа вычитается количество дуг, входящих в вершину из вершин предыдущих уровней (эти вершины хранятся в списке usedV). Если в итоге k оказывается равным нулю, значит вершина принадлежит данному уровню: добавляем ее список вершин уровня и удаляем из списка неиспользованных вершин. В конце итерации для данного иерархического уровня обновляем список использованных вершин usedV: добавляем в него номера вершин, занесенных в данный уровень.

Если вы хотите скачать код метода createHLevel, то нажмите на кнопку ниже.

Скачать код метода createHLevel

 

 

Примечание

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

 

Оцените статью

Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">