Czy istnieje odpowiedni algorytm do rysowania mieszanego wykresu okręgu / zależności w układzie współrzędnych?

Szukam algorytmu do rysowania mieszanego wykresu okręgów / zależności (dla aplikacji językowych). Taki wykres miałby dwa różne typy wierzchołków (tokeny, węzły) i dwa różne typy krawędzi (hierarchiczne, niehierarchiczne).

Jestem nowy w teorii grafów i algorytmach w ogóle i mam nadzieję, że to pytanie nie koliduje np. Z wymaganiami dotyczącymi tej strony na poziomie badań. Powinien jednak zasadniczo wchodzić w zakres cstheory .

Wykres musiałby być narysowany od dołu (myślę), ponieważ wszystkie tokeny powinny być wyświetlane z tą samą współrzędną y, a współrzędne y węzłów grupujących tokeny i / lub węzły w elementach będą musiały być obliczane dynamicznie, np. najdłuższą drogą do tokena.

Hierarchiczne krawędzie (używane do grupowania tokenów / węzłów w składniki) powinny mieć minimalną liczbę punktów zgięcia (najlepiej 0), ale powinna również istnieć minimalna liczba skrzyżowań, zastępując w razie potrzeby poprzednie wymaganie.

Krawędzie niehierarchiczne (używane w zależnościach) powinny mieć minimalną liczbę skrzyżowań i być rysowane jako krzywe Béziera.

Kolejną najlepszą rzeczą, na jaką się natknąłem, jest algorytm opisany przez Buchheim i in. , ulepszając algorytm Walkera do działania w czasie liniowym.

Daj mi znać, jeśli zaistnieje potrzeba poprawy mojego pytania i z góry dziękuję za wszelkie wskazówki.

EDYTOWAĆ:

Jak wskazano w komentarzu, powinienem wspomnieć, że zasadniczo chcę domyślnego układu graficznego algorytmu, który - na dłuższą metę - chcę edytować i poprawiać w ramach możliwości Eclipse GEF . Wcześniej szukałem opcji, aby Graphviz działał z GEF, ale wydaje się, że nie ma działającego rozwiązania, które zachowałoby wszystkie funkcje edycyjne odziedziczone po GEF.

wydaje się, że chcesz:

• algorytm układu wykresu. w wielu algorytmach std zwykle stosuje się metody oparte na sile, w których węzły są połączone przez sprężyste / atrakcyjne „sprężyny”, a stan równowagi / niskiej energii jest uzyskiwany przez pewien ciąg iteracji (odpowiedniego globalnie skonstruowanego równania różniczkowego związanego z siłą). wyjściem algorytmu jest zestaw współrzędnych 2-d lub 3-d dla węzłów i (zwykle) krawędzi.
• umiejętność ręcznej modyfikacji wyników tego algorytmu. zwykle nazywany „edytorem wykresów”. zaczyna się od współrzędnych z algorytmu układu i umożliwia regulację.

re (1) wydaje się, że głównym oprogramowaniem jest graphviz . re (2) patrz np. to pytanie „jaki jest najlepszy edytor grafów” na mathoverflow .

przeglądając galerię graphviz, oto dwa typy wykresów podobne do tego, co chcesz.

Schemat ER i sygnalizacja świetlna .

mówisz, że masz dwa rodzaje krawędzi. prostym sposobem byłoby skierowanie krawędzi „w stronę lub z dala”, jak w przykładzie sygnalizacji świetlnej. lub krawędzie można opisać na dwa sposoby, jak na schemacie ER. oba przykłady pokazują dwa różne typy węzłów przy użyciu różnych kształtów lub etykiet lub cieniowania itp. Inne podejście polegałoby na zastosowaniu kolorowania.

jak wskazują mathoverflow Q / As, istnieje wiele edytorów grafów. std z grafviz to „dotty”. patrz np. pdf „edycja wykresów z kropkami ” Koutsofiousa.

inną techniką tworzenia wykresów, być może dużych wykresów, jest przyglądanie się kompozycjom strukturalnym, np. rozkładom kliki.