30 декабря 2011 г.

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

В последней заметке цикла будет рассмотрена самая, пожалуй, популярная бибилотека для визуализации графов graphviz. Биндинги для неё существуют для большинства популярных языков, в том числе и для python.

В отличии от рассмотренных ранее библиотек, graphviz предназначен исключительно для визуализации. Никаких алгоритмов внутри вы не найдёте. Поэтому чаще всего для манипулирования графами берут другие библиотеки, а полученные результаты представляют в виде dot-файла и отдают graphviz.


Документация краткая, но полная. Примеров в интернете полно (благо библиотека используется уже давно).

Graphviz предоставляет несколько алгоритмов расстановки графа:
  • dot - алгоритм расстановки деревьев (хорошо подходит для небольших направленных графов).
  • neato - алгоритм Kamada-Kawai.
  • twopi - алгоритм радиальной подстановки.
  • circo - распределяет вершины равномерно по кругу.
  • fdp - алгоритм Fruchterman-Reingold.
  • sfdp - модификация алгоритма Fruchterman-Reingold для больших графов.
Код, отвечающий за создание, расстановку и рендеринг графа, будет выглядеть примерно так:
Copy Source | Copy HTML
  1. G = gv.digraph('domains');

  2. gv.setv( G, 'size', '10000.00' );

  3. E = gv.protoedge(G);

  4. gv.setv( E, 'arrowsize', '0.5');

  5. N = gv.protonode(G);

  6. gv.setv( N, 'fontsize', '5' );

  7. gv.setv( N, 'shape', 'plaintext' );


  8. for node in nodes.values():

  9.     gv.node( G, node.encode('ascii','ignore') );


  10. for edge in edges:

  11.     gv.edge( G, nodes[edge[ 0]].encode('ascii','ignore'), nodes[edge[1]].encode('ascii','ignore'));


  12. t = time.time();

  13. gv.layout(G, 'fdp');

  14. logging.debug("compute %.4f sec %d Mb" % ((time.time()-t), memory_usage() / 1024) );


  15. gv.render(G, 'png', 'graph.png');
Как видите, никакого синтаксического "сахара", добавляйте по одной ноде и вершине (:

Итоговые результаты
Алгоритм Время работы, сек Пик потребления памяти, Мб
dot - -
neato - -
twopi 2.2361 62
circo - -
fdp 977.3580 118
sfdp 4.5221 51

Алгоритмы dot, neato и circo так и не смогли успешно завершиться, поскольку граф такого размера оказался им не по силам на моём железе =(

Визуальные результаты
Полноразмерные результаты работы алгоритмов доступны по клику.
twopi
SFDP
FDP

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