Алгоритм авторазметки графика

Question

Чтобы упростить задачу, у меня есть график, который содержит узлы и ребра, которые находятся на 2D-плоскости.

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

Я знаю, что это совершенно субъективно по сравнению с чистым графиком, но кто-нибудь знает алгоритм, с которого нужно начинать, а не изобретать велосипед?

Спасибо.

Answer 1

Вы найдете http://graphdrawing.org/ и этот урок от Роберто Тамассия , профессор из Университета Брауна, весьма полезным.

Мне очень нравятся техники с направленной силой (стр. 66-72 в учебнике), например Spring Embedder .

Вы предполагаете, что между любыми двумя соседними узлами существует пружина или другая сила, и пусть природа (симуляция) выполняет работу:)

Answer 2

Я бы посоветовал вам взглянуть на graphviz .Программа dot может взять спецификацию графика и сгенерировать образ сети для вас несколько «чисто».Ссылка «теория» на этой странице дает вам несколько ссылок, которые могут быть полезны, если вам интересны теоретические знания.

Answer 3

Также JGraph , если вы хотите макеты на Java (я работаю над проектом).

Answer 4

Я бы сказал, как Нуфал Ибрагим, но вы также могли бы более точно взглянуть на C API проекта graphviz . Он включает в себя библиотеку для построения вашего графа ( libgraph.pdf ) со всеми узлами и ребрами и библиотеку для компоновки графа ( libgvc.pdf ) (просто вычислите положение каждого узла ), так что вы можете отобразить его в своем собственном интерфейсе, например.

Answer 5

Хорошее визуальное руководство, как на самом деле выглядят самые популярные макеты: перейдите по ссылке