История изменений
Исправление Sadler, (текущая версия) :
пружинная сеть? :)
Ну, это силовой алгоритм, да, но у классического силового алгоритма сложность O(N^2), что не очень приятно. Я расчитываю только притяжение по связанным вершинам, силами отталкивания занимается простой клеточный автомат, сдвигающий вершину по сетке, если она расположена близко к другим вершинам. Получается такая своеобразная карта. Есть ещё несколько аспектов, позволяющих улучшить сходимость, но не суть. Если сетка достаточно большая, то этот алгоритм Graph Layout работает очень быстро с приемлемой точностью. Я года два назад писал статью об этом в рецензируемый журнал.
Из неудобств: 1) приходится держать карту в памяти, а она бывает достаточно большой; 2) алгоритм сильно зависит от связности графа. Заметное ускорение даёт лишь при связности << числа вершин графа. Для википедии вполне подходит.
Исправление Sadler, :
пружинная сеть? :)
Ну, это силовой алгоритм, да, но у классического силового алгоритма сложность O(N^2), что не очень приятно. Я расчитываю только притяжение по связанным вершинам, силами отталкивания занимается простой клеточный автомат, сдвигающий вершину по сетке, если она расположена близко к другим вершинам. Получается такая своеобразная карта. Есть ещё несколько аспектов, позволяющих улучшить сходимость, но не суть. Если сетка достаточно большая, то этот алгоритм Graph Layout работает очень быстро с приемлемой точностью. Я года два назад писал статью об этом в рецензируемый журнал.
Исходная версия Sadler, :
пружинная сеть? :)
Ну, это силовой алгоритм, да, но у классического силового алгоритма сложность O(N^2), что не очень приятно. Я расчитываю только притяжение по связанным вершинам, силами отталкивания занимается простой клеточный автомат, сдвигающий вершину по сетке, если она расположена близко к другим вершинам. Получается такая своеобразная карта. Если сетка достаточно большая, то этот алгоритм Graph Layout работает очень быстро с приемлемой точностью. Я года два назад писал статью об этом в рецензируемый журнал.