Program do obliczania rozkładu drzewa na wykresie

22

Czy ktoś wie o otwartym oprogramowaniu do obliczania rozkładu drzewa grafów dla ustalonej „k” (szerokość)? Wiem, że problem ze znalezieniem rozkładu drzewa jest trudny NP dla zmiennej „k”, ale moje instancje wejściowe będą naprawdę małe (~ 10 węzłów), a „k” jest naprawione.

— Kaveh
źródło

1

Meta dyskusja: meta.cstheory.stackexchange.com/questions/1101/… . Przed opublikowaniem jakichkolwiek odpowiedzi odwiedź stronę meta - pytam, czy to pytanie ma zakres, czy nie.

— Suresh Venkat,

22

Niektóre z tych programów mogą ci pomóc. (Nie wszystkie z nich są jednak typu open source).

* TreeD http://www.itu.dk/people/sathi/treed/

* dlib http://dlib.net/

* QuickBB http://www.cs.washington.edu/homes/vgogate/quickbb.html

* Hypertree http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html

* LibTW http://www.treewidth.com/treewidth/

— Snowie
źródło

Nie widzę znaczenia dlib; Algorytm łączenia drzewa w sieci Bayesa jest związany z szerokością, ale wydaje się, że ta implementacja nie pomaga w obliczeniu rozkładu drzewa. Przydałby się także drzewkoDuomp Radu Marinescu: graphmod.ics.uci.edu/group/treeDecomp

— András Salamon

3

Funkcja tworzenia drzewa łączenia w dlib pobiera wykres i zwraca rozkład drzewa.

— Davis King,

@Davis: Dzięki za wyraźny wskaźnik, przegapiłem to w dokumentacji.

— András Salamon

1

Link do LibTW przekierowuje do autorskiej (holenderskiej) firmy konsultingowej. Czy jest nowy adres URL?

— Jeffε

7

$n \sim 10$ $k$ $n \leq 13$ $k \leq 4$

Ma około 170 linii kodu i jest to GPL (lub MIT, BSD lub cokolwiek, czego potrzebujesz).

— Pål GD
źródło

5

$n\le150$

— Fasermaler
źródło

5

LibTW wciąż można znaleźć. Jest na http://www.treewidth.com/treewidth/ .

— Mathijs
źródło

1

Być może zainteresują Cię również bardziej nowoczesne algorytmy FlowCutter ( GitHub ) oraz algorytmy Tamaki i in. ( GitHub )

— delete000
źródło