Алгоритмы на графах — Часть 1: Поиск в глубину и проблема взаимоблокировок

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

    Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
    Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
    В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
    На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
    Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
    Для начала определимся, что же будет элементами нашего графа, и как его составить.

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

    image

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

    Теперь все готово для формального описания самого алгоритма.
    1. Пронумеруем все вершины графа
    2. Отметить все вершины графа, как новые
    3. Отметить все дуги графа, как новые
    4. Поместим произвольную вершину графа в стек
    5. Пока стек не пуст, прочитать (не выталкивая) из стека последнюю вершину и применить к ней процедуру Find(Node V)
    6. Если стек пуст, но остались новые вершины, положить в стек любую из новых и перейти к п.5

    Процедура Find(Node V)
         Для вершины V снять признак новизны;
         Для всех новых дуг D, из списка смежности вершины V
              Снять с D признак новизны;
              Если дуга D ведет в новую вершину
                   Поместить D.LinkNode в стек;
                   Выполнить Find(Node D.LinkNode);
              Конец (Если);
              Если вершина не новая и присутствует в стеке
                   Прочитать стек от текущей вершины до D.LinkNode и поместить данные в хранилище обнаруженных контуров
              Конец (Если);
         Конец (для всех новых дуг D);
         Вытолкнуть V из стека;
    Конец (Процедура Find);

    Где D.LinkNode — вершина, на которую указывает дуга.

    Пример реализации алгоритма:

    Для начала нам понадобится объявить тип данных для графа и его вершин

      public class GraphNode
      {
        public bool New;
        public List<GraphNode> Links;
      }


    * This source code was highlighted with Source Code Highlighter.


      public class Graph
      {
        public List<GraphNode> Nodes;
      }


    * This source code was highlighted with Source Code Highlighter.


    Теперь реализуем класс, выполняющий поиск контуров

      public static class PathFinder
      {
        static List<GraphNode> list;
        static List<List<GraphNode>> paths;

        public static List<List<GraphNode>> Find(Graph graph)
        static void InternalFind(GraphNode node)
      }


    * This source code was highlighted with Source Code Highlighter.


    И, собственно, наши основные функции:

        static List<List<GraphNode>> Find(Graph graph)
        {
          list = new List<GraphNode>();    //Имитируем стек
          paths = new List<List<GraphNode>>(); //Результирующий список контуров

          foreach (GraphNode node in graph.Nodes)
          {
            node.New = true;
          }

          list.Add(graph.Nodes[0]); //Добавляем первую вершину для начала алгоритма

          bool done = false;
          while (!done)
          {
            while (list.Count > 0)
            {
              InternalFind(list[list.Count - 1]);
            }

            // Поиск оставшихся новых вершин
            done = true;
            foreach (GraphNode node in graph.Nodes)
            {
              if (node.New)
              {
                list.Add(node);
                done = false;
                break;
              }
            }
          }
          return paths;
        }


    * This source code was highlighted with Source Code Highlighter.


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

        static void InternalFind(GraphNode node)
        {
          node.New = false;

          foreach (GraphNode nextNode in node.Links) //Итерация по всем дугам текущей вершины
          {
            if (nextNode.New)
            {
              list.Add(nextNode);
              InternalFind(nextNode);
            }

            else if (list.IndexOf(nextNode) != -1) // Вершина уже присутствует в стеке, найден контур
            {
              List<GraphNode> newPath= new List<GraphNode>();
              int firstElement = list.IndexOf(nextNode);

              for (int i = firstElement; i < list.Count; i++)
              {
                newPath.Add(list[i]);
              }
              paths.Add(newPath);
            }
          }
          list.Remove(node);
        }


    * This source code was highlighted with Source Code Highlighter.


    Графически, алгоритм можно рассмотреть так:

    image

    Из вершины «0», которая является началом пути, мы движемся вниз, если на очередном шаге алгоритм находит дугу, указывающую на вершину, находящуюся в стеке (в данном случае дуга исходит из вершины «4»), из вершин стека образуется контур (на примере: 0-2-3-4-5-0), соответственно, если дуга указывает на уже не новую вершину, но уже вытолкнутую из стека (например на вершину «1»), контура не возникает.

    Данный алгоритм известен как поиск в глубину в ориентированном графе.

    Таким образом, исполняющей среде остаётся только отслеживать все вызовы методов и, периодически, проверять наличие блокировок.
    Как бороться с найденными блокировками? Иногда deadlock бывает настолько запутанным, что гораздо проще перезапустить взаимоблокируемый код, в любом случае, это уже должно решаться индивидуально для конкретной системы.

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

    UPD: Добавил пример кода
    UPD2: Перенес в алгоритмы, спасибо
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      0
      Пример с аудиторией — это скорее live lock.
        +1
        Хм, если я не ошибаюсь, в LiveLock процессы просто делают бесполезную работу, я имел ввиду что каждый просто будет стоять на месте и ждать, пока пройдет другой.
        +1
        мне кажется код тут не помешал бы.
        слишком сухо получилось.
          +1
          >> однопоточное java приложение с выходом в интернет

          Любое j2me-приложение, устанавливающее connect, будет отличным примером.
          0
          >> В следующий раз (с моей стороны) – алгоритм топологической сортировки, который, в том числе, может быть применен при компиляции и анализе цепи активаций нейронов в нейросети.

          Какие-нибудь бы попроще примеры на первый раз — например, определение порядка, в котором строить артефакты при помощи make-файла :)
            0
            Если вы имеете ввиду алгоритм ДеМукрона, то это и есть топологическая сортировка сети.
              0
              Меня смутило «в том числе», потому что основного примера я не увидел, был только пример " в том числе" :)
            –1
            Не совсем понят практическую ценность.

            Можете практических примеров привести поболее?

            И желательно, чтобы они были описаны в формате:
            1. Система делает А.
            2. Пользователь делает Б.
            3. Система делает В.
            4.…

            И где-то там в середке уже вплетается этот алгоритм, но что именно он делает для внешнего мира? Снутри то одной картинки хватило.
              0
              В том же примере с java2me, виртуальная машина могла бы определить deadlock, и запустить запрос разрешения у пользователя в отдельном потоке.
              Главная практическая польза — реализация алгоритма на уровне ОС.
                +1
                Позволю себе отметить, что это скорее академический интерес, нежели практическая польза.

                Что для конкретного пользователя это даёт в конкретной системе?
                  +1
                  Это, прежде всего, представляет интерес для разработчиков, упрощая решение каких-либо проблем.
                  Плюс для конечного пользователя такой же как от использования рекурсии или ООП, т.е. слабо поддаётся оценке.
                    0
                    Вот потому у нас и есть проблема коммерциализации изобретений — наизобретают тонны, а как до практики дойдет, то сразу «интерес для разработчиков».

                    Посмотрите в заголовок статьи!

                    :)
                +1
                Алгоритм поиска в глубину является вспомогательным в других более практических алгоритмах: тут. Думаю, потом эти алгоритмы появятся в след. статьях, с указанием практического применения.

                И так просто вспомнилось, когда мне нужно было C# загрузить файлы по некоторой маске (*.pdf) в БД из некоторой директории (в которой есть поддиректории), то я незадумываясь писал рекурсивную процедуру обхода директорий. Порядок в котором они обходились — и есть Поиск в глубину. В первую попавшуюся до упора, чуть назад в следующую… и.т.д.
                  0
                  Как раз вчера столкнулся с необходимостью поиска в глубину во время решения одной олимпиадной задачи. Тоже первым делом написал рекурсивную процедуру, но по быстродействию не проходило.
                  Посмотрел у другого участника его реализацию — вместо рекурсии используется очередь. То есть вместо вызова новой функции новое состояние ставится в очередь на обработку и по одному последовательно обрабатывается. Разница в быстродействии оказалась в 3-4 раза в пользу очереди. Количество состояний было ~50к, глубина рекурсии около 20 шагов.
                    0
                    Да. Согласен, что быстродействие и прожорливость по памяти ощутимо улучшается. =)

                    Позволю себе подправить Вашу опечатку, чтоб других не смущало: не «очередь», а «стэк» (рекурсия создает стэк вызовов функций).
                    Если там будет очередь, то получится BFS (поиск в ширину). =)
                      0
                      Спасибо, за поправку. Я тонкостей таких не знал. Вообще использование коллекции для хранения будущих обрабатываемых состояний увидел вчера впервые. Со стеком намного понятней осознать принцип алгоритма :)
                0
                «По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс»
                  0
                  Ой, рано отправил.
                  «По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс» — не совсем верно. Для взаимной блокировки нужна минимум пара ресурсов. Взаимной блокировки при споре об одном ресурсе быть не может. Пример: процесс A требует ресурс X и использует ресурс Y, а процесс B требует ресурс Y и использует ресурс X.
                  В примере с людьми в проходе тоже есть два ресурса — входы в этот проход с двух сторон. «Петя» стоит на входе в проход и ему нужен чтоб был свободен и выход чтоб пройти. Та же ситуация у «Васи» с другой стороны двери.
                  0
                  Контур и цикл в графе стало быть одно и то же? Никогда не встречал термин «контур» в этом контексте.
                    +1
                    не совсем одно и то же, «цикл» принято говорить в неориентированных графах. в ориентированных — «контур».

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

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