Анализ процессов, Графы

Библиотеки igraph. Графовые алгоритмы

Время прочтения: 3 мин.

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

Особенно сильно это заметно в программировании. Даже самый хороший алгоритм или идеально написанный код кто-то сможет сделать еще лучше)

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

С примером такого альтернативного решения, я встретился, когда изучал графовые алгоритмы. При рассмотрении статей на эту тему, мне в основном попадались реализации на языке python и библиотеки networkx. Но при этом есть не менее замечательная библиотека igraph.

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

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

Для этого нам потребуется следующий код:

from igraph import *
g = Graph()
g.add_vertices(3)
g.add_edges([(0,1), (1,2)])
layout = g.layout("circle")
plot(g, layout = layout)

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

Интересней становится, когда необходимо выбрать «форму графа». Это определяется его обозначением (в нашем случае «circle» – макет, где вершины располагаются по кругу). Всего основных макетов 13.

И последней строчкой мы рисуем граф. В итоге у нас получается следующие:

Теперь давайте перейдем к более сложному примеру. Например, нам необходимо построить дерево, которое изобразит компанию относительно подчинения директору.

Для этого мы будем использовать следующий код:

from igraph import *
g = Graph.Tree(7, 3)
g.vs['size'] = ['60']
g.vs['color'] = ['green', 'red', 'blue', 'yellow', 'red', 'red', 'red']
g.vs['label'] = ['Директор', 'Бухгалтер', 'Дворник', 'Сис.админ','зам.бух 1', 'зам.бух 2', 'зам.бух 3']
plot(g, layout=layout,bbox = (500, 300), margin = 50)

Давайте теперь разберемся в том, что здесь написано.

В начале мы так же импортировали библиотеку. После этого создали переменную графа, но уже указали его тип, количество вершин, глубину дерева. После этого мы начинаем описывать данные в графе. Первое – указываем размер вершины, после этого перечисляем все вершины и их цвета. Тут есть одна особенность. Как мы видим, в начале мы указали глубину 3. Это обозначает, что от каждой вершины первого уровня, идет три вершины второго уровня. И так далее, пока вершины не кончатся. Для правильного отображения и построения связей мы должны об этом помнить. Для цветов действует такой же алгоритм. Для примера мы подсветим бухгалтера и его замов красным цветом. В итоге у нас получается следующая картинка:

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

Использование дерева в аудите ограничивается лишь нашей фантазией) Можно искать и удобно просматривать даже достаточно большие деревья в igraph.

Кроме этого у библиотеки igraph есть одно большое преимущество: она работает намного быстрее по сравнению с networkx. Это связано с ее реализацией. Поэтому для успешного использования вам необходимо будет установить Cairo API (https://www.cairographics.org/).

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

Советуем почитать