function [G] = makeConnected(G)
% Connects the (possibly unconnected) graph given by weight matrix G.
%
% Example:
%   G = makeConnected(G);
%
% (c) 2011 Zalan Bodo

fprintf('--> Connecting components...\n');
L = 0;

[I,J] = find(G == Inf);
N = size(G,1);

if ~isempty(I)
    dmax = max(setdiff(reshape(G, N*N, 1), Inf));
    dmin = min(setdiff(reshape(G, N*N, 1), 0));
    gmax = dmax;

    k = 1;
    L = gmax + (dmin/dmax);
    while ~isempty(I)
        %%%
        fprintf(' Round %d\n', k);
        k = k+1;
        %%%
        [d, i] = min(G(sub2ind(size(G), I, J)));
        G(I(i),J(i)) = L; 
        G(J(i),I(i)) = L;
        % Calculating new distances:
        for m = 1:size(I,1)
            G(I(m),J(m)) = min(G(I(m),I(i))+L+G(J(i),J(m)), G(I(m),J(i))+L+G(I(i),J(m)));
            G(J(m),I(m)) = G(I(m),J(m));
        end;
        [I,J] = find(G == Inf);
        L = L + (dmin/dmax);
    end;
end;

fprintf(' done.\n');
