Thread: stop a recursion

hi,
I am implementing an algorithm, but I am having problems stopping my recursion. Basically, my procedure partitions a set of d-dimensional points (stored in a vector of vectors) according to the median in a given dimension, it performs some computation, and returns a value.

The problem I have is that sometimes the criteria (the median in this case) which partitions my set into 2 parts, will yield one part which is empty, and then I cannot stop my recursion. (This happens for example when all the values along one dimension are equal and therefore they should go to one partition leaving the other one empty)

Here is a part of my code.

Code:

vector < vector <int> >  SkylineBasic(vector < vector <int> > M, int dimension){
  
	vector < vector <int> > S1, S2;
	vector < vector <int> > vResult, vFilterResult;


 	if (M.size()==1){ 
		return M;
 	}

	sort(M.begin(), M.end(), vec_less(dimension));
	
	int pivot = M[M.size()/2][dimension];

	vector < vector <int> >::iterator medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, pivot));    //bind2nd( vec_less(dimension), 7)
	  

	vector < vector <int> > P1(M.begin(), medianIter); 
	vector < vector <int> > P2(medianIter++, M.end()); 
	 
	S1 = SkylineBasic(P1, dimension);  
	S2 = SkylineBasic(P2, dimension);
	
	vResult = S1;		

 	vFilterResult = MergeBasic(S1, S2, dimension);  // do some work with both sets
	
       //then, the union of S1 with the result of the previous work
	vResult.insert(vResult.end(), vFilterResult.begin(), vFilterResult.end());	
					
	return vResult;
}

I would appreciate some help, as how to stop the recursion when this case of having one empty part, happens.

Can't you just return when the vector is empty like you do when it has a size of one?

I tried, but it does not stop

Code:

 	if (M.size()<=1){
 		
		return M;
 		
 	}

if you are ending up with empty partitions, just write a function to test if a partition is empty, then add another stopping case. i haven't done anything with vectors so they might have their own for doing just that.

Ok, the problem is that when you have a certain set of values, your partitions have 0 items in one partition and multiple items in the other because all the elements are equal, right? Then you need to check both partitions P1 and P2 before you call SkylineBasic again. If either are empty, then don't call the function for either one, otherwise you will keep getting the same partitioning and never break down the vector with points in it.

Hi,
It seems that now with the added condition to my procedure, the recursion stops properly.
But now I have a similar problem in another recursion inside MergeBasic. I have written my code below.
Note: it is ok to have one empty partition, for example, in the case that the elements along one dimension are equal,
that is why I should not use this following code, becase it might make that points (vectors) that correspond to say set S1, end up in set S2.

Code:

vector < vector <int> >::iterator medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, pivot));
if (medianIter==M.begin() || medianIter==M.end())
    medianIter=M.begin()+M.size()/2;

In this case I try to partition around the median.

Btw, the scenario is the following:
Having a set of objects S in an n-dimensional space D=(D1, …, Dn)
Point u dominates Point v (u and v belong to S) if (u.Di <= v.Di) for 1 <= i <= n, and on at least one dimension Dj, u.Dj < v.Dj
u is a skyline object if u is not dominated by any other objects in S

Code:

/*******************************************************************************************
 * SkylineBasic:
 * 	equipartitions the set into two parts, then, recursively applies the whole algorithm
 * 	to both parts, obtains two sets of their respective Skyline, and combines the results.
 *******************************************************************************************/
vector < vector <int> >  SkylineBasic(vector < vector <int> > M, int dimension){
  
	vector < vector <int> > S1, S2;
	vector < vector <int> > vResult, vFilterResult;

 	if (M.size()==1) // partitioning stops	
		return M;
	  
	// calculate an approximate median
	sort(M.begin(), M.end(), vec_less(dimension));	
	int pivot =  M[M.size()/2][dimension]; 

	vector < vector <int> >::iterator medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, pivot));
	  
	// equipartition the set
	 vector < vector <int> > P1(M.begin(), medianIter); 
	 vector < vector <int> > P2(medianIter, M.end()); 

	 
	if ( (P1.size()>0) && (P2.size()>0) ) {  <=== new condition to avoid enter again
		// computes the skyline recursively
	  S1 = SkylineBasic(P1, dimension);   	  
		S2 = SkylineBasic(P2, dimension);		
	}
	else{
		S1 = P1;				
		S2 = P2;				
	}
	
	//"filters" the elements from S2, that are dominated by elements in S1
	//None of the points in S1 can be dominated by a point in S2		
	vResult = S1; 			
	if (S2.size()>0){	// is S2 is not empty
		if (S1.size()==0)	// and if S1 is empty
			vFilterResult = S2; // the result is just S2 (none of S2 is dominated by S1, because S1 is empty)
		else
	 		vFilterResult = MergeBasic(S1, S2, dimension); // if both S1 and S2 are not empty, then enter into MergeBasic
	}

	vResult.insert(vResult.end(), vFilterResult.begin(), vFilterResult.end());	//get rid of this
					
	return vResult;
}

