В 1736 году была очень популярна задача «кенигсбергских мостах», которую долгое время никто не мог решить. Позже она стала классической задачей теории графов. А сам термин «граф» впервые был введен только через 200 лет. Сегодня графы – это невероятное средство моделирования. Расскажем, как мы используем их для поиска альтернативных решений привычных задач.
Одним из преимуществ сети интернет является возможность почти всегда найти альтернативное решение проблемы, которую уже давно вы сами решили. Особенно сильно это заметно в программировании. Даже самый хороший алгоритм или идеально написанный код кто-то сможет сделать еще лучше). А мы, пользователи, программисты и просто мимо проходящие можем сделать вывод, какай вариант лучше.
С примером такого альтернативного решения, мы встретились, когда изучали графовые алгоритмы. При рассмотрении статей на эту тему, нам в основном попадались реализации на языке python и библиотеки networkx. Но при этом есть не менее замечательная библиотека igraph.
Давайте разберем несколько простых примеров графовых алгоритмов на примере библиотеки igraph.
В начале попробуем просто разобраться как можно ее использовать, например, для построения простого графа.
Для этого нам потребуется следующий код:
В начале мы импортируем библиотеку igraph. После создаем переменную, которая в себе будет содержать данные о графе. А дальше мы указываем количество и связи между вершинами.
Интересней становится, когда необходимо выбрать «форму графа». Это определяется его обозначением (в нашем случае «circle» – макет, где вершины располагаются по кругу). Всего основных макетов 13.
И последней строчкой мы рисуем граф. В итоге у нас получается следующие:
Теперь давайте перейдем к более сложному примеру. Например, нам необходимо построить дерево, которое изобразит компанию относительно подчинения директору.
Для этого мы будем использовать следующий код:
Давайте теперь разберемся в том, что здесь написано.
В начале мы так же импортировали библиотеку. После этого создали переменную графа, но уже указали его тип, количество вершин, глубину дерева. После этого мы начинаем описывать данные в графе.
Первое – указываем размер вершины, после этого перечисляем все вершины и их цвета. Тут есть одна особенность. Как видим, в начале мы указали глубину 3. Это обозначает, что от каждой вершины первого уровня идет три вершины второго уровня. И так далее, пока вершины не кончатся. Для правильного отображения и построения связей мы должны об этом помнить. Для цветов действует такой же алгоритм. Для примера мы подсветим бухгалтера и его замов красным цветом. В итоге у нас получается следующая картинка:
Как вы видите ничего сложного. Главное разобраться, кто за кем идет.
Использование дерева в наших задачах ограничивается лишь нашей фантазией) Можно искать и удобно просматривать даже достаточно большие деревья в igraph.
Кроме этого у библиотеки igraph есть одно большое преимущество: она работает намного быстрее по сравнению с networkx. Это связано с ее реализацией. Поэтому для успешного использования вам необходимо будет установить Cairo API (https://www.cairographics.org/).
В этой статье мы рассмотрели примеры использования библиотеки igraph. Она достаточно эффективно позволяет работать с различными графовыми алгоритмами. Опыт ее использования показал, что она незаменимый помощник при построении графов по большим данным, но при этом остается достаточно простым в использовании инструментом.