Databases
StackOverflow2013
Postsdbo
POGale-Shapley Implementation a multi-dimensional array issue
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGale-Shapley Implementation a multi-dimensional array issue
    text
    copied!<p>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. </p> <p>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, <code>kTaxiIndex</code>, 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?</p> <p>Any help is most welcome.</p> <pre><code>class TaxiScheduler { ArrayList acceptorTaxis; ArrayList proposorPassengers; Integer [] waitingList; //index represent taxis, contents passengers ArrayList&lt;Integer&gt; 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&lt;Integer&gt;(); //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&lt;Integer&gt; 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) &gt; 0){ //new passenger is closer i.e. d1 &gt; 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&lt; 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 &lt; 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 &lt; 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&lt;Double&gt; 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&lt;Integer&gt; 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] &lt; 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; } } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload