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

Тема второй заметки о визуализации графов - библиотека igraph, имеющая биндинги под python. Для визуализации она использует библиотеку Cairo.

Документация библиотеки детальная и подробнейшая, но абсолютно лишена даже базовых примеров. Примеры однако доступны в бета версии туториала - там всё детально и подробно расписано, правда на R =)
Что касается визуализации - то данный раздел туториала ещё не сделан, что в целом не сильно мешает.

По аналогии с предыдущей заметкой мерить будем время работы и пиковое потребление памяти алгоритма расстановки графа. Исходные данные для работы взяты идентичные использованным в тойже первой заметке цикла.


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

Copy Source | Copy HTML

1. import igraph as ig


2. t = time.time();


3. layout = G.layout("drl");


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


5. t = time.time();


6. ig.plot(G, "igraph.png",


7.         layout = layout,


8.         bbox=(10000,10000),


9.         edge_arrow_size=0.5,


10.         edge_arrow_width=0.5,


11.         edge_width=0.1,


12.         vertex_size=2,


13.         vertex_color='red',


14.         vertex_label_size=5,


15.         vertex_label=node_names);


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

В данном случае используется алгоритм DRL, предназначенный специально для больших графов и разработанный Shawn Martin и его коллегами из Sandia National Laboratories.

После нескольких прогонов этого кода, были получены следующие результаты:
RAM 602 Mb
Time 16.6279 сек

В библиотеке также реализовано много других алгоритмов расстановки. Подходят нам (2D, направленный невзвешенный граф) следующие:

• circle - распределяет вершины равномерно по кругу.
• drl - уже упомянутый алгоритм для больших графов.
• fr - силовой алгоритм Fruchterman-Reingold.
• graphort - алгоритм на основе физической модели, разработанный Michael Schmuhl. 
• gfr - модификация алгоритма Fruchterman-Reingold для больших графов.
• kk - алгоритм Kamada-Kawai.
• lgl - адгоритм LGL.
• random - равномерное распределение точек.
• rt - алгоритм Reingold-Tilford (хорош для деревьев).
• rt_circular - модификация предыдущего алгоритма для размещения дерева по кругу.

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

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

Алгоритм	Время работы, сек	Пик потребления памяти, Мб
drl	16.4427	602
circle	0.0021	33
fr	201.5808	33
graphopt	207.0354	33
gfr	5.5035	33
kk	7909.0232	166
lgl	28.1835	33
random	0.0022	33
rt	0.0404	33
rt_circular	0.0410	33

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

DRL

Circle

FR

Graphopt

GFR

KK

LGL

Random

RT

RT circular