%%This code does not need the H matrix. It requires an nxn symmetric X matrix of rsd values of the n prefixes to be clustered.  For instance, one can sample n prefixes from the pfxListCoding.txt and then extract the corresponding values from pairwiseDistances.mat to generate X.



clear all;
%%%%%%%% load the pairwise rsd values of prefixes (or ASes) to be clustered.
%%%%%%%% X is an n x n matrix where each entry X(i,j) is the rsd(pfx i, pfx j). 
  
load X;
numItems = size(X,1);
threshold = 50; % threshold is a variable. 


clusteredFlag = int16(ones(numItems,1));
membershipVec = int16(zeros(numItems,1));
Clusters = {}; k = 1; 
Pivots = [];
numItemsLeft = numItems;
while numItemsLeft
	%pick a random prefix among the prefixes that are not clustered yet, and use it as a pivot.
	ind = randsample(numItemsLeft,1,1); tmp = find(clusteredFlag);  
	pivotItem = tmp(ind);	
	% get the column that corresponds to the pivot prefix.
	rsd_col = X(:,pivotItem);
	% find the prefixes that are close to the pivot and that have not been clustered yet.
	candidateItems = find(rsd_col <= threshold);
	groupItems = setdiff(candidateItems, find(clusteredFlag == 0));
	
	Clusters{k} = groupItems;
	Pivots(k) = pivotItem;
	membershipVec(groupItems) = k;
	k = k + 1;
	clusteredFlag(groupItems) = 0;		
	numItemsLeft = numItemsLeft - length(groupItems);
end


