Trianglulate a graph

Triangulation ensures a graph G is triangulated (chordal), i.e., every cycle of length > 3 has a chord. During the process, we can also find maximal cliques in the triangulated graph.

Pseudo code:

// G is moralized.
triangulate(G, order):
1. eliminated = {}
2. cliques = {}
3. for i = 1 : n
       u = order(i)
       nodes = neighbors of u which are not eliminated yet \(\cup\) u
       make every node in nodes all connected to each other
       add u to eliminated
       check whether nodes is a subset of any clique already found, if not, add nodes to cliques.