connect

(tmp_for_tar/misc/connect.m)

Function Synopsis

[ll,ii] = connect (...)

Help text

 [l,ii] = connect (m1,...,mP) - Connect intersecting sets

 m1   : matrix   : Represents a set of numbers.
 :   or list     : List of matrices each representing a set of numbers.
 mp

 l    : list (N) : Non-intersecting sets (l1,...,lN). Each li is the union
                   of some of the mi. 

 ii   : N x P    : 0-1 matrix. ii(i,j) is true iff lj contains mj

 Assuming the mi are all matrices, one has the following properties :

 For each non-empty mi, there is only one lj that contains mi.
 For each non-empty mi, there is only one lj that intersects mi.
 For each intersecting mi, mj, there is a lk containing both.
 Empty sets are not joined with any other sets.

 Last modified: April 2001

Listing of function file tmp_for_tar/misc/connect.m

## [l,ii] = connect (m1,...,mP) - Connect intersecting sets
##
## m1   : matrix   : Represents a set of numbers.
## :   or list     : List of matrices each representing a set of numbers.
## mp
##
## l    : list (N) : Non-intersecting sets (l1,...,lN). Each li is the union
##                   of some of the mi. 
##
## ii   : N x P    : 0-1 matrix. ii(i,j) is true iff lj contains mj
##
## Assuming the mi are all matrices, one has the following properties :
##
## For each non-empty mi, there is only one lj that contains mi.
## For each non-empty mi, there is only one lj that intersects mi.
## For each intersecting mi, mj, there is a lk containing both.
## Empty sets are not joined with any other sets.

## Author:        Etienne Grossmann  <etienne@isr.ist.utl.pt>
## Last modified: April 2001

function [ll,ii] = connect (...)

l = append (list (), all_va_args);
N = length (l);
				# One or less args
if N <= 1, ll = l; ii = ones(length (l)); return; end

from = allv = zeros (1,0);
for i = 1:N, 
  tmp = l(i) = nth(l,i)(:)';
  allv = [allv, tmp]; 
  from = [from, i*ones(1,columns(tmp))];
end

[allv,jj] = sort (allv);
from = from(jj);

kk = find ((! diff (allv)) & diff (from));

				# Pairs of sets that will be joined together
aa = [from(kk); from(kk+1)];

goes = zeros (1,N);

for i = 1:columns (aa)
  ## keyboard
  if all (goes(aa(:,i))),
    j = min (goes(aa(:,i)));
    k = max (goes(aa(:,i)));
    goes(find (goes==k)) = j;
  elseif ((j = max (goes(aa(:,i)))))
    goes(aa(:,i)) = j;
  else
    j = min (complement (goes, 0:max(goes)+1));
    goes(aa(:,i)) = j;
  end
end
## goes
				# there is room for optimization below ...


				# Number sets that have not bee joined to
				# any other
kk = find (! goes);
if ! isempty (kk),
  j = complement (goes, 0:max(goes)+length(kk));
  goes(kk) = j(1:length (kk));
end
				# ... however, goes may not contain all
				# values in 1:max(goes(:)), so I must
				# renumber again in a contiguous way
kk = create_set (goes);

g2 = zeros (1,N);
cnt = 1;
for i = kk
  g2(find(goes==i)) = cnt++;
end

ii = cloose (g2);

ll = list ();
for i = create_set(g2),

  tmp = [];
  for j = find (g2 == i), tmp = union (tmp, nth (l, j)); end
  ll(i) = tmp;

end

## keyboard