Недавно на Хабре была статья, посвященная алгоритмам на графах. С позволения автора, мой первый хабратопик продолжит цикл.
Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.
Возьмем более «машинный» пример: однопоточное java приложение с выходом в интернет. Представим, что наш код и система вывода сообщений будут выполняться в одном потоке, в этом случае, перед открытием соединения буден инициирован запрос пользователю, действительно ли он доверяет этому приложению пользоваться интернетом. Возникает блокировка, код не завершится, пока пользователь не нажмет «OK», но вывод сообщений будет возможен только после завершения кода. Попробуем построить граф для этого примера.
Вершинами обозначим функциональные узлы программы, дугами – внешние запросы, необходимые для продолжения работы узла.
Определим контур, как путь из какой либо вершины в саму себя. В таком случае на нашем графе каждый контур будет иллюстрировать возникший 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 — вершина, на которую указывает дуга.
Пример реализации алгоритма:
Для начала нам понадобится объявить тип данных для графа и его вершин
Теперь реализуем класс, выполняющий поиск контуров
И, собственно, наши основные функции:
Стек был намеренно реализован списком, т.к. нам надо будет считывать из него найденные контура, не выталкивая элементы
Графически, алгоритм можно рассмотреть так:
Из вершины «0», которая является началом пути, мы движемся вниз, если на очередном шаге алгоритм находит дугу, указывающую на вершину, находящуюся в стеке (в данном случае дуга исходит из вершины «4»), из вершин стека образуется контур (на примере: 0-2-3-4-5-0), соответственно, если дуга указывает на уже не новую вершину, но уже вытолкнутую из стека (например на вершину «1»), контура не возникает.
Данный алгоритм известен как поиск в глубину в ориентированном графе.
Таким образом, исполняющей среде остаётся только отслеживать все вызовы методов и, периодически, проверять наличие блокировок.
Как бороться с найденными блокировками? Иногда deadlock бывает настолько запутанным, что гораздо проще перезапустить взаимоблокируемый код, в любом случае, это уже должно решаться индивидуально для конкретной системы.
В следующий раз (с моей стороны) – алгоритм топологической сортировки, который, в том числе, может быть применен при компиляции и анализе цепи активаций нейронов в нейросети.
UPD: Добавил пример кода
UPD2: Перенес в алгоритмы, спасибо
Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.
Возьмем более «машинный» пример: однопоточное java приложение с выходом в интернет. Представим, что наш код и система вывода сообщений будут выполняться в одном потоке, в этом случае, перед открытием соединения буден инициирован запрос пользователю, действительно ли он доверяет этому приложению пользоваться интернетом. Возникает блокировка, код не завершится, пока пользователь не нажмет «OK», но вывод сообщений будет возможен только после завершения кода. Попробуем построить граф для этого примера.
Вершинами обозначим функциональные узлы программы, дугами – внешние запросы, необходимые для продолжения работы узла.
Определим контур, как путь из какой либо вершины в саму себя. В таком случае на нашем графе каждый контур будет иллюстрировать возникший 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.Графически, алгоритм можно рассмотреть так:
Из вершины «0», которая является началом пути, мы движемся вниз, если на очередном шаге алгоритм находит дугу, указывающую на вершину, находящуюся в стеке (в данном случае дуга исходит из вершины «4»), из вершин стека образуется контур (на примере: 0-2-3-4-5-0), соответственно, если дуга указывает на уже не новую вершину, но уже вытолкнутую из стека (например на вершину «1»), контура не возникает.
Данный алгоритм известен как поиск в глубину в ориентированном графе.
Таким образом, исполняющей среде остаётся только отслеживать все вызовы методов и, периодически, проверять наличие блокировок.
Как бороться с найденными блокировками? Иногда deadlock бывает настолько запутанным, что гораздо проще перезапустить взаимоблокируемый код, в любом случае, это уже должно решаться индивидуально для конкретной системы.
В следующий раз (с моей стороны) – алгоритм топологической сортировки, который, в том числе, может быть применен при компиляции и анализе цепи активаций нейронов в нейросети.
UPD: Добавил пример кода
UPD2: Перенес в алгоритмы, спасибо
