Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/graph/check_triangulated.m @ 0:e9a9cd732c1e tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
rev   line source
wolffd@0 1 function [triangulated, order] = check_triangulated(G)
wolffd@0 2 % CHECK_TRIANGULATED Return 1 if G is a triangulated (chordal) graph, 0 otherwise.
wolffd@0 3 % [triangulated, order] = check_triangulated(G)
wolffd@0 4 %
wolffd@0 5 % A numbering alpha is perfect if Nbrs(alpha(i)) intersect {alpha(1)...alpha(i-1)} is complete.
wolffd@0 6 % A graph is triangulated iff it has a perfect numbering.
wolffd@0 7 % The Maximum Cardinality Search algorithm will create such a perfect numbering if possible.
wolffd@0 8 % See Golumbic, "Algorithmic Graph Theory and Perfect Graphs", Cambridge Univ. Press, 1985, p85.
wolffd@0 9 % or Castillo, Gutierrez and Hadi, "Expert systems and probabilistic network models", Springer 1997, p134.
wolffd@0 10
wolffd@0 11
wolffd@0 12 G = setdiag(G, 1);
wolffd@0 13 n = length(G);
wolffd@0 14 order = zeros(1,n);
wolffd@0 15 triangulated = 1;
wolffd@0 16 numbered = [1];
wolffd@0 17 order(1) = 1;
wolffd@0 18 for i=2:n
wolffd@0 19 U = mysetdiff(1:n, numbered); % unnumbered nodes
wolffd@0 20 score = zeros(1, length(U));
wolffd@0 21 for ui=1:length(U)
wolffd@0 22 u = U(ui);
wolffd@0 23 score(ui) = length(myintersect(neighbors(G, u), numbered));
wolffd@0 24 end
wolffd@0 25 u = U(argmax(score));
wolffd@0 26 numbered = [numbered u];
wolffd@0 27 order(i) = u;
wolffd@0 28 nns = myintersect(neighbors(G,u), order(1:i-1)); % numbered neighbors
wolffd@0 29 if ~isequal(G(nns,nns), ones(length(nns))) % ~complete(G(nns,nns))
wolffd@0 30 triangulated = 0;
wolffd@0 31 break;
wolffd@0 32 end
wolffd@0 33 end
wolffd@0 34