Теория графов - основанный на силе алгоритм автоматического размещения

Question

Просто хочу проверить, правильно ли я изложил свою теорию, прежде чем начать реализацию.

Константа:

• m = масса вершины (все то же самое - возможно, установите это значение для радиуса узла)
• k = постоянная сила края.
• l = длина ребра в «минимальном состоянии энергии».

Переменные:

• d = расстояние между двумя вершинами.
• cl = текущая длина края.

Теория: Каждая вершина имеет силу отталкивания на каждой другой вершине, которая: m / (d^2). Для каждого ребра он демонстрирует силу, с которой обе вершины «тянут» их в направлении, чтобы получить ребро до «минимального энергетического состояния»; Итак, каждая вершина: -k * ((l - cl) / 2).

псевдокод:

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

Комментарии: Так будет ли это работать? Что я должен установить m и k?

Answer 1

Вы на правильных линиях.Ваша терминология / физика немного не совпадают: то, что вы называете массой, а «k» вроде как все смешивается с тем, что лучше назвать «зарядом» (для закона обратного квадрата отталкивания) и «пружинной константой» дляЗакон притяжения Гука.

Как отмечается в комментариях к ответам на ваш вопрос, вам действительно необходимо некоторое демпфирование, которое фактически забирает энергию из системы, иначе она будет просто колебаться, превращая потенциальную энергию в кинетическую энергию и обратно навсегда.Хуже того, проблемы точности симуляции могут легко привести к бесконечному увеличению энергии, и симуляция «сходит с ума», если вы не будете осторожны.очень похоже на ваше, но с учетом вышеупомянутых пунктов (хотя обратите внимание, что даже в этом псевдокоде не хватает деления по массе в расчете ускорения; см. обсуждение на странице).

Вам также нужно немного подуматьо начальном распределении, с которого вы начнете моделирование, и о том, насколько вам небезразлична возможность застрять в локальном минимуме, если существует (возможно) гораздо лучший глобальный минимум.Эти пункты связаны между собой;многое зависит от топологии вашего графа.Если это простое дерево, у вас не будет проблем с получением хорошего макета.Если у него много петель и структуры ... удачи.

Answer 2

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

Понятия не имею к.