Gale-Shapley Implementation a multi-dimensional array issue
-
20-03-2021 - |
Pregunta
I am implementing the Gale-Shapley algorithm to match passengers and taxicabs. So far, I've got a single preference structure (distance) to reject or keep the current match.
All seems fine and I think I am close to the solution. However, something odd is happening when accessing the preference data (multidim array). The second index, kTaxiIndex
, has the right value but when indexing I am getting data from a different column in the same row! I have already moved variables around. Does anyone have the slightest clue what is happening here?
Any help is most welcome.
class TaxiScheduler {
ArrayList acceptorTaxis;
ArrayList proposorPassengers;
Integer [] waitingList; //index represent taxis, contents passengers
ArrayList<Integer> rejectionPool; //where unmatched passengers are kept
Integer [] rejectionCounter; //determines the KBest option for that passenger
Double [][] distancePreferences; //unique preference structure
public TaxiScheduler(){
}
public Integer[] doGaleShapley(ArrayList taxis, ArrayList passengers){
acceptorTaxis = taxis;
proposorPassengers = passengers;
waitingList = new Integer [acceptorTaxis.size()]; //keeps best current match
rejectionPool = new ArrayList<Integer>(); //rejected passengers' indexes
rejectionCounter = new Integer [proposorPassengers.size()]; //keeps track of rejections per passenger
distancePreferences = new Double[proposorPassengers.size()][acceptorTaxis.size()];
initPoolandCounter(); //No passenger has been rejected, but all are included in the rejecion (not matched) pool
calculatePreferences(); // distances between taxis and passengers
/*
* Every rejected passenger turns to its next (1st, 2nd, 3rd,...) closest taxi
* Every taxi with more than one proposal keeps the closest passenger in the waitingList and
* rejects other proposing passengers
*/
ListIterator<Integer> itrRejected = this.rejectionPool.listIterator();
while(!this.rejectionPool.isEmpty())
{
if(!itrRejected.hasNext()) //end of list
itrRejected = this.rejectionPool.listIterator();
int newPassengerIndex = (Integer) itrRejected.next().intValue();
int kTaxiIndex = getKBestOption(this.rejectionCounter[newPassengerIndex], newPassengerIndex); //Get K-best based on number of rejections
itrRejected.remove(); //remove current passenger from rejected list
if(waitingList[kTaxiIndex]== null ){ //taxi is vacant!
waitingList[kTaxiIndex] = newPassengerIndex; //match w/ closest taxi
}else{ //compare, keep the best and pool rejected, update rejection counter
int currentPassengerIndex = waitingList[kTaxiIndex].intValue();
Double d1 = distancePreferences[currentPassengerIndex][kTaxiIndex];
Double d2 = distancePreferences[newPassengerIndex][kTaxiIndex];
if(d1.compareTo(d2) > 0){ //new passenger is closer i.e. d1 > d2
addToPool(currentPassengerIndex, itrRejected); //add current passenger to pool and update rejection counter
waitingList[kTaxiIndex] = new Integer(newPassengerIndex); //set new passenger as new match
}else{ //current passenger is preferred
addToPool(newPassengerIndex, itrRejected);
}
}
}
Logger.getLogger("data").log(Level.INFO, "rejectedList = "+printPool(), "");
return waitingList;
}
private void initPoolandCounter() {
rejectionCounter = new Integer[this.proposorPassengers.size()];
for(int i = 0;i< rejectionCounter.length;i++)
{
rejectionCounter[i]=0;
this.rejectionPool.add(i);
}
}
//Works with indexes, look up on preference structure
private Double getDistance(Integer passengerIndex, Integer taxiIndex) {
return distancePreferences[passengerIndex.intValue()][taxiIndex.intValue()];
}
/**
*Fills the preferences structure with distances between taxis and passengers
*
*/
private void calculatePreferences() {
double distance = -1;
StringBuffer buff = new StringBuffer();
try {
for (int iPass = 0; iPass < this.proposorPassengers.size(); iPass++){
PassengerMovement passMov = (PassengerMovement) this.proposorPassengers.get(iPass);
GeoPointExt passGeo = new GeoPointExt(passMov.getLatitude(),passMov.getLongitude());
buff.append(iPass+":\t");
for (int iTaxi = 0; iTaxi < this.acceptorTaxis.size(); iTaxi++){
TaxiMovement taxiMov = (TaxiMovement) this.acceptorTaxis.get(iTaxi);
GeoPointExt taxiGeo = new GeoPointExt(taxiMov.getLatitude(), taxiMov.getLongitude());
distance = Haversine.getDistance(taxiGeo, passGeo, DistanceUnit.Kilometers);
this.distancePreferences[iPass][iTaxi] = new Double(distance);
//TODO: Inverted distances!!!
buff.append(distancePreferences[iPass][iTaxi].toString().substring(0, 5) +"\t");
//Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "PREFS = ["+passMov.getPassengerMovementPK().getMobileNo()+"]["+taxiMov.getTaxiMovementPK().getPlateNo()+"]");
//Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "PREFS = ["+iPass+"]["+iTaxi+"]("+this.distancePreferences[iPass][iTaxi].toString().substring(0, 4));
}
buff.append("\n");
}
}catch(NullPointerException ex)
{
Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "distance = "+distance, ex);
}
Logger.getLogger(TaxiScheduler.class.getName()).log(Level.SEVERE, "TOTAL PREF = \n"+buff.toString());
}
/*
* Returns index of the taxi that is k-best option for that passenger
*
* @param k The k-best (closest) taxi to be retrieved, 0 being the closest
* @param passIndex The passenger index
* @return K-closest taxi index for this passenger
*/
private int getKBestOption(int k, int passIndex){
Double [] passPreferences = this.distancePreferences[passIndex]; //Preferences for the taxi in that index
List<Double> pPreferences = Arrays.asList(passPreferences);
ArrayList originalOrder = new ArrayList(pPreferences);
Collections.sort(pPreferences); //sort taxi distances
Double kDistance = (Double) pPreferences.get(k); //get k-smallest distance
int ind = originalOrder.indexOf(kDistance); //find index of this value in the original array, even if repeated still KBest
return ind;
}
private String printPool() {
StringBuffer buff = new StringBuffer();
int c = 0;
for(Integer x:this.rejectionPool)
{
buff.append(x+"["+rejectionCounter[x]+"] ");
c++;
}
return buff.toString();
}
/*
* Add this element to rejection pool and updates its rejection counter
*
* @param passengerToPool Passenger index to add to the pool
* @param itrRejected iterator used in the rejectionPool
*/
private void addToPool(int passengerToPool, ListIterator<Integer> itrRejected) {
//check whether this passenger is already in the pool
int rIndex = rejectionPool.indexOf(passengerToPool);
if(rIndex == -1){ //not in the pool
this.rejectionCounter[passengerToPool]+=1;
if(this.rejectionCounter[passengerToPool] < this.acceptorTaxis.size()) //if has not been rejected by all taxis
itrRejected.add(passengerToPool);
}else{ //was already pooled, leave it there and increase counter
this.rejectionCounter[rIndex]+=1;
}
}
}
Solución
I hate to be the bearer of bad news but for a problem this specific with an algorithm of this complexity, you're unlikely to get a pinpoint answer.
What I can suggest to help you find your bug(s):
- You have a lot of collections, in particular arrays of differing sizes. It doesn't really surprise me that you're getting some "out of whack" positions given this
- It looks like you've taken an algorithm expressed in a non-OO language (or perhaps pseudocode) - it could be worth setting up a new class to represent a
Taxi
and aPassenger
, holding all the pertinent details inside, rather than trying to index into a particular array position of a particular array - You have a mixture of method parameters and member variables that means your
TaxiScheduler
can actually only deal with one call todoGaleShapley()
at a time. This will probably bite you later on unless you move all those member variables into the method - Using "naked"
ArrayList
s is a double-no-no:List<Taxi>
gives you type-safety while not forcing your client to use anArrayList
- Refactor your
doGaleShapley()
method into smaller, self-contained, well-named methods that do one thing only - Use Unit Tests to simulate each possible situation. Each test should be named after a desired functionality (e.g.
shouldReturnEmptyWaitingListIfNoPassengersProvided
) and consist ofGiven - When - Then
statements that set up a scenario, exercise your function, and verify the results are as expected. If you've refactored your big method into smaller ones, it will be very easy to name your tests and make sure you're covering everything. You can also use a code coverage tool like Cobertura to ensure all your branches are being hit. - If, after doing all this, you still can't figure it out, you should at least have a smaller snippet of code that you can post here :-)