29 декабря 2011 г.

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

Комментариев нет: