Алгоритм Камада-Кавай

Алгоритм Камада-Кавай (T. Kamada-S. Kawai)) относится к семейству силовых алгоритмов (forced-directed) укладки графов на плоскости, в котором используется пружинная физическая модель, где вершины определяются как тела системы, а ребра как пружины. Силы могут действовать только на вершины, вес пружин при этом не учитывается.

Постановка задачи

Имеется простой неориентированный граф $G=(V,E)$. У каждой вершины из множества $V$ в качестве переменных используются координаты ее размещения $V_x$ и $V_y$, а также $V_f$ - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы, меняя расположение вершин. Результатом алгоритма будет наглядное изображение графа на плоскости.

Описание алгоритма

1. Рассчитываются расстояния по графу между всеми вершинами
2. Вершины графа помещаются в случайные координаты
3. Выбирается вершина $p_i$, на которую действует максимальная сила
4. Остальные вершины фиксируются, энергия системы минимизируется
5. Повторяются шаги 3-4

Алгоритм не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций.

Описание модели

$d_{ij}$ - длина кратчайшего пути между вершинами i и j

$l_{ij}=L\ast d_{ij}$ - длина пружины между вершинами i и j

$k_{ij}=K/d_{ij}^2$ - сила пружины между вершинами i и j

Функция энергии

$E_{KK}=\sum _{i=1}^{n-1}\sum _{j=i+1}^n\frac{1}{2}{k}_{ij}(||p_i-p_j||-l_{ij}{)}^2$

Свойства

Алгоритм является вычислительно затратным, так как для расчета кратчайших путей между вершинами требует $O(|V{|}^3)$ времени

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

Демонстрация

Литература

1. Kamada T., Kawai S. An algorithm for drawing general undirected graphs. Information Processing Letters. – 1989. – Vol. 31, N 1. – pp. 7–15.