python - Algorithm for generating a tree decomposition

Question

I want to construct a tree decomposition: http://en.wikipedia.org/wiki/Tree_decomposition and I have the chordal graph and a perfect elimination ordering. I am following advice given in a previous thread, namely:

To construct a non-nice (in general) tree decomposition of a chordal graph: find a perfect elimination ordering, enumerate the maximal cliques (the candidates are a vertex and the neighbors that appear after it in the ordering), use each clique as a decomposition node and connect it to the next clique in the ordering that it intersects.

This does not work however and I can not figure out why. Consider the following example:

Perfect elimination ordering:

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

Chordal graph:

Tree decomposition:

I am using python and my current algorithm is the following:

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 the perfect ordering and 'chordal_graph' is a graph object for networkx.

Answer 1

So that was my (bad, as it turns out) advice. Your tree decomposition has some cliques that aren't maximal, i.e., {2, 0, 1}, {0, 1}, and {1}. The list of candidate cliques is

{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 wrong as well, since the 0 vertices aren't connected. Sorry about that.

What I should have done is to set aside the maximality condition for the moment and to connect each clique K to the next candidate seeded with a vertex belonging to K. This ensures that every vertex in K that exists in at least one other subsequent clique also appears in the target of the connection. 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 splice out the non-maximal cliques by checking, for each clique in reverse order, whether it's a superset of its parent, and if so, reparenting its parent's children to it.

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