Create clusters from pairs

[billfish]

Although the question is deemed answered, I want to put in 2 cents into the discussion.

I do not have access to SAS/OR so I cannot evaluate the chosen solution.

There are 2 offered solutions: 1) by xia keshan, and 2) SubGraphsMacro.sas (by PGStats)

In the following I propose a different solution.

First the input dataset t_a (here I will characterize it as 100000 (150000)):

/***********************/
/**** input dataset ****/
/***********************/
data t_a;
  do _N_ = 1 to 100000;
      a1 =  int(150000*ranuni(3));
      a2 =  int(150000*ranuni(5));
      output;
  end;
run;

Now some benchmarks for the 3 solutions: 1) xia 2) current 3) SubGraphsMacro

                          xia       current     SubGraphsMacro
  100000   (150000) ->  54.00 sec ( 2.00 sec)   (7:00 min)
  200000   (300000) ->   1:50 min ( 4.06 sec)  (25:57 min)
  400000   (600000) ->   3:35 min ( 9.00 sec)

1000000  (1500000) ->   9:15 min (13.50 sec)
2000000  (3000000) ->  19:19 min (34:00 sec)
4000000  (6000000) ->  37:45 min ( 1:03 min)
8000000 (12000000) -> 106:58 min ( 2:25 min)
16000000 (24000000) -> (not done) (memory crash)

Observations:
   1) SubGraphsMacro is by far the slowest, about 10 times slower that xia's solution.
   2) The current solution is about 30 times faster than xia's solution.
   3) If enough RAM resources are available the current solution can find the clusters for 130M record dataset in less than 1 hour.

The main ingredient of the proposed solution is the "symmetrization" of the dataset:

/*****************************/
/*** t_b = symmetrized t_a ***/
/*****************************/
data t_b(keep=a1 a2);
  set t_a(rename=(a1=b1 a2=b2));
  if b1=b2 then do; a1=b1; a2=b2; output; end;
           else do; a1=b1; a2=b2; output;
                    a1=b2; a2=b1; output; end;
run;

/************************************/
/***** proposed hash solution 1 *****/
/************************************/
data _null_;
   length yMbr Mbr SetNo a1 a2 SET_NO SetNo 8.;

   if _N_=1 then do;
      declare hash ha(dataset:'t_b',multidata:'Y');
         ha.definekey ('a1');
         ha.definedata('a1','a2');
         declare hiter aIter('ha');
         ha.definedone();
         call missing(a1,a2);

      declare hash hx(multidata:'N');
         hx.definekey ('xMbr');
         hx.definedata('xMbr');
         declare hiter xIter('hx');
         hx.definedone();

      declare hash hy(multidata:'N');
         hy.definekey ('yMbr');
         hy.definedata('yMbr');
         declare hiter yIter('hy');
         hy.definedone();

      declare hash hz(multidata:'N');
         hz.definekey ('Mbr');
         hz.definedata('Mbr','SetNo');
         hz.definedone();
   end;

   do until (aDone);
      set t_b end=aDone;
      xMbr=a1; hx.ref();
      xMbr=a2; hx.ref();
   end;
   /***************************/
   /*** start of clustering ***/
   /***************************/
   Set_No=0;
   aSum=0;
   k1=xIter.first();
   do while (k1=0);
      aSum+1;
      a1=xMbr; Mbr=xMbr;
      k2=ha.find();
      j2=hz.find();
      z1=hy.num_items;
      if (k2=0) and (not(j2=0)) and (z1=0) then do;
         Set_No+1; zChange=1;
         yMbr=a1; hy.ref();
         yMbr=a2; hy.ref();
         do until (zChange=0);
            zChange=0;
            k3=yIter.first();
            do while(k3=0);
               a1=yMbr;
               k4=ha.find();
               if (k4=0) then do; d1=ha.remove(key:a1); end;
               do while (k4=0);
                  yMbr=a2; zAdd=hy.add();
                  zChange+(zAdd=0);
                  k4=ha.find_next();
                  if (k4=0) then do; d1=ha.remove(key:a1); end;
               end;
               k3=yIter.next();
            end;
         end;
         k4=yIter.first();
         do while (k4=0);
            Mbr=yMbr; SETNO=SET_NO; hz.ref();
            k4=yIter.next();
         end;
         z1=hy.num_items;
         hy.clear();
         z1=hy.num_items;
      end;
      k1=xIter.next();
   end;
   hz.output(dataset:'t_c');
run;