Алгоритмы на графах — Часть 2: Сортировка сетей

    Пролог

    В продолжение опубликованной на выходных статьи.

    Компиляторы — пожалуй одна из самых интересных тем системного программирования.
    Эта статья не расскажет как написать идеальный, или, хотя бы, работающий компилятор, но она поможет прояснить пару аспектов его работы, при помощи метода топологической сортировки сети.

    Что такое сети?

    Сеть — это бесконтурный ориентированный граф (В предыдущей статье разбирался вопрос контуров и методы их нахождения).
    Для алгоритма нам понадобятся некоторые свойства, часть из них была более подробно разобрана в самой первой статье.



    Как видно из картинки, каждую вершину можно охарактеризовать числом дуг, входящих в неё (полустепень захода), и числом дуг, исходящих из неё к другим вершинам (полустепень исхода).
    Если у вершины нет ни одной входящей дуги, вершина называется источником сети.
    Если у вершины нет ни одной исходящей дуги, вершина называется стоком сети.



    Рассмотрим сеть на примере сборки приложения.
    Файлы обозначим вершинами.
    Роль дуг в сети проще понять по картинке:



    Дуга, идущая из вершины «Код» в вершину «Результирующий файл» говорит о том, что «Код» должен быть обработан прежде, чем будет получен Result.exe
    Перед тем, как вершина может быть обработана, следует обработать все вершины, ссылающиеся на неё.

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

    Пример 1:


    К сожалению, даже современные компиляторы не такие глазастые, чтобы увидеть здесь правильную последовательность сборки.

    Алгоритм

    Как же тогда компилятор понимает, что ему сделать сначала, а что потом?
    Сначала опишем, что же мы хотим от нашего алгоритма, а потом приведем код.
    Итак, наша цель — создать сеть, состоящую из нескольких уровней.



    Из рисунка видно, что задачи внутри одного уровня зависят только от задач на младших уровнях, и независимы друг от друга.
    В таком случае, для достижения цели нам сначала надо в любом порядке выполнить все задачи уровня 0, потом, в любом порядке, задачи уровня 1, и т.д., до уровня 3 (последнего).

    Для решения задачи, нам понадобится представление графа в виде матрицы (ij элемент = 1, если есть дуга из вершины i в вершину j, и равен 0, если дуги нет).

    Рассмотрим ещё один пример

    Пример 2:


    В строке под таблицей даны полустепени захода для всех вершин. Каждое число отражает сумму единичек в соответствующем столбце матрицы.

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



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

    Далее, проделываем тоже самое с оставшимися вершинами, имеющими нулевую полустепень захода и помещаем их в первый уровень:



    Последующие шаги выполняются аналогично



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

    Применим алгоритм к нашей сети из примера 1:



    Пример реализации

    Базовый каркас, который нам понадобится:
    public class GraphNode
    {
      public List<GraphNode> LinkedNodes;
    }

    public class Graph
    {
      public List<GraphNode> nodes;

      public void TopologicSort(out List<string> algResult, bool animated)
    }


    * This source code was highlighted with Source Code Highlighter.


    Вспомогательная функция, возвращающая массив полустепеней захода для всех вершин сети.
    int?[] GetInputNodesArray()
    {
      int?[] array = new int?[this.nodes.Count];
      for (int i = 0; i < this.nodes.Count; i++)
      {
        array[i] = this.nodes[i].LinkedDownNodes.Count;
      }
      return array;
    }


    * This source code was highlighted with Source Code Highlighter.


    И, наконец, алгоритм:
    public void TopologicSort()
        {
          List<List<GraphNode>> levels = new List<List<GraphNode>>();
          int?[] workArray = GetInputNodesArray();

          int completedCounter = 0;
          int currentLevel = 0;

          bool pathFound;
          while (completedCounter != this.nodes.Count)
          {
            levels.Add(new List<GraphNode>());

            // Во избежание обработки вершин, с нулевой
            // степенью захода, возникших по ходу следующего цикла,
            // помечаем их заранее.
            for (int i = 0; i < this.nodes.Count; i++)
            {
              if (workArray[i] == 0)
              {
                workArray[i] = null;
              }
            }

            for (int i = 0; i < this.nodes.Count; i++)
            {
              if (workArray[i] == null)
              {
                // Если вершину следует обработать, помещаем её
                // В соответствующий ей уровень и корректируем
                // Массив степеней захода остальных вершин
                levels[currentLevel].Add(this.nodes[i]);
                this.nodes[i].Tag = currentLevel; // Оставляем в вершине метку о её уровне

                foreach (GraphNode node in this.nodes[i].LinkedNodes)
                {
                  int linkedNode = this.nodes.IndexOf(node);
                  workArray[linkedNode]--;
                }

                workArray[i] = -1; // Помечаем вершину как обработанную

                completedCounter++;
              }
            }

            currentLevel++;
          }
        }


    * This source code was highlighted with Source Code Highlighter.

    Эпилог

    Компиляторами не ограничивается применение данного алгоритма, он также может быть применен например, при программировании нейронных сетей, или планировании крупных проектов.
    В следующий раз будет рассказ про алгоритмы поиска кратчайшего пути на графе (алгоритм Дейкстры и алгоритм Волнового фронта).

    Исходники

    Программа и Исходники на C#: Скачать
    По данной ссылке много более функциональная программа и несколько примеров сетей для сортировки.
    Презентация с опущенными шагами алгоритма: Скачать
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 22

      +1
      Что-то такое я смотрел при построении компиляторов.
        +9
        красивые иллюстрации, да и вообще все предельно понятно описано. спасибо.
          0
          а в чем иллюстрации такие красивые делали?
            0
            судя по раскраске кругов и форме стрелок это 2007й Word.
          +3
          Статья хорошая. Всё понятно написано, иллюстрации супер.
            +2
            VenomBlood, расскажите, пожалуйста, чем вы рисовали картинки? :)
              0
              Тоже интересно :)
                0
                очень похоже на клипарт из ворда-2007 :)
                  +4
                  Рисовал в PowerPoint 2007, в статье есть архив с этой презентацией.
                  +1
                  Иллюстрации хорошие, но вот код…

                  Понять, что делает функция (реализация алгоритма) зачастую проще если она чистая (без побочных действий). В таком случае часто по сигнатуре уже ясно, что происходит, но в вас TopologicSort ничего не возвращает, но кроме того, еще и принимает какие-то параметры, которые ни на что не влияют.
                    0
                    Алгоритм чистый, извините, забыл убрать параметры из заголовка.
                      0
                      Добавьте еще «return levels;» и измените сигнатуру, а то чистая функция, которая ничего не возвращает бесполезна=)
                    +5
                    Это не компилятор — это компоновщик, он же линкер, он же сборщик.
                    А компилятор (или даже несколько) отработал уровнем выше — преобразовав файлы кода в *.obj файлы
                      0
                      Это даже не линковщик. Это система сборки (например, make).
                        0
                        в компиляцию входит процесс сборки (линковки), как и процессы: анализа, оптимизации, генерации объектных файлов и т.д.

                        так что назвать линковку частью компиляции — вполне приемлимо.
                        0
                        В исходниках программа отличная, спасибо.
                          0
                          [терминология] Такие бесконтурные направленные графы иногда ещё называют дагами (dag, directed acyclic graph).
                            –3
                            Картинки красивые, и код разукрашен… а по делу что? лучше бы опущенные шаги сюда описали, код написать дело десятое…
                              0
                              Советую для прочтения книгу «Алгоритмы» Роберта Седжвика, в ней подробно описаны наиболее популярные алгоритмы, в том числе и на графах.
                                0
                                А задача расчета Page Rank'а для страниц в интернете не может быть решена таким же способом?
                                  0
                                  Я сомневаюсь, во первых мы вряд ли получим бесконтурный граф. Для расчета Page Rank, предполагаю, используются куда более сложные и комбинированные методы.
                                  0
                                  Кстати, есть книга Дж. Макконелл «Основы современных алгоритмов.» Содержание можно посмотреть, например здесь www.technosphera.ru/34.html?action=print

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

                                  Самое читаемое