Какие задачи, где и когда решают фреймворки для построения графов? Есть целый класс проблем, связанных с изучением графов. Это моделирование социальных связей, сетей и маршрутов, анализ алгоритмов и структур, к примеру, молекул или скрытых слоев глубоких нейронных сетей.
Для этих задач требуется инструмент построения моделей, способный анализировать структуры и вычисленять метрики, который к тому же будет оптимизирован по потреблению памяти и дискового пространства, так как графы как правило весьма объемны.
Именно такими инструментами являются библиотеки Snap и Networkx.
Snap
Фреймворк Stanford Network Analysis Platform (SNAP), как следует из названия, разработан в рамках Stanford University проекта по изучению графовых структур. В Стенфорде преподается специальный курс cs224w, в котором студенты проходят алгоритмы и методы построения, обработки и оптимизации графов.
Фреймворк Snap написан на C++ и имеет обертку на python. Вообще, сам проект не очень активно поддерживается и пишется в основном силами студентов (один из вариантов защиты на курсе).
Документация проекта существует в довольно сумбурном виде: есть автосгенерированная сишная и вот такая для python. Вот тут находится краткое описание как работать со Snap.
Фреймворк поддерживает четыре типа графов - направленный, ненаправленный, и аналогичные «сети» (так называемые мультиграфы). Описание классов этих четырех сущностей и производных можно найти тут.
Важный аспект — так как фреймворк написан на c++, а питоном только обернут, большинство питоновских методов во фреймворке недоступно. Все объекты, используемые для построения моделей требуют собственных типов, определенных в Snap. При первом знакомстве это очень сильно сбивает с толку. Кроме того, не все методы Snap, имеющиеся в наборе, обернуты в python. В некоторых аспектах (например, при итерации или манипуляциях с random) придется изобретать что-то неочевидное.
Питонья обертка написана в сишном стиле. Опять-таки, будет сложно запомнить нотацию. Пример:
import snap
G = snap.GenFull(snap.PNEANet, 100)
Rnd = snap.TRnd(42)
Rnd.Randomize()
for i in range(0, 10):
NId = G.GetRndNId(Rnd)
print(NId)
В Snap есть интерфейс к Graphviz, с помощью которого можно отрисовывать модели. Обратите внимание, что для того, чтобы graphviz сросся с вашим python, потребуется установить pydot и python-graphviz.
Основное преимущество Snap — это скорость расчетов графовых структур. Во фреймворке не сильно богатый набор готовых решений для моделирования, поэтому, если потребуется что-то доработать, придется знать c++.
Еще один нюанс — Snap не всегда дружит с путями к системному питону. Если у вас не получилось запустить фреймворк, то вам необходимо найти в папке размещения Snap два файла _snap.pyd и snap.py, после чего скопировать их в корень проекта, в котором вы ведете разработку с применением Snap. Все должно заработать.
Networkx
Фреймворк Networkx — более дружелюбный сородич Snap, написанный на чистом python. Проект поддерживается обширным комьюнити, регулярно обновляется и имеет отличную документацию.
По вычислениям Networkx не такой бодрый, как Snap, но благодаря значительной оптимизации, довольно шустро справляется с графами среднего размера. Основное его преимущество — он написан в python стиле, к объектам фреймворка применимы все методы и функции питона. Это позволяет итерировать, писать собственные решения, наследуя поведение, а так же наслаждаться всеми преимуществами языка.
В Networkx также доступны все четыре типа графов из Snap - ненаправленный, направленный, и два аналога для мультиграфа. Нодами, в отличие от Snap, могут быть любые хешируемые объекты. Специальных типов создавать не нужно. Фреймворк позволяет добавлять ноды и ребра «на лету» используя несколько интерфейсов, включая списки кортежей, словари и другие графы. Можно добавлять любые атрибуты к нодам, ребрам и графам.
Пример использования разных методов при создании графа:
import networkx as nx
G = nx.MultiDiGraph()
G.add_node(1)
G.add_nodes_from([2, 3])
G.add_nodes_from(range(100, 110))
H = nx.path_graph(10)
G.add_nodes_from(H)
G.add_node(H)
G.add_edge(1, 2)
G.add_edges_from([(1, 2), (1, 3)])
G.add_edges_from(H.edges)
G.add_edges_from([(4,5,dict(route=282)), (4,5,dict(route=37))])
G[4]
AdjacencyView({5: {0: {}, 1: {'route': 282}, 2: {'route': 37}}})
В «build-in» входит довольно внушительное число инструментов для моделирования и изучения структуры графов. Также фреймворк позволяет отрисовывать модели в matplotlib и graphviz. Можно читать и писать различные структуры, такие как JSON, yaml, сериализованные объекты и различные другие форматы хранения графовых моделей. Есть интеграция с Numpy, Scypy и Pandas.
Вывод
Скорее всего, вы познакомитесь со Snap, если проходите курс cs224w, так как домашние работы требуется выполнить именно в этом фреймворке. Пройдя курс, с большой долей вероятности вы забудете про Snap и перейдете на Networkx.