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!

ds.algorithms reference-request graph-algorithms implementation Bart Jansen
źródło

Odpowiedzi:

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ω2n)ω=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