Jak zmniejszyć liczbę skrzyżowanych krawędzi na schemacie?

10

Pracuję nad edytorem diagramów. Diagramy przedstawiają kształty 2D ( węzły ) połączone ze złączami ( krawędziami ).

Chciałbym dodać operację, która, biorąc pod uwagę wybór węzłów, „rozplątuje” je: zmienia ich położenie, jeśli to możliwe, aby zmniejszyć liczbę przecinających się krawędzi (i jest w porządku, jeśli krawędzie będą musiały być rysowane za pomocą punktów zgięcia) .

Chcę więc algorytmu graficznego, który, biorąc pod uwagę ( topologiczny ) osadzanie wykresu i podzbiór jego węzłów, modyfikuje osadzanie (jego topologię ) tylko na tych węzłach, aby zminimalizować liczbę przecinających się krawędzi.

Czytając o wykresach wierzchołków i przeglądając Cabello i Mohara (2013) , przypuszczam, że ten problem jest trudny do rozwiązania. Będę więc zadowolony ze sparametryzowanego algorytmu (np. Liczby przecinających się krawędzi), który ma znaną wielomianową złożoność czasową dla dowolnej wartości parametru. Wydaje się to wykonalne, ale nie jest mi łatwo wymyślić taki algorytm.

Pytania:

  • Gdzie szukać takiego algorytmu?
  • Czy to istnieje?
  • W istniejącym oprogramowaniu?
  • Czy jest jakieś istotne praktyczne doświadczenie z taką operacją? (To, co w teorii wygląda dobrze, może nie być tak dobre w praktyce lub odwrotnie.)

(Nie jestem pewien, gdzie najlepiej zadać to pytanie: tutaj, na StackOverflow lub MathOverflow?)

reinierpost
źródło
1
Zakładam, że pytanie może lepiej pasować do StackOverflow, ale zauważyłem, że podobne pytania mają niezadowalające odpowiedzi. Postaram się udzielić odpowiedzi, która powinna pomóc ci w teoretycznym zakończeniu, ale może być najlepiej, aby migrować tam twoje pytanie.
mdxn
Trwają tutaj bardzo dogłębne prace: Complang.tuwien.ac.at/cd/ebner/ebner05da.pdf
Dschoni
Dzięki! Poza tym jest to wyraźnie czytelna prezentacja problemu i przegląd niektórych dobrze znanych podejść.
reinierpost

Odpowiedzi:

9

Obliczenie absolutnej minimalnej liczby przekroczeń jest, jak zauważyłeś, NP-hard. Proces rysowania wykresów powinien być co najmniej tak trudny.

Problem postawiony w pytaniu jest w rzeczywistości trudniejszy i bardziej zaangażowany niż powyższe. Rozważasz węzły wykresu o określonym rozmiarze i kształcie, jednocześnie ograniczając rozmiar (obszar) wyniku. Ponadto pożądane jest jeszcze nieokreślone pojęcie estetyki. Oczywiście chcemy do tego heurystyki, która nie wykorzystuje absolutnego minimum w ogólnym przypadku. Liczba węzłów napotkanych w takiej aplikacji prawdopodobnie nie jest duża w przeciętnym przypadku. Rysowanie wersji wykresu z minimalnym przekraczaniem krawędzi może być wykonalne w przypadku małych rozmiarów.

Zasoby:
Mogą Cię zainteresować następujące zasoby, szczególnie pierwsze:

Istnieje również wiele innych zasobów. To powinno ci pomóc zacząć.

Dodatkowe przemyślenia i obserwacje:

Oto pomysł na obejście problemów dotyczących kształtu i wielkości węzłów. Biorąc pod uwagę wykres (nieskończenie małe węzły), rozwiń każdy węzeł, jednocześnie „wypychając” lub zginając krawędzie (np. Używając splajnów, jednocześnie egzekwując ograniczenie odległości). Musisz to zrobić z innymi krawędziami i węzłami, które mu przeszkadzają, co może rozpocząć reakcję łańcuchową. Przyjrzyj się, jak można skutecznie obliczyć równowagę (np. Struktury molekularne). Jeśli nie możesz uzyskać kształtu węzła do żądanego rozmiaru, przeskaluj cały diagram.

Użytkownik może cieszyć się wynikami losowego algorytmu. Mogą używać tej funkcji wiele razy, dopóki nie uzyskają czegoś, co im się podoba. W takim przypadku unikaj nadmiarowych obliczeń (nie musisz ponownie obliczać numeru przecięcia).

mdxn
źródło
Dodałem topologię do mojego pytania, aby uniknąć dyskusji o estetyce. To ważne, ale nie sądzę, aby miały duży wpływ na podstawowy problem - myślę, że można sobie z nimi poradzić w osobnym kroku, po dostosowaniu topologii węzłów (tj. Które węzły są otoczone przez które inne węzły).
reinierpost
Po raz pierwszy użyłem Graphviz ponad 15 lat temu; Używam go mniej więcej raz w tygodniu dla wszystkich rodzajów wykresów. Nie jestem pod wrażeniem jego wyników i rozumiem, że ciężko jest zrobić dużo lepiej.
reinierpost
Często odwiedzam graphviz.org i czytałem niektóre artykuły, do których się odnoszą. Ale nie spotkałem się jeszcze z odpowiedzią na to konkretne pytanie i nie jest w moim opisie pracy zapoznanie się z literaturą. Dlatego pytam o to tutaj.
reinierpost
Dziękuję za referencje - zauważam, że są to wciąż aktualne badania .
reinierpost
Pierwszą rzeczą, której spróbuję, jest trywialny (i dlatego niekoniecznie przydatny) algorytm z grubsza oparty na pomyśle pani Shabbeer. Dzięki jeszcze raz.
reinierpost