Algorytm generowania dekompozycji drzewa

Question

Chcę zbudować rozkład drzewa: http://en.wikipedia.org/wiki/Tree_decomposition i mam wykres wykresu oraz doskonałe uporządkowanie eliminacji. Śledzę zaleceń podanych w previous thread, mianowicie:

skonstruować non-nice (ogólnie) Drzewo dekompozycji na cięciwy wykresie: znaleźć idealne eliminacji zamawianie, wyliczyć maksymalne klik (kandydatów są wierzchołkami i sąsiadami, które pojawiają się po zamówieniu w postaci ), użyj każdej kliki jako węzła dekompozycji, a następnie podłącz ją do następnej kliki w kolejności, w której się przecina.

To nie działa jednak i nie mogę zrozumieć dlaczego. Rozważmy następujący przykład:

Doskonała eliminacja Kolejność:

['4', '3', '5', '7', '6', '2', '0', '1'] 

cięciwy wykres:

Drzewo dekompozycji:

używam python i mój obecny algorytm jest następujący:

T=nx.Graph() 
    nodelist=[] 
    for i in eo: 
     vertex=str(i) 
     bag=set() 
     bag.add(vertex) 
     for j in chordal_graph.neighbors(str(i)): 
      bag.add(str(j)) 
     T.add_node(frozenset(bag)) 
     nodelist.append(frozenset(bag)) 
     chordal_graph.remove_node(str(i)) 
    for node1 in range(len(nodelist)): 
     found=False 
     for node2 in range(node1+1,len(nodelist)): 
      if found==False and len(nodelist[node1].intersection(nodelist[node2]))>0: 
       T.add_edge(nodelist[node1],nodelist[node2]) 
       found=True 
    nx.draw(T) 
    p.show()  

gdzie eo jest lista doskonałego uporządkowania i „chordal_graph” jest obiektem wykres dla networkx.

Answer 1

To była moja (zła, jak się okazuje) rada. Dekompozycja drzewa ma kilka kliknięć, które nie są maksymalne, tj. {2, 0, 1}, {0, 1} i {1}. Lista klik kandydat

{4, 5, 6} (maximal) 
{3, 2} (maximal) 
{5, 6, 2, 0} (maximal) 
{7, 2, 1} (maximal) 
{6, 2, 0, 1} (maximal) 
{2, 0, 1} (not maximal: subset of {6, 2, 0, 1}) 
{0, 1} (not maximal: subset of {6, 2, 0, 1}) 
{1} (not maximal: subset of {6, 2, 0, 1}) 

Wówczas rozkład powinien wyglądać

   {3, 2} 
        | 
{4, 5, 6}----{5, 6, 2, 0} 
        | 
      {7, 2, 1} 
        | 
      {6, 2, 0, 1}, 

co jest źle, jak dobrze, ponieważ 0 wierzchołki nie są połączone. Przepraszam za to.

Co powinienem zrobić, to odłożyć na bok warunek maksymalności na chwilę i połączyć każdą klikę K z kolejnym kandydatem obsadzonym wierzchołkiem należącym do K. Zapewni to, że każdy wierzchołek w K, który istnieje w co najmniej jednym inna kolejna klika pojawia się również w celu połączenia. Wtedy dekompozycja wygląda to

{4, 5, 6}----{5, 6, 2, 0} 
        | 
      {6, 2, 0, 1} 
        | 
    {3, 2}----{2, 0, 1}----{7, 2, 1} 
        | 
       {0, 1} 
        | 
       {1} 

i można splatać się z non-maksymalnych klik poprzez sprawdzenie, dla każdego kliki w odwrotnej kolejności, czy jest rozszerzeniem jego rodzica, a jeśli tak, reparenting dzieci swojego rodzica do to.

{4, 5, 6}----{5, 6, 2, 0} 
        | 
    {3, 2}----{6, 2, 0, 1}----{7, 2, 1}