function [tridag,clusters] = triangulate( G_m, bn_nsizes )
% function [tridag,clusters] = triangulate( G_m, bn_nsizes )
%
% An undirected graph is triangulated iff every cycle of length four or greater
% contains (a triangle:) an edge that connects two nonadjacent nodes in the
% cycle.

% step 1
G_p = G_m;
% step 2
N = length(G_m);
G_p_nodes = 1:N;
clusters  = cell(1,N);  % one for each eliminated vertex
elimnodes = zeros(1,N); % one at each iteration
while 1,
  if isempty( G_p_nodes )
    break;
  else
    % a
    [v,vc,ve] = choose_node( G_p, G_p_nodes, bn_nsizes );
    % disp(sprintf('chose v=%d',v));
    % b
    if isempty(find(elimnodes)),
      clusters{v} = vc;
      if ~isempty(ve),
        G_p = add_edges( ve, G_p );
        G_m = add_edges( ve, G_m );
      end;
      v_Gm = v;
    else % remap labels
      [v_Gm,vc_Gm,ve_Gm] = remap( v,vc,ve, elimnodes );
      clusters{v_Gm} = vc_Gm;
      if ~isempty(ve),
        G_p = add_edges( ve, G_p ); % keep same ones
        G_m = add_edges( ve_Gm, G_m );
      end;
    end;
    % disp(sprintf('v_Gm=%d',v_Gm));
    % c
    %G_p_nodes = setdiff(G_p_nodes,v);
    N = N-1;
    G_p_nodes = 1:N;
    G_p = rmnode( G_p, v );
    elimnodes(v_Gm) = -1;
  end;
end;
% step 3
tridag = G_m;