27 декабря 2011 г.

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

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