Есть ли подходящий алгоритм для рисования смешанного графа постоянных / зависимостей в системе координат?

9

Я ищу алгоритм для рисования смешанного графа групп интересов / зависимостей (для лингвистического приложения). Такой граф будет иметь два разных типа вершин (токены, узлы) и два разных типа ребер (иерархические, неиерархические).

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

График должен быть нарисован снизу вверх (я думаю), так как все токены должны отображаться с одинаковыми координатами y, а координаты y узлов, группирующих токены и / или узлы в составляющие, должны рассчитываться динамически, например, через их самый длинный путь к токену.

Иерархические ребра (используемые для группировки токенов / узлов в составляющие) должны иметь минимальное количество точек сгиба (в идеале 0), но также должно быть минимальное количество пересечений, перезаписывая прежнее требование, если это необходимо.

Неиерархические ребра (используемые для зависимостей) должны иметь минимальное количество пересечений и быть нарисованы в виде кривых Безье.

Следующая лучшая вещь, с которой я столкнулся, - это алгоритм, описанный Buchheim et al. , улучшая алгоритм Уокера для запуска в линейное время.

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

РЕДАКТИРОВАТЬ:

Как отмечено в комментарии, я должен упомянуть, что я в основном хочу макет графика по умолчанию с помощью алгоритма, который я - в конечном счете - хочу редактировать и пересматривать в рамках возможностей Eclipse GEF . Ранее я рассматривал варианты, чтобы заставить Graphviz работать с GEF, но, похоже, не существует рабочего решения, которое сохранило бы все функциональные возможности редактирования, унаследованные от GEF.

ds.algorithms graph-algorithms cg.comp-geom graph-drawing SD
источник
Вам нужен алгоритм или существующий инструмент? Graphviz ( graphviz.org ) может сделать это. Вы указываете граф, возможно, некоторые параметры форматирования (для разных видов узлов и ребер), и инструмент выводит разумно визуализированный граф.
Дэйв Кларк,
@DaveClarke: Спасибо. Я знаю, что Graphviz может это сделать. К сожалению, похоже, что в настоящее время нет возможности использовать Graphviz с редактором, основанным на [Eclipse Graphical Editing Framework] (www.eclipse.org/gef). Поэтому я ищу фактический алгоритм. Если, конечно, кто-нибудь знает, как подключить / портировать Graphviz в GEF :).
сд
Похоже, что ОП ищет алгоритм (или формулировку проблемы, которая отражает спецификацию)
Суреш Венкат
@SureshVenkat: Да, спасибо за разъяснения.
сд
1
В Q нет упоминаний о редактировании, но в комментарии вы выключаете graphviz и, похоже, указываете, что хотите редактировать его с помощью GEF. GEF - это общая среда визуального редактирования / API, на которой могут основываться другие "плагины". Похоже, вы хотите макет графика по умолчанию с помощью алгоритма, который вы затем можете пересмотреть. предлагаю вам отредактировать свой вопрос, чтобы отразить это. кстати, верьте, что graphviz можно использовать для генерации координат, которые затем можно подавать в редактор графиков.
Относительно

Ответы:

1

Вы, кажется, хотите следующее

  • алгоритм построения графика. во многих стандартных алгоритмах обычно используются методы, основанные на силе, в которых узлы соединяются притягивающими / притягивающими «пружинами», а состояние равновесия / низкоэнергетического состояния получается посредством некоторого количества итераций (соответствующего глобально построенного дифференциального уравнения, связанного с силой). Результатом работы алгоритма является набор 2-х или 3-х координат для узлов и (обычно) ребер.
  • способность вручную изменять результаты этого алгоритма. обычно называется «редактор графиков». это начинается с координат из алгоритма расположения и позволяет регулировку.

По-видимому, (1) передовое программное обеспечение выглядит графически . re (2) см., например, этот вопрос «какой редактор графов лучше» на mathoverflow .

просматривая галерею graphviz, вы увидите два типа графиков, аналогичных тем, которые вы хотите.

Диаграмма ER и светофор .

Вы говорите, у вас есть два типа ребер. простой способ состоит в том, чтобы направлять края «в направлении или в сторону», как в примере со светофором. или края могут быть помечены двумя способами, как на диаграмме ER. В обоих примерах показаны два разных типа узлов с использованием разных форм или меток, или затенения и т. д. Другие подходы заключаются в использовании окраски.

как показывают mathoverflow Q / As, существует много графических редакторов. STD с Graphviz является "dotty". см., например, pdf "Редактирование графиков с помощью dotty" от Koutsofious.

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

ВЗН
источник