diff toolboxes/FullBNT-1.0.7/graph/triangulate.m @ 0:e9a9cd732c1e tip

first hg version after svn

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/toolboxes/FullBNT-1.0.7/graph/triangulate.m	Tue Feb 10 15:05:51 2015 +0000
@@ -0,0 +1,42 @@
+function [G, cliques, fill_ins] = triangulate(G, order)
+% TRIANGULATE Ensure G is triangulated (chordal), i.e., every cycle of length > 3 has a chord.
+% [G, cliques, fill_ins, cliques_containing_node] = triangulate(G, order)
+% 
+% cliques{i} is the i'th maximal complete subgraph of the triangulated graph.
+% fill_ins(i,j) = 1 iff we add a fill-in arc between i and j.
+%
+% To find the maximal cliques, we save each induced cluster (created by adding connecting
+% neighbors) that is not a subset of any previously saved cluster. (A cluster is a complete,
+% but not necessarily maximal, set of nodes.)
+
+MG = G;
+n = length(G);
+eliminated = zeros(1,n);
+cliques = {};
+for i=1:n
+  u = order(i);
+  U = find(~eliminated); % uneliminated
+  nodes = myintersect(neighbors(G,u), U); % look up neighbors in the partially filled-in graph
+  nodes = myunion(nodes, u); % the clique will always contain at least u
+  G(nodes,nodes) = 1; % make them all connected to each other
+  G = setdiag(G,0);  
+  eliminated(u) = 1;
+  
+  exclude = 0;
+  for c=1:length(cliques)
+    if mysubset(nodes,cliques{c}) % not maximal
+      exclude = 1;
+      break;
+    end
+  end
+  if ~exclude
+    cnum = length(cliques)+1;
+    cliques{cnum} = nodes;
+  end
+end
+
+fill_ins = sparse(triu(max(0, G - MG), 1));
+
+%assert(check_triangulated(G)); % takes 72% of the time!
+
+