diff options
Diffstat (limited to 'sourcecodes/bnt-master/graph/check_triangulated.m')
| -rw-r--r-- | sourcecodes/bnt-master/graph/check_triangulated.m | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/graph/check_triangulated.m b/sourcecodes/bnt-master/graph/check_triangulated.m new file mode 100644 index 00000000..99bcc9f1 --- /dev/null +++ b/sourcecodes/bnt-master/graph/check_triangulated.m @@ -0,0 +1,34 @@ +function [triangulated, order] = check_triangulated(G) +% CHECK_TRIANGULATED Return 1 if G is a triangulated (chordal) graph, 0 otherwise. +% [triangulated, order] = check_triangulated(G) +% +% A numbering alpha is perfect if Nbrs(alpha(i)) intersect {alpha(1)...alpha(i-1)} is complete. +% A graph is triangulated iff it has a perfect numbering. +% The Maximum Cardinality Search algorithm will create such a perfect numbering if possible. +% See Golumbic, "Algorithmic Graph Theory and Perfect Graphs", Cambridge Univ. Press, 1985, p85. +% or Castillo, Gutierrez and Hadi, "Expert systems and probabilistic network models", Springer 1997, p134. + + +G = setdiag(G, 1); +n = length(G); +order = zeros(1,n); +triangulated = 1; +numbered = [1]; +order(1) = 1; +for i=2:n + U = mysetdiff(1:n, numbered); % unnumbered nodes + score = zeros(1, length(U)); + for ui=1:length(U) + u = U(ui); + score(ui) = length(myintersect(neighbors(G, u), numbered)); + end + u = U(argmax(score)); + numbered = [numbered u]; + order(i) = u; + nns = myintersect(neighbors(G,u), order(1:i-1)); % numbered neighbors + if ~isequal(G(nns,nns), ones(length(nns))) % ~complete(G(nns,nns)) + triangulated = 0; + break; + end +end + |