Чтобы упростить задачу, у меня есть граф, содержащий узлы и ребра, которые находятся на 2D-плоскости.
То, что я хочу сделать, - это нажать кнопку, и это автоматически сделает график, чтобы выглядеть чистым. Под этим я подразумеваю минимальное пересечение ребер, хорошее пространство между узлами, возможно, даже представляют собой шкалу графа (взвешенные ребра).
Я знаю, что это полностью субъективно, что является чистым графиком, но знает ли кто-нибудь об алгоритме для начала, а не о том, чтобы изобретать колесо?
Спасибо.
Я бы посоветовал вам взглянуть на graphviz. Программа dot может принимать спецификацию графика и генерировать изображение сети для вас несколько "чисто". Ссылка "теория" на этой странице дает вам некоторые ссылки, которые могут иметь значение, если вас интересует теоретический фон.
Вы найдете http://graphdrawing.org/ и этот учебник Роберто Тамассиа, профессора Браунского университета, весьма полезен.
Мне очень нравятся методы Force-Directed (стр. 66-72 в учебнике), например Spring Embedder.
Вы предполагаете, что между любыми двумя соседними узлами есть пружина или другая сила, и пусть природа (симуляция) выполняет работу :)
Также JGraph, если вы хотите, чтобы макеты в Java (я работаю над проектом).
Я бы сказал, как Нуфаль Ибрагим, но вы также можете более точно посмотреть на API C graphviz. Он включает в себя lib для построения вашего графика (libgraph.pdf) со всеми узлами и ребрами, а lib для компоновки графика (libgvc.pdf) (просто вычислите позицию каждого узла), поэтому вы можете отобразить его в своем собственном пользовательском интерфейсе, например.
Хорошее визуальное руководство, как выглядят наиболее популярные макеты: следуйте ссылке