General purpose algorithm for triangulating an undirected graph?

Question

I am playing around with implementing a junction tree algorithm for belief propagation on a Bayesian Network. I'm struggling a bit with triangulating the graph so the junction trees can be formed.

I understand that finding the optimal triangulation is NP-complete, but can you point me to a general purpose algorithm that results in a 'good enough' triangulation for relatively simple Bayesian Networks?

This is a learning exercise (hobby, not homework), so I don't care much about space/time complexity as long as the algorithm results in a triangulated graph given any undirected graph. Ultimately, I'm trying to understand how exact inference algorithms work before I even try doing any sort of approximation.

I'm tinkering in Python using NetworkX, but any pseudo-code description of such an algorithm using typical graph traversal terminology would be valuable.

Thanks!

Answer 1

If Xi is a possible variable (node) to be deleted then,

• S(i) will be the size of the clique created by deleting this variable
• C(i) will be the sum of the size of the cliques of the subgraph given by Xi and its adjacent nodes

Heuristic:

In each case select a variable Xi among the set of possible variables to be deleted with minimal S(i)/C(i)

Reference: Heuristic Algorithms for the Triangulation of Graphs