Электрически заряженные ребра в алгоритме рисования графа на основе силы?

Question

Я пытаюсь написать короткую мини-программу на Python, которая работает с силовыми алгоритмами для рисования графиков.

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

Может ли кто-нибудь дать мне подсказку о том, как я могу это сделать?(Или, в качестве альтернативы, другой способ настройки алгоритма рисования графиков на основе силы, чтобы минимизировать количество пересечений линий?) Я просто ищу подсказку;без исходного кода, пожалуйста.

В случае, если кому-то интересно, мой исходный код и youtube vid Я сделал об этом.

Answer 1

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