Топологическая декомпозиция структуры C#

В этой статье рассмотрим одну из важнейших задач структурного анализа – топологическую декомпозицию структуры системы, то есть выделение в ней сильно связных подграфов (подсистем). Будет описан алгоритм и приведена его реализация на языке программирования C#.

Теоретические сведения

Введем некоторые определения. Множество вершин графа G(V, E), достижимых из вершины i, называется достижимым множеством R(i) и определяется следующим образом:

Формула достижимого множества вершин - vscode.ru

где G(i) – множество правых инциденций вершины i, т. е. множество вершин, достижимых из вершины i с использованием путей длиной, равной единице; G(P)(i) – множество вершин, достижимых из вершины i с использованием путей длиной p. При этом предполагается, что сама вершина i достижима с использованием пути длиной, равной нулю, и включена во множество R(i).

Контрдостижимым множеством Q(i) графа G(V, E) называется множество таких вершин, когда из любой вершины этого множества можно достигнуть вершины i. Оно определяется следующим образом:

Контрдостижимое множество вершин графа - vscode.ru

где G(-1)(i) – множество левых инциденций вершины i, т. е. множество вершин, из которых можно достичь i-ую вершину, при этом длина пути равна 1 и т. д.

Пересечение множеств R(i) ∩ Q(j) – это множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от i-ой вершины к j-ой. Эти вершины называются существенными или неотъемлемыми, относительно двух концевых вершин i и j.

Множество R(i) ∩ Q(i) – однозначно определяет сильно связный подграф графа G(V, E), содержащий вершину i, т.к. все вершины этого множества достижимы из i-ой вершины и из каждой вершины достижима вершина i, то есть они взаимно достижимы.

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

  1. Выбираем вершину с наименьшим номером i.
  2. Определяем для нее достижимое множество вершин R(i).
  3. Определяем для нее контрдостижимое множество вершин Q(i).
  4. Выделяем в системе сильно связный подграф, включающий множество вершин V = R(i) ∩ Q(i).
  5. Удаляем все вершины V из первоначального графа.
  6. ЕСЛИ начальный граф не пуст, ТО переходим к шагу 1. ИНАЧЕ конец.

Пример использования алгоритма

Пусть имеется такой граф:

Топологическая декомпозиция структуры - vscode.ru

  1. Определяем достижимое множество для вершины 1: R(1) = (1, 2, 5, 7, 6, 8, 9, 10).
  2. Определяем контрдостижимое множество для вершины 1: Q(1) = (1, 9, 8, 10, 3, 6, 4, 7, 2).
  3. Находим пересечение этих множеств, которое и определяет сильно связный подграф (подсистему), включающий вершину 1: V1 = R(1) ∩ Q(1) => G1(V1, E1) = (1, 2, 6, 7, 8, 9, 10).
  4. Удаляем все вершины V1 из первоначального графа.
  5. Поступаем аналогично с остальными вершинами:

V2 = R(3) ∩ Q(3) => G2(V2, E2) = (3),

V3 = R(4) ∩ Q(4) => G3(V3, E3) = (4),

V4 = R(5) ∩ Q(5) => G4(V4, E4) = (5).

В результате декомпозиции получили 4 связных подграфа (подсистемы): G1 (1, 2, 6, 7, 8, 9, 10), G2 (3), G3 (4), G4 (5).

Топологическая декомпозиция структуры - vscode.ru

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

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

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

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

Подграф представим в виде экземпляра класса Subgraph:

, где List<int> V – список номеров вершин, входящих в подграф.

Все множества дуг и подграфов будем хранить в виде списков:

Приведем реализацию метода topologicalDecomposition(…), выполняющего топологическую декомпозицию структуры.

Аргументы метода topologicalDecomposition: countV – количество вершин в графе, E – список дуг в графе, Sub – список подграфов.

Для обхода графа и поиска множеств R и Q используется рекурсивный алгоритм “Поиск в глубину” (Depth-first search). Опишем принцип его работы:

Пусть дан граф G = (V, E), где V – множество вершин графа, E – множество его ребер. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

  1. Переберем все вершины v ∈ V. ЕСЛИ вершина белая, выполним для нее DFS(v).

Процедура DFS (параметр – вершина u ∈ V)

  1. Перекрашиваем вершину u в черный цвет.
  2. Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w).

Вот реализация метода DFS для нашей задачи (белый цвет – это 1, черный – 2):

Аргументы метода DFS: u – номер начальной вершины, endV – номер конечной вершины, E – список дуг графа, color – цвета вершин. Если вершина endV достижима из вершины u, то метод вернет значение true, иначе false.

Скачать листинги из статьи

 

 

Топологическая декомпозиция структуры C#
5 (100%) 2 votes

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

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

Ваш 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="">