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?)
źródło
Odpowiedzi:
Obliczenie absolutnej minimalnej liczby przekroczeń jest, jak zauważyłeś,NP-twardy . 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:
Posiada wiele innych funkcji, które mogą się okazać przydatne. Kod źródłowy znajduje się na ich stronie internetowej pod EPL. Zawiera także stronę poświęconą teorii związanej z wizualizacją grafów.
Obliczanie liczb przekraczania w czasie kwadratowym
grafów
Algorytm dla problemu przekroczenia wykresu
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).
źródło