|
wolffd@0
|
1 function [G, cliques, fill_ins] = triangulate(G, order)
|
|
wolffd@0
|
2 % TRIANGULATE Ensure G is triangulated (chordal), i.e., every cycle of length > 3 has a chord.
|
|
wolffd@0
|
3 % [G, cliques, fill_ins, cliques_containing_node] = triangulate(G, order)
|
|
wolffd@0
|
4 %
|
|
wolffd@0
|
5 % cliques{i} is the i'th maximal complete subgraph of the triangulated graph.
|
|
wolffd@0
|
6 % fill_ins(i,j) = 1 iff we add a fill-in arc between i and j.
|
|
wolffd@0
|
7 %
|
|
wolffd@0
|
8 % To find the maximal cliques, we save each induced cluster (created by adding connecting
|
|
wolffd@0
|
9 % neighbors) that is not a subset of any previously saved cluster. (A cluster is a complete,
|
|
wolffd@0
|
10 % but not necessarily maximal, set of nodes.)
|
|
wolffd@0
|
11
|
|
wolffd@0
|
12 MG = G;
|
|
wolffd@0
|
13 n = length(G);
|
|
wolffd@0
|
14 eliminated = zeros(1,n);
|
|
wolffd@0
|
15 cliques = {};
|
|
wolffd@0
|
16 for i=1:n
|
|
wolffd@0
|
17 u = order(i);
|
|
wolffd@0
|
18 U = find(~eliminated); % uneliminated
|
|
wolffd@0
|
19 nodes = myintersect(neighbors(G,u), U); % look up neighbors in the partially filled-in graph
|
|
wolffd@0
|
20 nodes = myunion(nodes, u); % the clique will always contain at least u
|
|
wolffd@0
|
21 G(nodes,nodes) = 1; % make them all connected to each other
|
|
wolffd@0
|
22 G = setdiag(G,0);
|
|
wolffd@0
|
23 eliminated(u) = 1;
|
|
wolffd@0
|
24
|
|
wolffd@0
|
25 exclude = 0;
|
|
wolffd@0
|
26 for c=1:length(cliques)
|
|
wolffd@0
|
27 if mysubset(nodes,cliques{c}) % not maximal
|
|
wolffd@0
|
28 exclude = 1;
|
|
wolffd@0
|
29 break;
|
|
wolffd@0
|
30 end
|
|
wolffd@0
|
31 end
|
|
wolffd@0
|
32 if ~exclude
|
|
wolffd@0
|
33 cnum = length(cliques)+1;
|
|
wolffd@0
|
34 cliques{cnum} = nodes;
|
|
wolffd@0
|
35 end
|
|
wolffd@0
|
36 end
|
|
wolffd@0
|
37
|
|
wolffd@0
|
38 fill_ins = sparse(triu(max(0, G - MG), 1));
|
|
wolffd@0
|
39
|
|
wolffd@0
|
40 %assert(check_triangulated(G)); % takes 72% of the time!
|
|
wolffd@0
|
41
|
|
wolffd@0
|
42
|
