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

В заметках этого цикла будут рассмотренны несколько известных библиотек для визуализации графов, имеющие python-api.
В каждой заметке произведено сравнение скорости работы различных алгоритмов расстановки графов, а также примерные значения требуемой памяти.
Все сравнения я буду производить на невзвешенном ориентированном графе, включающем около 5 тысяч вершин и 18 тысяч рёбер.
Тестовая машинка - 4GB RAM + i3 540 3.07 GHz (x4).

Мерить будем пиковое значение памяти и время работы, поскольку для меня именно эти метрики являются критичными.

Итак, NetworkX - библиотека для манипулирования графами под python.

Сами разработчики пишут, что визуализация не является приоритетной задачей данной библиотеки, однако делает она это неплохо, а в купе с удобными инструментами для манипулирования её применение видится весьма перспективным.

В последнее время её сильно пиарят и документация у неё очень хорошая, поэтому можно предположить стремительный рост популярности.

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

Copy Source | Copy HTML

1. def memory_usage():


2.     """Memory usage of the current process in kilobytes."""


3.     status = None


4.     result = 0;


5.     try:


6.         status = open('/proc/self/status');


7.         for line in status:


8.             parts = line.split();


9.             if parts[0][:-1] == 'VmPeak':


10.                 result = int(parts[1]);


11.     finally:


12.         if status is not None:


13.             status.close();


14.     return result;

По хорошему, её надо заменить модулем resource, но (чёрт его знает почему) пиковую память он отдаёт ровно вдвое большую, хотя анализирует тот же /proc/self/status. В общем мистика, надо разобраться =)

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

Copy Source | Copy HTML

1. import matplotlib.pyplot as plt


2. import networkx as nx   


3. plt.figure( figsize=(50,50) );


4. t = time.time();


5. nx.draw_random(


6.            G,


7.            node_size=1,


8.            width=0.1,


9.            font_size=6,


10.            alpha=0.5,);


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


12. plt.savefig('networkx');

В данном примере используется случайный алгоритм расстановки графа (равномерно распределяет узлы по квадрату).
Визуализации подлежит заданный ранее граф G. Процесс создания графов подробно описан в доке и учитываться при сравнении не будет (поверьте, этих милисекунд вы не заметите рядом с временем отрисовки =) ).

Вообще (если кто не знал), основное время отрисовки - это время рассчёта положения точек. Для этого придумано множество алгоритмов и большинство библиотек позволяют выбрать из нескольких доступных.
Основные же пики памяти нередко приходятся на рендеринг итоговой картинки, поэтому данный процесс не включен в таймер.

Результаты нескольких замеров работы данного кода дали следующее:
RAM 220.00 Mb
Time 2.4674 сек.

Для полноты картины попробуем другие алгоритмы.
Используемые функции:

• draw_graphviz() - обёртка над graphviz (). В данном случае использует neato и минимизирует целевую функцию аля spring.
• draw_spectral() -  опирается на граф Лапласа.
• draw_spring() - алгоритм Fruchterman-Reingold.
• draw_shell() -  стремится к концентрическим кругам.
• draw_circular() -упрощённый аналог предыдущего алгоритма.

Стоит заметить, что все рассмотренные функции работают на одном ядре процессора, что грустно, поскольку задачи на графы чудесно параллелятся.
Также напомню, что в памяти хранится сам граф, поэтому данная метрика годится только для оценки соотношения памяти, потребляемой алгоритмами.

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

Алгоритм	Время работы, сек	Пик потребления памяти, Мб
random	2.4674	220
graphviz	140.5406	234
spectral	117.5004	226
spring	307.1961	225
shell	2.5685	220
circular	2.6359	220

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

Random

Circular and shell

Graphviz

Spectral

Spring