Я использую Processing для разработки системы навигации по сложным данным и процессам. В рамках этого я довольно глубоко погрузился в компоновку графов. Это все забавно, и мое мнение об алгоритмах компоновки таково: принудительное управление для слабаков (просто посмотрите на его масштаб... ха-ха), проекция собственного вектора — это круто, слои Сугиямы выглядят хорошо, но быстро терпят неудачу на графических графиках, и хотя я полагался на собственных векторах до сих пор мне нужно минимизировать пересечения ребер, чтобы действительно добраться до точки данных. Я знаю, я знаю NP-полный и т.д.
Я должен добавить, что у меня есть некоторый успех в применении упаковки xy и использовании перестановок, подобных Sugiyama, для уменьшения пересечения ребер между строками и столбцами. А именно: граф (| V | = 90, средняя степень log | V |) может перейти от 11000 пересечений -> 1500 (по заключенным в рамку собственным векторам) -> 300 путем чередования перестановок строк и столбцов для уменьшения пересечений.
Но локальные минимумы... что бы это ни было, липнет к этой отметке, и результат не так ясен, как мог бы быть. Мое исследование освещенности подсказывает мне, что я действительно хочу использовать алгоритм планаризации, подобный тому, который они используют для СБИС:
- Используйте BFS или что-то еще, чтобы сделать максимальный планарный подграф 1.a. Красиво расположите планарный подграф
- Умело добавляйте выдающиеся ребра, чтобы восстановить исходный граф
Пожалуйста, ответьте, что вы думаете об самом быстром алгоритме планаризации. Вы можете подробно рассказать о любых конкретных оптимизациях, с которыми вы были знакомы.
Большое спасибо!
