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.

ds.algorithms graph-theory graph-algorithms software treewidth 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,

Odpowiedzi:

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∼10kn≤13k≤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≤150

Fasermaler
ź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