Wdrożony kod do obliczania szerokości ścieżki (= numer wyszukiwania węzła, numer separacji wierzchołków, grubość przedziału)

13

Szukam implementacji algorytmu do obliczania szerokości ścieżki wykresu. Dobrze wiadomo, że obliczenie szerokości ścieżki jest równoważne z obliczeniem numeru wyszukiwania węzła, numeru separacji wierzchołków lub grubości przedziału wykresu. Algorytm nie musi być bardzo szybki; Chcę uruchomić go na wykresach o maksymalnie 20 wierzchołkach. Wymagam od algorytmu dokładnego obliczenia szerokości ścieżki, a nie przybliżenia.

Wiem, że istnieją pewne implementacje do obliczania szerokości wykresu (koncepcja pokrewna), ale nie udało się znaleźć żadnej do obliczenia szerokości ścieżki. Wszelkie wskazówki są mile widziane!

— Bart Jansen
źródło

8

Prosta implementacja DFS + DP została dodana do SAGE 4.8 w zeszłym roku: sage.graphs.graph_decompositions.vertex_separation.path_decomposition

Jest zaimplementowany w Cython (GNU GPL) tu i tutaj . Bardzo proste i krótkie, jeśli zignorujesz wszystko, co nie jest niezbędne. czas, gdzie . Można to przyspieszyć dzięki regułom przycinania, a zwłaszcza heurystyce. $O(n\omega 2^n)$ $\omega = pw(G)$

— Ralph Versteegen
źródło

Wouaaaaaaaaahhhh !! Jak dowiedziałeś się, że został dodany do Sage? Miło widzieć, jak ludzie naprawdę wyglądają, jakie są nowe funkcje Sage'a :-)

— Nathann Cohen

Nawiasem mówiąc, dokumentacja modułu jest właśnie tam i wyjaśnia, jak to wszystko działa: sagemath.org/doc/reference/sage/graphs/graph_decompositions/...

— Nathann Cohen

Przepraszam za rozczarowanie, ale tak naprawdę nie jestem użytkownikiem SAGE; Google odkryło, że Twoja poprawka się do niego przyczyniła. Chciałbym przyczynić się do SAGE (już używam Cython), ale wydaje mi się, że lepiej byłoby uczestniczyć w projektach upstream (NetworkX?), W których więcej osób mogłoby z niego korzystać.

— Ralph Versteegen

Dobrze. NetworkX nie jest już tak naprawdę „upstream” z Sage, ponieważ tak naprawdę nie używa NetworkX, chyba że o to poprosisz. I możliwość korzystania z innych części matematyki, Cython i interfejs z programowaniem liniowym również robi różnicę :-P

— Nathann Cohen

8

Nie wiem o „implementacji”, ale sprawdź

Obliczanie przepustowości szybciej niż 2 ^ n Karol Suchan i Yngve Villanger sparametryzowane i dokładne obliczenia, 4. międzynarodowe warsztaty, IWPEC 2009, Kopenhaga, Dania, Springer Verlag, Uwagi do wykładu z informatyki 5917, strony 324-335.

— Andreas Björklund
źródło

2

Hisao Tamaki opracował niedawno dokładny algorytm dla ukierunkowanej przepustowości (WG 2011). Tam nawiązuje do udanego praktycznego zastosowania swojego podejścia (ISCIT 2010), więc sądzę, że ma również implementację algorytmu.

Hisao Tamaki: Ukierunkowane podejście do rozkładu ścieżki do dokładnej identyfikacji atraktorów sieci boolowskich. Międzynarodowe sympozjum nt. Technologii komunikacyjnych i informacyjnych (ISCIT 2010), s. 844–849

Hisao Tamaki: algorytm wielomianu czasu dla ograniczonej ukierunkowanej ścieżki. W: 37. międzynarodowe warsztaty nt. Koncepcji teoretyczno-graficznych w informatyce (WG 2011), LNCS 6986, s. 331–342.

— Hermann Gruber
źródło