Here in MergeBasic, for example I have the following situation where the recursion never stops:
using dimension 5 (the 5th elements of each vector)
S1:
45 2 16 41 31 6
42 4 44 48 31 6

S2:
50 14 3 34 42 11
41 16 9 10 38 11
29 20 1 5 43 12

==> pivot: 31
partition S1 around 31
S11: (empty)

S12:
45 2 16 41 31 6
42 4 44 48 31 6
partition S2 around 31

S21:

S22:
50 14 3 34 42 11
41 16 9 10 38 11
29 20 1 5 43 12

the of course when it enters into this line
R2 = MergeBasic(S12, S22, dimension);
it never stops.

Code:

/*******************************************************************************************
 * filter:
 * 	computes the filter(S1|S2), which determines the elements of the set S2 which are not
 * 	dominated by any element in set S1.
 *******************************************************************************************/
vector< vector <int> > MergeBasic(vector< vector <int> > S1, vector< vector <int> > S2, int dimension){
	vector< vector <int> > 
		A, S11, S12, S21, S22, vTmp;
	vector< vector <int> > 
		R, R1, R2, R3, intersct;		
	vector< vector <int> >::iterator 
		vIter;
	vector <int> 
		q, p;
	vector< vector <int> >::iterator 
		medianIter;				
	unsigned int 
		i;

		
	if (S1.size()==1){  // trivial case
		p = S1[0];
		for (i=0; i<S2.size(); i++){
			if ( domination(p, S2[i], D) != 2 ) //if p does not dominate q
				R.push_back(S2[i]);			
		}
		return R; 		
	}	

  if (S2.size()==1){  // trivial case
  	R = S2;
  	q = S2[0];
  	for (i=0; i<S1.size(); i++){
	  	p = S1[i];
  		if (domination(p, q, D)== 2) { // if p dominates q
  			R.clear();
  			break;
  		}
  	}
		return R; 		  	
	}

	if (dimension == 1){	// dimension is low
		sort(S1.begin(), S1.end(), vec_less(0));
 		int min = S1[0][0];

		for (i=0; i<S2.size(); i++){
			if (S2[i][0] < min)
				R.push_back(S2[i]);
		}	 
		return R; 				
	}	

	// general case				 
	else {							
		int pivot = 0;

		if (S1.size()>0)	{
			sort(S1.begin(), S1.end(), vec_less(dimension-1));							 			 		
			pivot = S1[S1.size()/2][dimension-1];		//approximate median
			medianIter = stable_partition (S1.begin(), S1.end(), vec_part(dimension-1, pivot)); 				    
			S11.assign(S1.begin(), medianIter);
			S12.assign(medianIter, S1.end());
		}

		// partition S2 with the pivot used in S1
		medianIter = stable_partition (S2.begin(), S2.end(), vec_part(dimension-1, pivot)); 
	
		vector < vector <int> > S21(S2.begin(), medianIter); 
	 	vector < vector <int> > S22(medianIter, S2.end());		

		
		//compare adjacent parts			
		R1 = MergeBasic(S11, S21, dimension);
		R2 = MergeBasic(S12, S22, dimension);		
		//compare diagonally		
		R3 = MergeBasic(S11, R2, dimension-1);
		
		R = R1;
			 
		R.insert(R.end(), R3.begin(), R3.end());
		return R;
	}
		
}

I would appreciate some suggestions about how to stop the recursion inside MergeBasic in this situations.


Thanks

p.s. this paper has the "basic divide and conquer" that I am trying to implement:
http://citeseer.ist.psu.edu/borzsonyi01skyline.html