Алгоритм Камада-Кавай
Алгоритм Камада-Кавай (T. Kamada-S. Kawai)) относится к семейству силовых алгоритмов (forced-directed) укладки графов на плоскости, в котором используется пружинная физическая модель, где вершины определяются как тела системы, а ребра как пружины. Силы могут действовать только на вершины, вес пружин при этом не учитывается.
Постановка задачи
Имеется простой неориентированный граф [math]\displaystyle{ G = (V, E) }[/math]. У каждой вершины из множества [math]\displaystyle{ V }[/math] в качестве переменных используются координаты ее размещения [math]\displaystyle{ V_x }[/math] и [math]\displaystyle{ V_y }[/math], а также [math]\displaystyle{ V_f }[/math] - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы, меняя расположение вершин. Результатом алгоритма будет наглядное изображение графа на плоскости.
Описание алгоритма
- Рассчитываются расстояния по графу между всеми вершинами
- Вершины графа помещаются в случайные координаты
- Выбирается вершина [math]\displaystyle{ p_i }[/math], на которую действует максимальная сила
- Остальные вершины фиксируются, энергия системы минимизируется
- Повторяются шаги 3-4
Алгоритм не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций.
Описание модели
[math]\displaystyle{ d_{ij} }[/math] - длина кратчайшего пути между вершинами i и j
[math]\displaystyle{ l_{ij} = L * d_{ij} }[/math] - длина пружины между вершинами i и j
[math]\displaystyle{ k_{ij} = K/d_{ij}^2 }[/math] - сила пружины между вершинами i и j
Функция энергии
[math]\displaystyle{ E_{KK} = \sum_{i=1}^{n-1}{\sum_{j=i+1}^{n} {\frac{1}{2}}k_{ij}(||p_i-p_j|| - l_{ij})^2} }[/math]
Свойства
Алгоритм является вычислительно затратным, так как для расчета кратчайших путей между вершинами требует [math]\displaystyle{ O(|V|^3) }[/math] времени
Также алгоритму требуется более 100 итераций для получения хорошего результата, что делает его неэффективным для применения на больших графах
Демонстрация
Литература
- Kamada T., Kawai S. An algorithm for drawing general undirected graphs. Information Processing Letters. – 1989. – Vol. 31, N 1. – pp. 7–15.