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