graph-tool [заметки о визуализации графов на python]

Третья заметка цикла посвящена python модулю graph-tool.
Базируется он на шибко резвой Boost Graph Library (BGL), а для визуализации использует graphviz.
Вообще, у BGL есть собственные биндинги на Python, однако

• BGL-Python bindings are no longer being maintained.  
• BGL не имеет инструментов для визуализации и нацеленна на использование в паре с graphviz.
• Готовые яйца под питон так и не появились, а ставить руками столь широкие вещи весьма трудоёмко.

Думаю именно по этим причинам была написана graph-tool.

Итак, ближе к телу =)


Документация удобная, подробная и всеобъемлющая, поэтому с использованием проблем скорее всего не возникнет.

В модуле реализовано всего 3 алгоритма расстановки графа, что весьма скудно, если сравнивать с тем же igraph. Остальные алгоритмы возлагаются на graphviz и будут рассмотренны, когда я до него доберусь =)

Код визуализации графа будет выглядеть примерно так:

Copy Source | Copy HTML

1. t = time.time();
2. pos = draw.random_layout(G);
3. logging.debug("compute %.4f sec %d Mb" % ((time.time()-t), memory_usage() / 1024) );
4. draw.graph_draw(G,
5.         pos=pos,
6.         pin=True,
7.         size = (10000,10000),
8.         vsize= 0.1,
9.         eprops={"color": "#707070", "penwidth":  0.2, "arrowsize":  0.2},
10.         penwidth= 0.5,
11.         output_format="png",
12.         output="gtool_random");

Обратите внимание - если не указать pin=True, то рассчитанные позиции вершин будут проигнорированы и graphviz посчитает всё сам.
Также замечу, что размер холста надо указать в сантиметрах (Оо). К слову, добиться жёсткого размера итогового изображения мне так и не удалось - библиотека или сам graphviz домысливают оптимальный размер холста и игнорируют мои пожелания =((

В общем с этими подводными камнями пришлось повозиться, а всё ради следующих функций:

• fruchterman_reingold_layout - алгоритм Fruchterman-Reingold.
• arf_layout - алгоритм, разработанный Chair of Systems Design of ETH Zürich. Полное название "attractive and repulsive forces".
• random_layout - равномерное распределение вершин по квадрату.

Итоговые результаты

Алгоритм	Время работы, сек	Пик потребления памяти, Мб
fruchterman_reingold	474.5751	142
arf	>6067.1120	223
random	0.0330	140

Алгоритм ARF по истечении полутора часов работы завершился с ошибкой
  graph is too large for cairo-renderer bitmaps. Scaling by 1.52583e-05 to fit
Что позволяет предположить наличие внутри ещё и библиотеки Cairo. Кстати говоря, из всех перечисленных, только этот алгоритм использует несколько ядер в работе.

Визуальные результаты 
Полноразмерные результаты доступны по клику (осторожно, трафик).

Fruchterman-Reingold

Random