Tree Shredding Generation Algorithm

Question

I want to build a tree decomposition: http://en.wikipedia.org/wiki/Tree_decomposition , and I have a chordal graph and an ideal sort order. I follow the tips given in the previous thread , namely:

To build a fuzzy (generally) tree-like decomposition of a chordal graph: find the ideal ordering order, list the maximum clicks (candidates are the vertex and neighbors that appear after that in ordering order), use each click as a node decomposition and connect it to the next click in the order of its intersection.

However, this does not work, and I cannot understand why. Consider the following example:

Perfect ordering:

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

Chord chart:

Tree decomposition:

I am using python and my current algorithm is as follows:

 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() 

where eo is a list of perfect ordering, and 'chordal_graph' is a graph object for networkx .

Answer 1

So, that was my (bad, as it turns out) advice. There are some clicks in your tree expansion that are not maximal, i.e. {2, 0, 1}, {0, 1} and {1}. Candidate click list

 {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}) 

Then the decomposition should look like

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

which is also incorrect, since 0 vertices are not connected. Excuse me.

What I had to do was to postpone the maximality condition for the moment and connect each clique K to the next candidate, seeded with a vertex belonging to K. This ensures that every vertex in K existing in at least one other subsequent a click also appears at the connection target. Then the decomposition looks like this:

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

and you can splicing non-maximal clicks by checking for each click in reverse order whether this is a superset of your parent, and if so, re-educating its parent children.

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