Автоматически вращать график

Question

Я рисую графики с помощью принудительного макета, и проблема состоит в том, что созданные графики ориентированы случайным образом и непредсказуемо, что делает их с толку. Например, предположим, что узел A является членом двух отдельных графов G1 и G2. С принудительным макетом узел A может оказаться на левой стороне G1, но с правой стороны G2.

Теперь я пытаюсь уменьшить путаницу, автоматически вращая график детерминированным способом после того, как алгоритм макета графика был нанесен на него. Можно вычислить Минимальный ограничивающий прямоугольник Для этого, но было бы лучше, если алгоритм вращения может включать в себя некоторые дополнительные данные на вершины и края.

В этом случае каждая вершина представляет собой документ с временем временем и подсчетом слов, а кромки представляют неопроверженные и направленные отношения между документами. Возможно, есть способ повернуть график, так что более старые документы сосредоточены на левом и новее справа? То же самое со ссылками: стрелки должны указывать вправо, чем влево. Это звучит как разумный подход, но я понятия не имею, как рассчитать что-то вроде этого (и Google действительно не помогал).

Примечания:

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

Answer 1

Вы можете либо использовать

• Динамический, направленный на силу алгоритм, который сохраняет ментальную карту пользователя между кадрами (например, рисунок графов в движении, в журнале алгоритмов и приложений графика (JGAA), 6 (3), 353--370, 2002) или
• Прокруст анализ Перевести, вращать и масштабировать кадры так, чтобы относительные позиции «базовых баллов» сохранены.

Answer 2

Вы можете использовать макет, который использует семена для генерации случайных чисел. Попробуйте Yifan Hu MultiLevel Algorithm в Гефир.