%==============================================================================
%    connected.m
%    Copyright (C) 2007  Amoolya H. Singh, singh@embl.de
%
%    This program is free software: you can redistribute it and/or modify
%    it under the terms of the GNU General Public License as published by
%    the Free Software Foundation, either version 3 of the License, or
%    (at your option) any later version.
%
%    This program is distributed in the hope that it will be useful,
%    but WITHOUT ANY WARRANTY; without even the implied warranty of
%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%    GNU General Public License for more details.
%
%    You should have received a copy of the GNU General Public License
%    along with this program.  If not, see <http://www.gnu.org/licenses/>.
%===============================================================================
function M = connected(x,y)
%------------------------------------------------------------------------------
%
% M = connected(x,y) finds all the disconnected components of the
% pairs [xi,yi] and returns it as an array where each row is a list of
% elements.
%
% Input: 
%   x, starting point of edge
%   y, end point of edge
% Output:
%   M, matrix of connected components
%
% Example:
%      x     y
%      1     2
%      3     4
%      3     5
%      4     5
%      6     7
%      6     8
%      7     8
%      6     9
%      7     9
%      8     9
%
% should return
% 1 2
% 3 4 5
% 6 7 8 9
%
%------------------------------------------------------------------------------


%x=[1 3 3 4 6 6 7 6 7 8];
%y=[2 4 5 5 7 8 8 9 9 9];

M = zeros(length(unique(x)));
visited = zeros(max([x;,y]),1);
tmp = [];


N = length(x);
for i=1:N
  if( ~visited(x(i)) & ~visited(y(i)) )
    visited(x(i)) = 1;
    M(i,1) = x(i);
    ind = find(x==x(i));
    tmp = [tmp, y(ind)];
    visited(y(ind)) = 1;
    tmp = unique(tmp);		% has to be row vector
    M(i,2:length(tmp)+1) = tmp';
  end
  tmp = [];
end

M = unique(M,'rows');
% remove all-zero rows
M(find(sum(M') == 0),:) = [];
M(:,find(sum(M) == 0)) = [];
