rails-commits

[Stefan F. <ste...@us...>]

Update of /cvsroot/rails/18xx/rails/algorithms
In directory sfp-cvsdas-4.v30.ch3.sourceforge.com:/tmp/cvs-serv15565/rails/algorithms

Modified Files:
	NetworkTrain.java RevenueCalculator.java RevenueAdapter.java 
	NetworkEdge.java NetworkIterator.java NetworkGraphBuilder.java 
Log Message:
Several fixes and improvements to the revenue calculator and the network iterator.

Index: RevenueCalculator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueCalculator.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** RevenueCalculator.java	20 Apr 2010 22:07:09 -0000	1.7
--- RevenueCalculator.java	27 Apr 2010 23:24:50 -0000	1.8
***************
*** 12,18 ****
      
      // static vertex data
!     private final int[] vertexValue;
!     private final boolean[] vertexCity;
!     private final boolean[] vertexTown;
      private final int[][] vertexNeighbors;
  
--- 12,18 ----
      
      // static vertex data
!     private final int[][] vertexValueByTrain; // dimensions: vertexId, trainId
!     private final boolean[] vertexMajor;
!     private final boolean[] vertexMinor;
      private final int[][] vertexNeighbors;
  
***************
*** 28,41 ****
      
      // static train data
!     private final int[] trainMaxCities;
!     private final int[] trainMaxTowns;
!     private final boolean[] trainIgnoreTowns;
!     private final int[] trainMultiplyCities;
!     private final int[] trainMultiplyTowns;
      
      // dynamic train data
      private final int[] trainCurrentValue;
!     private final int[] trainCities;
!     private final int[] trainTowns;
      private final boolean[][] trainVisited;
      private final int[][] trainVertexStack;
--- 28,39 ----
      
      // static train data
!     private final int[] trainMaxMajors;
!     private final int[] trainMaxMinors;
!     private final boolean[] trainIgnoreMinors;
      
      // dynamic train data
      private final int[] trainCurrentValue;
!     private final int[] trainMajors;
!     private final int[] trainMinors;
      private final boolean[][] trainVisited;
      private final int[][] trainVertexStack;
***************
*** 44,54 ****
      private final int [] trainStartEdge;
      
!     // dynamic run data
      private int finalTrain;
      private boolean useRevenuePrediction;
      
      private int currentBestValue;
      private final int [][] currentBestRun;
      
      private int countVisits;
      private int countEdges;
--- 42,61 ----
      private final int [] trainStartEdge;
      
!     // run settings
!     private int startTrain;
      private int finalTrain;
      private boolean useRevenuePrediction;
      
+     // current best run results
      private int currentBestValue;
      private final int [][] currentBestRun;
      
+     // prediction data
+     private int[] maxCumulatedTrainRevenues;
+     private int[][] maxMajorRevenues; // dimensions trainId x nb vertex; 
+     private int[][] maxMinorRevenues; // dimensions trainId x nb vertex;
+     private int[][] maxBonusRevenues; // dimensions trainId x nb bonuses
+ 
+     // statistic data
      private int countVisits;
      private int countEdges;
***************
*** 57,65 ****
      private int nbPredictions;
  
-     // prediction data
-     private int[] maxCityRevenues;
-     private int[] maxTownRevenues;
-     private int[] maxTrainRevenues;
-     
      // revenue Adapter
      private RevenueAdapter revenueAdapter;
--- 64,67 ----
***************
*** 87,93 ****
          
          // initialize all required variables
!         vertexValue = new int[nbVertexes];
!         vertexCity = new boolean[nbVertexes];
!         vertexTown = new boolean[nbVertexes];
          vertexNeighbors = new int[nbVertexes][maxNeighbors];
          
--- 89,95 ----
          
          // initialize all required variables
!         vertexValueByTrain = new int[nbVertexes][nbTrains];
!         vertexMajor = new boolean[nbVertexes];
!         vertexMinor = new boolean[nbVertexes];
          vertexNeighbors = new int[nbVertexes][maxNeighbors];
          
***************
*** 96,108 ****
          edgeUsed = new boolean[nbVertexes][nbVertexes];
          
!         trainCities = new int[nbTrains];
!         trainTowns = new int[nbTrains];
!         trainIgnoreTowns = new boolean[nbTrains];
!         trainMultiplyCities = new int[nbTrains];
!         trainMultiplyTowns = new int[nbTrains];
          
          trainCurrentValue = new int[nbTrains];
!         trainMaxCities = new int[nbTrains];
!         trainMaxTowns = new int[nbTrains];
          trainVisited = new boolean[nbTrains][nbVertexes];
          trainVertexStack = new int[nbTrains][nbVertexes];
--- 98,108 ----
          edgeUsed = new boolean[nbVertexes][nbVertexes];
          
!         trainMaxMajors = new int[nbTrains];
!         trainMaxMinors = new int[nbTrains];
!         trainIgnoreMinors = new boolean[nbTrains];
          
          trainCurrentValue = new int[nbTrains];
!         trainMajors = new int[nbTrains];
!         trainMinors = new int[nbTrains];
          trainVisited = new boolean[nbTrains][nbVertexes];
          trainVertexStack = new int[nbTrains][nbVertexes];
***************
*** 114,124 ****
          
          useRevenuePrediction = false;
-         
      }
  
!     void setVertex(int id, int value, boolean city, boolean town, int[]neighbors) {
!         vertexValue[id] = value;
!         vertexCity[id] = city;
!         vertexTown[id] = town;
          vertexNeighbors[id] = neighbors;
      }
--- 114,125 ----
          
          useRevenuePrediction = false;
      }
  
!     void setVertex(int id, int value, boolean major, boolean minor, int[] neighbors) {
!         for (int j=0; j < nbTrains; j++) {
!             vertexValueByTrain[id][j] = value;
!         }
!         vertexMajor[id] = major;
!         vertexMinor[id] = minor;
          vertexNeighbors[id] = neighbors;
      }
***************
*** 133,149 ****
      }
      
!     void setTrain(int id, int cities, int towns, boolean ingoreTowns, int multiplyCities, int multiplyTowns) {
!         trainMaxCities[id] = cities;
!         trainMaxTowns[id] = towns;
!         trainIgnoreTowns[id] = ingoreTowns;
!         trainMultiplyCities[id] = multiplyCities;
!         trainMultiplyTowns[id] = multiplyTowns;
      }
      
!     void setPredictionData(int[] maxCityRevenues, int[] maxTownRevenues) {
!         this.maxCityRevenues = maxCityRevenues;
!         this.maxTownRevenues = maxTownRevenues;
!         useRevenuePrediction = true;
!     }
      
      int[][] getOptimalRun() {
--- 134,154 ----
      }
      
!     void setTrain(int id, int majors, int minors, boolean ignoreMinors, int multiplyMajors, int multiplyMinors) {
!         trainMaxMajors[id] = majors;
!         trainMaxMinors[id] = minors;
!         trainIgnoreMinors[id] = ignoreMinors;
!         
!         for (int j=0; j < nbVertexes; j++) {
!             if (vertexMajor[id]) {
!                 vertexValueByTrain[j][id] = vertexValueByTrain[j][id] * multiplyMajors;
!             }
!             if (vertexMinor[id]) {
!                 vertexValueByTrain[j][id] = vertexValueByTrain[j][id] * multiplyMinors;
!             }
!         }
      }
      
! //    void setPredictionData(int[] maxMajorRevenues, int[] maxMinorRevenues) {
! //    }
      
      int[][] getOptimalRun() {
***************
*** 169,188 ****
          revenueAdapter.notifyRevenueListener(revenue, finalResult);
      }
      
!     int calculateRevenue(int startTrain, int finalTrain) {
!         log.info("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
          
          nbEvaluations = 0; nbPredictions = 0; nbEdges = 0;
  
!         // initialize maximum train revenues 
!         if (useRevenuePrediction) {
!             maxTrainRevenues = new int[nbTrains];
!             for (int j=0; j < nbTrains; j++) {
!                 maxTrainRevenues[j] = maxCityRevenues[trainMaxCities[j]] * trainMultiplyCities[j] + 
!                 maxTownRevenues[trainMaxTowns[j]] * trainMultiplyTowns[j];
!             }
          }
          
          this.finalTrain = finalTrain;
          runTrain(startTrain);
  
--- 174,264 ----
          revenueAdapter.notifyRevenueListener(revenue, finalResult);
      }
+ 
+     private int[] bestRevenues(int[] values, int length) {
+         int[] bestRevenues = new int[length + 1];
+         Arrays.sort(values);
+         int cumulatedRevenues = 0;
+         for (int j=1; j <= length ; j++) {
+             cumulatedRevenues += values[values.length - j];
+             bestRevenues[j] = cumulatedRevenues;
+         }
+         log.info(Arrays.toString(bestRevenues));
+         return bestRevenues;
+     }
      
!     private void initRevenueValues(int startTrain, int finalTrain){
!         
!       // intialize values
!         maxMajorRevenues = new int[nbTrains][nbVertexes];
!         maxMinorRevenues = new int[nbTrains][nbVertexes];
!         for (int t=startTrain; t <= finalTrain; t++) {
!             int[] majorValues = new int[nbVertexes];
!             int[] minorValues = new int[nbVertexes];
!             int[] bonusValues = new int[nbVertexes];
!             int major = 0, minor = 0, bonus = 0;
!             for (int v=0; v < nbVertexes; v++) {
!                 if (vertexValueByTrain[v][t] == 0) continue;
!                 if (vertexMajor[v])
!                     majorValues[major++] = vertexValueByTrain[v][t];
!                 else if (vertexMinor[v])
!                     minorValues[minor++] = vertexValueByTrain[v][t];
!                 else
!                     bonusValues[bonus++] = vertexValueByTrain[v][t];
!             }
!             maxMajorRevenues[t] = bestRevenues(majorValues, trainMaxMajors[t]);
!             maxMinorRevenues[t] = bestRevenues(minorValues, trainMaxMinors[t]);
!             maxCumulatedTrainRevenues[t] = maxMajorRevenues[t][trainMaxMajors[t]] + maxMinorRevenues[t][trainMaxMinors[t]];
!         }
!     }
!     
!     void initialPredictionRuns(int startTrain, int finalTrain) {
          
+         if (startTrain > finalTrain) return;
+        
+         useRevenuePrediction = true;
+         this.maxCumulatedTrainRevenues = new int[nbTrains];
+          initRevenueValues(startTrain, finalTrain);
+         
+         if (startTrain == finalTrain) return;
+         
+         // start prediction runs
          nbEvaluations = 0; nbPredictions = 0; nbEdges = 0;
  
!         log.info("RC: start individual prediction Runs");
!         int cumulatedRevenues = 0;
!         int[] maxSingleTrainRevenues = new int[nbTrains]; 
!         for (int j=finalTrain; j >= startTrain; j--) {
!             this.startTrain = j;
!             this.finalTrain = j;
!             currentBestValue = 0;
!             runTrain(j);
!             log.info("RC: Best prediction run of train number " + j + " value = " + currentBestValue);
!             maxSingleTrainRevenues[j] = currentBestValue;
!             cumulatedRevenues +=  currentBestValue;
!             maxCumulatedTrainRevenues[j] = cumulatedRevenues;
          }
          
+         if (startTrain == finalTrain-1) return;
+ 
+         log.info("RC: start combined prediction runs");
+         this.finalTrain = finalTrain;
+         for (int j=finalTrain - 1; j > startTrain; j--) {
+             this.startTrain = j;
+             currentBestValue = 0;
+             runTrain(j);
+             log.info("RC: Best prediction run until train nb. " + j + " value = " + currentBestValue);
+             maxCumulatedTrainRevenues[j] = currentBestValue;
+             maxCumulatedTrainRevenues[j-1] = currentBestValue  + maxSingleTrainRevenues[j-1];
+         }
+     }
+     
+     int calculateRevenue(int startTrain, int finalTrain) {
+         log.info("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
+         
+         nbEvaluations = 0; nbPredictions = 0; nbEdges = 0;
+ 
+         this.startTrain = startTrain;
          this.finalTrain = finalTrain;
+         
          runTrain(startTrain);
  
***************
*** 192,199 ****
          return currentBestValue;
      }
!     
      private void runTrain(int trainId) {
          log.debug("RC: runTrain " + trainId);
          
          // initialize the positions
          trainStackPos[trainId] = 0;
--- 268,279 ----
          return currentBestValue;
      }
!    
      private void runTrain(int trainId) {
          log.debug("RC: runTrain " + trainId);
          
+         // initialize lengths
+         trainMajors[trainId] = trainMaxMajors[trainId];
+         trainMinors[trainId] = trainMaxMinors[trainId];
+         
          // initialize the positions
          trainStackPos[trainId] = 0;
***************
*** 237,242 ****
--- 317,330 ----
              finalizeVertex(trainId, vertexId, valueStation);
              encounterVertex(trainId, vertexId, false);
+             // keep them on the visited vertex list to avoid route duplication
+             trainVisited[trainId][vertexId] = true;
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
          }
+ 
+         for (int i=0; i < startVertexes.length; i++) {
+             // remove all of them from the visited vertex list
+             trainVisited[trainId][startVertexes[i]] = false;
+         }
+ 
          log.debug("RC: finishTrain " + trainId);
      }
***************
*** 308,312 ****
              }
              // 2b. restart at startVertex for bottom part
!             if (valueStation && trainBottomPos[trainId] == 0 && (vertexCity[vertexId] || vertexTown[vertexId])){
                  runBottom(trainId);
              }
--- 396,400 ----
              }
              // 2b. restart at startVertex for bottom part
!             if (valueStation && trainBottomPos[trainId] == 0){
                  runBottom(trainId);
              }
***************
*** 327,357 ****
          // set visit to true if arriving, otherwise you leave
          trainVisited[trainId][vertexId] = arrive;
!         
!         boolean valueVertex = false;
          if (arrive) {
!             if (vertexCity[vertexId]) {
!                 trainCities[trainId]++;
!                 trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyCities[trainId];
!                 valueVertex = true;
!             } else if (vertexTown[vertexId] && !trainIgnoreTowns[trainId]) {
!                 trainTowns[trainId]++;
!                 trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyTowns[trainId];
                  valueVertex = true;
              }
              trainVertexStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
              countVisits++;
          } else {
!             if (vertexCity[vertexId]) {
!                 trainCities[trainId]--;
!                 trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyCities[trainId];
!                 valueVertex = true;
!             } else if (vertexTown[vertexId] && !trainIgnoreTowns[trainId] ) {
!                 trainTowns[trainId]--;
!                 trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyTowns[trainId];
                  valueVertex = true;
              }
              trainStackPos[trainId]--; // pull from stack
              countVisits--;
!         }
          log.debug("RC: Count Visits = " + countVisits);
          return valueVertex;
--- 415,448 ----
          // set visit to true if arriving, otherwise you leave
          trainVisited[trainId][vertexId] = arrive;
! 
!         boolean valueVertex;
          if (arrive) {
!             if (vertexValueByTrain[vertexId][trainId] == 0) {
!                 valueVertex = false; 
!             } else {
                  valueVertex = true;
+                 trainCurrentValue[trainId] += vertexValueByTrain[vertexId][trainId];
+             }
+             if (vertexMajor[vertexId])
+                 trainMajors[trainId]--;
+             if (vertexMinor[vertexId]) {
+                 trainMinors[trainId]--;
              }
              trainVertexStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
              countVisits++;
          } else {
!             if (vertexValueByTrain[vertexId][trainId] == 0) {
!                 valueVertex = false; 
!             } else {
                  valueVertex = true;
+                 trainCurrentValue[trainId] -= vertexValueByTrain[vertexId][trainId];
              }
+             if (vertexMajor[vertexId])
+                 trainMajors[trainId]++;
+             if (vertexMinor[vertexId])
+                 trainMinors[trainId]++;
              trainStackPos[trainId]--; // pull from stack
              countVisits--;
!         }   
          log.debug("RC: Count Visits = " + countVisits);
          return valueVertex;
***************
*** 404,427 ****
      private Terminated trainTerminated(int trainId) {
          Terminated terminated = Terminated.NotYet;
!         if (trainIgnoreTowns[trainId]) {
              // express trains
!             if (trainCities[trainId] == trainMaxCities[trainId])
!                 terminated = Terminated.WithEvaluation;
!         } else if (trainTowns[trainId] == 0) {
!             // default train
!             if (trainCities[trainId] + trainTowns[trainId] == trainMaxCities[trainId])
                  terminated = Terminated.WithEvaluation;
!         } else {
!             // plus trains
!             if (trainCities[trainId] > trainMaxCities[trainId]){
                  terminated = Terminated.WithoutEvaluation;
!             } else if (trainCities[trainId] + trainTowns[trainId] == 
!                 trainMaxCities[trainId] + trainMaxTowns[trainId] )
                  terminated = Terminated.WithEvaluation;
          }
          if (terminated != Terminated.NotYet) {
              log.debug ("RC: Train " + trainId + " has terminated: " +
!             		"cities = " + trainCities[trainId] + " towns = " + trainTowns[trainId] +
!             		"maxCities = " + trainMaxCities[trainId] + "maxTowns = " + trainMaxTowns[trainId]);
          }
          return terminated;
--- 495,511 ----
      private Terminated trainTerminated(int trainId) {
          Terminated terminated = Terminated.NotYet;
!         if (trainIgnoreMinors[trainId]) {
              // express trains
!             if (trainMajors[trainId] == 0)
                  terminated = Terminated.WithEvaluation;
!         } else { // default and plus trains
!             if (trainMajors[trainId] < 0){
                  terminated = Terminated.WithoutEvaluation;
!             } else if (trainMajors[trainId] + trainMinors[trainId] == 0)
                  terminated = Terminated.WithEvaluation;
          }
          if (terminated != Terminated.NotYet) {
              log.debug ("RC: Train " + trainId + " has terminated: " +
!             		"majors = " + trainMajors[trainId] + " minors = " + trainMinors[trainId]);
          }
          return terminated;
***************
*** 431,436 ****
          log.debug("RC: No more edges found at " + vertexId + " for train " + trainId);
          
-         if (!vertexCity[vertexId] && !vertexTown[vertexId]) return;
-         
          if (trainId == finalTrain) {
              if (evaluate) evaluateResults();
--- 515,518 ----
***************
*** 443,454 ****
          // sum to total value
          int totalValue = 0;
!         for (int j = 0; j <= finalTrain; j++) {
!             if (trainCities[j] + trainTowns[j] <= 1) {
!                 log.debug("RC: Train " + j + " has no value / does not have 2+ stations");
              } else {
!                 totalValue += trainCurrentValue[j];
!                 log.debug("RC: Train " + j + " has value of " + trainCurrentValue);
              }
          }
          nbEvaluations++;
          log.debug("RC: current total value " + totalValue);
--- 525,538 ----
          // sum to total value
          int totalValue = 0;
!         for (int j = startTrain; j <= finalTrain; j++) {
!             if (trainIgnoreMinors[j]) { 
!                 if (trainMaxMajors[j] - trainMajors[j] >= 2)
!                     totalValue += trainCurrentValue[j];
              } else {
!                 if (trainMaxMajors[j] + trainMaxMinors[j] - trainMajors[j] - trainMinors[j] >= 2)
!                     totalValue += trainCurrentValue[j];
              }
          }
+         
          nbEvaluations++;
          log.debug("RC: current total value " + totalValue);
***************
*** 474,512 ****
      // predict revenues and returns true if best value can still be exceeded
      private boolean predictRevenues(int trainId){
          int totalValue = 0;
!         for (int j = 0; j <= finalTrain; j++) {
!             int trainValue;
!             if (j < trainId) { // train has run already => use realized values
!                 trainValue =  trainCurrentValue[j];
!             } else if (j > trainId) { // train is in the future => use maximum values
!                 trainValue =  maxTrainRevenues[j];
!             } else { // the current train
!                 if (trainIgnoreTowns[j]) {
!                     // express train
!                     trainValue = trainCurrentValue[j] + 
!                     maxCityRevenues[trainMaxCities[j] - trainCities[j] ] * trainMultiplyCities[j];
!                 } else if (trainMaxTowns[j] == 0) {
!                     // default train
!                     trainValue = trainCurrentValue[j] + 
!                     maxCityRevenues[trainMaxCities[j] - trainCities[j] - trainTowns[j] ] * trainMultiplyCities[j];
!                 } else {
!                     // plus trains (or capped default trains)
!                     int townDiff = trainMaxTowns[j] - trainTowns[j];
!                     if (townDiff > 0) {
!                         trainValue = trainCurrentValue[j] + 
!                         maxCityRevenues[trainMaxCities[j] - trainCities[j]] * trainMultiplyCities[j] +
!                         maxTownRevenues[trainMaxTowns[j] - trainTowns[j]] * trainMultiplyTowns[j];
!                     } else if (townDiff == 0) {
!                         trainValue = trainCurrentValue[j] + 
!                         maxCityRevenues[trainMaxCities[j] - trainCities[j]] * trainMultiplyCities[j];
!                     } else { // negative townDiff, thus too many towns already visited
!                         trainValue = trainCurrentValue[j] + 
!                         maxCityRevenues[trainMaxCities[j] - trainCities[j] + townDiff] * trainMultiplyCities[j];
!                     }
!                 }
!                 trainValue = Math.min(trainValue, maxTrainRevenues[j]); 
              }
-             log.debug("RC: Train " + j + " has value of " + trainValue);
-             totalValue += trainValue;
          }
  
--- 558,594 ----
      // predict revenues and returns true if best value can still be exceeded
      private boolean predictRevenues(int trainId){
+         // the potential revenues of the future trains
          int totalValue = 0;
!         if (trainId < finalTrain)
!              totalValue = maxCumulatedTrainRevenues[trainId + 1];
!         
!         // predict the current train
!         int trainValue = trainCurrentValue[trainId];
!         if (trainIgnoreMinors[trainId]) {
!             // express train
!             trainValue += maxMajorRevenues[trainId][trainMajors[trainId]];
!         } else {
!             // default and plus trains
!             if (trainMinors[trainId] > 0){
!                 trainValue += maxMajorRevenues[trainId][trainMajors[trainId]];
!                 trainValue += maxMinorRevenues[trainId][trainMinors[trainId]];
!             } else { // <= 0
!                 trainValue += maxMajorRevenues[trainId][trainMajors[trainId] + trainMinors[trainId]]; 
!             }
!         }
!         log.debug("RC: Current train has predicted  value of " + trainValue);
! 
!         // maximum value for the trainId including future trains
!         totalValue = Math.min(totalValue + trainValue, maxCumulatedTrainRevenues[trainId]); 
!         
!         // and add the past trains: current realized values
!         for (int j = startTrain; j < trainId; j++) {
!             if (trainIgnoreMinors[j]) { 
!                 if (trainMaxMajors[j] - trainMajors[j] >= 2)
!                     totalValue += trainCurrentValue[j];
!             } else {
!                 if (trainMaxMajors[j] + trainMaxMinors[j] - trainMajors[j] - trainMinors[j] >= 2)
!                     totalValue += trainCurrentValue[j];
              }
          }
  
***************
*** 524,539 ****
          StringBuffer buffer = new StringBuffer();
          
!         buffer.append("vertexValues:" + Arrays.toString(vertexValue) + "\n");
!         buffer.append("vertexCity:" + Arrays.toString(vertexCity) + "\n");
!         buffer.append("vertexTown:" + Arrays.toString(vertexTown) + "\n");
          buffer.append("vertexEdges:" + Arrays.deepToString(vertexNeighbors) + "\n");
  //        buffer.append("edgeGreedy:" + Arrays.deepToString(edgeGreedy));
  //        buffer.append("edgeDistance:" + Arrays.deepToString(edgeDistance));
          buffer.append("startVertexes:" + Arrays.toString(startVertexes) + "\n"); 
!         buffer.append("trainMaxCities:" + Arrays.toString(trainMaxCities) + "\n"); 
!         buffer.append("trainMaxTowns:" + Arrays.toString(trainMaxTowns) + "\n"); 
!         buffer.append("trainIgnoreTowns:" + Arrays.toString(trainIgnoreTowns) + "\n"); 
!         buffer.append("maxCityRevenues:" + Arrays.toString(maxCityRevenues) + "\n"); 
!         buffer.append("maxTownRevenues:" + Arrays.toString(maxTownRevenues) + "\n"); 
        
          return buffer.toString();
--- 606,619 ----
          StringBuffer buffer = new StringBuffer();
          
!         buffer.append("vertexValuesByTrain:" + Arrays.deepToString(vertexValueByTrain) + "\n");
!         buffer.append("vertexMajor:" + Arrays.toString(vertexMajor) + "\n");
!         buffer.append("vertexMinor:" + Arrays.toString(vertexMinor) + "\n");
          buffer.append("vertexEdges:" + Arrays.deepToString(vertexNeighbors) + "\n");
  //        buffer.append("edgeGreedy:" + Arrays.deepToString(edgeGreedy));
  //        buffer.append("edgeDistance:" + Arrays.deepToString(edgeDistance));
          buffer.append("startVertexes:" + Arrays.toString(startVertexes) + "\n"); 
!         buffer.append("trainMaxMajors:" + Arrays.toString(trainMaxMajors) + "\n"); 
!         buffer.append("trainMaxMinors:" + Arrays.toString(trainMaxMinors) + "\n"); 
!         buffer.append("trainIgnoreMinors:" + Arrays.toString(trainIgnoreMinors) + "\n"); 
        
          return buffer.toString();

Index: NetworkIterator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkIterator.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** NetworkIterator.java	19 Apr 2010 19:35:38 -0000	1.4
--- NetworkIterator.java	27 Apr 2010 23:24:50 -0000	1.5
***************
*** 16,54 ****
      AbstractGraphIterator<NetworkVertex, NetworkEdge> {
  
!     /**
!      * Standard vertex visit state enumeration.
!      * Copied from CrossComponentIterator due to visibility for generic definition above
!      */
!     protected static enum VisitColor
!     {
!         /**
!          * Vertex has not been returned via iterator yet.
!          */
!         WHITE,
!         /** 
!         * Vertex has been returned via iterator, but we're
!         * not done with all of its out-edges yet.
!         */
!         GRAY,
!         /**
!          * Vertex has been returned via iterator, and we're
!          * done with all of its out-edges.
!          */
!         BLACK
      }
! 
!     /**
!      * Stores the vertices that have been seen during iteration and
!      * some additional traversal info regarding each vertex.
!      */
!     private Map<NetworkVertex, VisitColor> seen = new HashMap<NetworkVertex, VisitColor>();
!     private Map<NetworkVertex, Boolean> mustUseGreedy = new HashMap<NetworkVertex, Boolean>();
      private NetworkVertex startVertex;
  
      private final PublicCompanyI company;
      private final Graph<NetworkVertex, NetworkEdge> graph;
-     
-     /** LIFO stack for DFS */
-     private List<NetworkVertex> stack = new ArrayList<NetworkVertex>();
  
      protected static Logger log =
--- 16,33 ----
      AbstractGraphIterator<NetworkVertex, NetworkEdge> {
  
!     public static enum greedyState {
!         seen,
!         nonGreedy,
!         greedy,
!         done
      }
!     
      private NetworkVertex startVertex;
+     private List<NetworkVertex> stack = new ArrayList<NetworkVertex>();
+     private List<Boolean> greedyStack = new ArrayList<Boolean>();
+     private Map<NetworkVertex, greedyState> seen = new HashMap<NetworkVertex, greedyState>();
  
      private final PublicCompanyI company;
      private final Graph<NetworkVertex, NetworkEdge> graph;
  
      protected static Logger log =
***************
*** 95,99 ****
          }
          
!         return !isConnectedComponentExhausted();
      }
  
--- 74,85 ----
          }
          
!         int i = stack.size() - 1;
!         while (i >= 0) {
!             if (stack.get(i) != null) 
!                 break;
!             else
!                 i = i - 2;
!         }
!         return i >=0; 
      }
  
***************
*** 108,117 ****
  
          if (hasNext()) {
  
!             NetworkVertex nextVertex = provideNextVertex();
  
!             VisitColor previousColor = putSeenData(nextVertex , VisitColor.GRAY);
              
!             addUnseenChildrenOf(nextVertex, previousColor);
  
              return nextVertex;
--- 94,113 ----
  
          if (hasNext()) {
+             NetworkVertex nextVertex;
+             while (true) {
+                  nextVertex = stack.remove(stack.size() - 1);
+                 if (nextVertex != null)
+                     break;
+                 stack.remove(stack.size() - 1);
+             }
  
!             log.debug("Iterator: provides next vertex" + nextVertex);
!             boolean nextGreedy = greedyStack.remove(greedyStack.size() - 1);
  
!             putSeenData(nextVertex, nextGreedy);
!             stack.add(nextVertex);
!             stack.add(null); // add sentinel that we know when we are ready
              
!             addUnseenChildrenOf(nextVertex, nextGreedy);
  
              return nextVertex;
***************
*** 121,149 ****
      }
  
-     /**
-      * Access the data stored for a seen vertex.
-      *
-      * @param vertex a vertex which has already been seen.
-      *
-      * @return data associated with the seen vertex or <code>null</code> if no
-      * data was associated with the vertex. A <code>null</code> return can also
-      * indicate that the vertex was explicitly associated with <code>
-      * null</code>.
-      */
-     private VisitColor getSeenData(NetworkVertex vertex) {
-         return seen.get(vertex);
-     }
- 
-     /**
-      * Determines whether a vertex has been seen yet by this traversal.
-      *
-      * @param vertex vertex in question
-      *
-      * @return <tt>true</tt> if vertex has already been seen
-      */
-     private boolean isSeenVertex(NetworkVertex vertex, boolean mustUseGreedy)
-     {
-         return seen.containsKey(vertex) && (mustUseGreedy || !this.mustUseGreedy.get(vertex) );
-     }
      
      /**
--- 117,120 ----
***************
*** 158,190 ****
       * associated with <code>null</code>.
       */
!     private VisitColor putSeenData(NetworkVertex vertex, VisitColor data)
      {
!         return seen.put(vertex, data);
!     }
!     
!     /**
!      * Called when a vertex has been finished (meaning is dependent on traversal
!      * represented by subclass).
!      *
!      * @param vertex vertex which has been finished
!      */
!     private void finishVertex(NetworkVertex vertex) {
!         // do nothing
      }
      
!     private void addUnseenChildrenOf(NetworkVertex vertex, VisitColor previousColor) {
  
          if (company != null && !vertex.canCompanyRunThrough(company)) return;
-         
-         for (NetworkEdge edge : graph.edgesOf(vertex)) {
-             
-             if (previousColor == VisitColor.WHITE || edge.isGreedy()) {  
  
                  NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
!                 if (isSeenVertex(oppositeV, vertex.isSide() && !edge.isGreedy() )) {
!                     encounterVertexAgain(oppositeV, edge);
!                 } else {
!                     encounterVertex(oppositeV, edge);
!                 }
              }
          }
--- 129,160 ----
       * associated with <code>null</code>.
       */
!     private void putSeenData(NetworkVertex vertex, boolean greedy)
      {
!         if (!vertex.isSide()) {
!             seen.put(vertex, greedyState.seen);
!             log.debug("Iterator:  Vertex " + vertex + " seen with greedyState = seen");
!             return;
!         }
!         // side
!         if (seen.containsKey(vertex)){
!             seen.put(vertex, greedyState.done);
!             log.debug("Iterator:  Vertex " + vertex + " seen with greedyState = done");
!         } else if (greedy) {
!             seen.put(vertex, greedyState.greedy);
!             log.debug("Iterator:  Vertex " + vertex + " seen with greedyState = greedy");
!         } else {
!             seen.put(vertex, greedyState.nonGreedy);
!             log.debug("Iterator:  Vertex " + vertex + " seen with greedyState = nonGreedy");
!         }
      }
      
!     private void addUnseenChildrenOf(NetworkVertex vertex, boolean greedy) {
  
          if (company != null && !vertex.canCompanyRunThrough(company)) return;
  
+         for (NetworkEdge edge : graph.edgesOf(vertex)) {
+             if (!greedy || edge.isGreedy()) {
                  NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
!                 encounterVertex(oppositeV, edge);
              }
          }
***************
*** 192,287 ****
      
      private void encounterStartVertex() {
!         putSeenData(startVertex, VisitColor.WHITE);
          stack.add(startVertex);
          startVertex = null;
-         log.debug("Iterator: Added to stack " + startVertex);
      }
  
-     /** copy of standard dfs */
-     private void encounterVertex(NetworkVertex vertex, NetworkEdge edge) {
-         putSeenData(vertex, VisitColor.WHITE);
-         mustUseGreedy.put(vertex, vertex.isSide() && !edge.isGreedy());
-         stack.add(vertex);
-         log.debug("Iterator: Added to stack " + vertex);
-     }
  
!     /** copy of standard dfs */
!     private void encounterVertexAgain(NetworkVertex vertex, NetworkEdge edge) {
!         VisitColor color = getSeenData(vertex);
!         if (color != VisitColor.WHITE) {
!             // We've already visited this vertex; no need to mess with the
!             // stack (either it's BLACK and not there at all, or it's GRAY
!             // and therefore just a sentinel).
              return;
          }
!         int i = stack.indexOf(vertex);
! 
!         // Since we've encountered it before, and it's still WHITE or YELLOW, it
!         // *must* be on the stack.
!         assert (i > -1);
!         stack.remove(i);
!         stack.add(vertex);
!     }
! 
!     /** copy of standard dfs */
!     private boolean isConnectedComponentExhausted() {
!         while (true) {
!             if (stack.isEmpty()) {
!                 return true;
!             }
!             if (peekStack() != null) {
!                 // Found a non-sentinel.
!                 return false;
!             }
! 
!             // Found a sentinel:  pop it, record the finish time,
!             // and then loop to check the rest of the stack.
! 
!             // Pop null we peeked at above.
!             popStack();
! 
!             // This will pop corresponding vertex to be recorded as finished.
!             recordFinish();
!         }
!     }
! 
!     /** copy of standard dfs */
!     private NetworkVertex provideNextVertex() {
!         NetworkVertex v;
!         while (true) {
!             v = popStack();
!             if (v == null) {
!                 // This is a finish-time sentinel we previously pushed.
!                 recordFinish();
!                 // Now carry on with another pop until we find a non-sentinel
!             } else {
!                 // Got a real vertex to start working on
!                 break;
!             }
!         }
! 
!         // Push a sentinel for v onto the stack so that we'll know
!         // when we're done with it.
          stack.add(v);
!         stack.add(null);
!         return v;
      }
  
-     private NetworkVertex popStack()
-     {
-         return stack.remove(stack.size() - 1);
-     }
  
-     private NetworkVertex peekStack()
-     {
-         return stack.get(stack.size() - 1);
-     }
  
-     private void recordFinish()
-     {
-         NetworkVertex v = popStack();
-         if (getSeenData(v) == VisitColor.WHITE)
-             putSeenData(v, VisitColor.BLACK);
-         finishVertex(v);
-     }
  }
--- 162,187 ----
      
      private void encounterStartVertex() {
!         putSeenData(startVertex, true);
          stack.add(startVertex);
+         greedyStack.add(false);
+         log.debug("Iterator: Added to stack " + startVertex +  " with greedy set to false");
          startVertex = null;
      }
  
  
!     private void encounterVertex(NetworkVertex v, NetworkEdge e){
!         if (stack.contains(v)) return;
!         if (v.isSide() && seen.containsKey(v) && (seen.get(v) == greedyState.done || (e.isGreedy() && seen.get(v) == greedyState.nonGreedy)
!                 || (!e.isGreedy() && seen.get(v) == greedyState.greedy) )) {
!             log.debug("Leave vertex " + v + " due to greedState rules");
              return;
          }
!         
          stack.add(v);
!         greedyStack.add(v.isSide() && !e.isGreedy());
!         log.debug("Iterator: Added to stack " + v +  " with greedy set to " + (v.isSide() && !e.isGreedy()));
      }
  
  
  
  }

Index: RevenueAdapter.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueAdapter.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** RevenueAdapter.java	20 Apr 2010 19:45:40 -0000	1.6
--- RevenueAdapter.java	27 Apr 2010 23:24:50 -0000	1.7
***************
*** 2,6 ****
  
  import java.awt.EventQueue;
- import java.awt.Graphics2D;
  import java.awt.geom.GeneralPath;
  import java.awt.geom.Point2D;
--- 2,5 ----
***************
*** 12,25 ****
  import java.util.Map;
  
- import javax.swing.SwingUtilities;
  
- import org.jgrapht.Graph;
  import org.jgrapht.Graphs;
  
- import rails.game.GameManager;
  import rails.game.MapHex;
  import rails.game.PhaseI;
  import rails.game.PublicCompanyI;
- import rails.game.TokenI;
  import rails.game.TrainI;
  import rails.ui.swing.hexmap.HexMap;
--- 11,21 ----
  import java.util.Map;
  
  
  import org.jgrapht.Graphs;
+ import org.jgrapht.graph.SimpleGraph;
  
  import rails.game.MapHex;
  import rails.game.PhaseI;
  import rails.game.PublicCompanyI;
  import rails.game.TrainI;
  import rails.ui.swing.hexmap.HexMap;
***************
*** 28,32 ****
  public class RevenueAdapter implements Runnable {
  
!     private Graph<NetworkVertex, NetworkEdge> graph;
      
      private RevenueCalculator rc;
--- 24,28 ----
  public class RevenueAdapter implements Runnable {
  
!     private SimpleGraph<NetworkVertex, NetworkEdge> graph;
      
      private RevenueCalculator rc;
***************
*** 42,46 ****
  
      
!     public RevenueAdapter(Graph<NetworkVertex, NetworkEdge> graph){
          this.graph = graph;
          
--- 38,42 ----
  
      
!     public RevenueAdapter(SimpleGraph<NetworkVertex, NetworkEdge> graph){
          this.graph = graph;
          
***************
*** 109,120 ****
          }
          
!         if (activatePrediction) {
!             // get max revenue results
!             int[] maxCityRevenues = revenueList(cities, maxCityLength);
!             int[] maxTownRevenues = revenueList(towns, maxTownLength);
! 
!             // set revenue results in revenue calculator
!             rc.setPredictionData(maxCityRevenues, maxTownRevenues);
!         }
      }
      
--- 105,116 ----
          }
          
! //        if (activatePrediction) {
! //            // get max revenue results
! //            int[] maxCityRevenues = revenueList(cities, maxCityLength);
! //            int[] maxTownRevenues = revenueList(towns, maxTownLength);
! //
! //            // set revenue results in revenue calculator
! //            rc.setPredictionData(maxCityRevenues, maxTownRevenues);
! //        }
      }
      
***************
*** 258,261 ****
--- 254,258 ----
      public int calculateRevenue(int startTrain, int finalTrain) {
          if (startTrain < 0 || finalTrain >= trains.size() || startTrain > finalTrain) return -1;
+         rc.initialPredictionRuns(startTrain, finalTrain);
          return rc.calculateRevenue(startTrain, finalTrain);
      }
***************
*** 323,338 ****
              GeneralPath path = new GeneralPath();
              NetworkVertex startVertex = null;
              for (NetworkVertex vertex:run.get(train)) {
                  Point2D vertexPoint = NetworkVertex.getVertexPoint2D(map, vertex);
                  if (startVertex == null) {
                      startVertex = vertex;
                      path.moveTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
                      continue;
                  } else if (startVertex == vertex) {
                      path.moveTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
                      continue;
                  } 
!                 if (vertexPoint != null)
                      path.lineTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
              }
              pathList.add(path);
--- 320,353 ----
              GeneralPath path = new GeneralPath();
              NetworkVertex startVertex = null;
+             NetworkVertex previousVertex = null;
              for (NetworkVertex vertex:run.get(train)) {
                  Point2D vertexPoint = NetworkVertex.getVertexPoint2D(map, vertex);
                  if (startVertex == null) {
                      startVertex = vertex;
+                     previousVertex = vertex;
                      path.moveTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
                      continue;
                  } else if (startVertex == vertex) {
                      path.moveTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
+                     previousVertex = vertex;
                      continue;
                  } 
!                 // draw hidden vertexes
! //                NetworkEdge edge = graph.getEdge(previousVertex, vertex);
! //                if (edge != null) {
! //                    edge = graph.getEdge(vertex, previousVertex);
! //                }
! //                if (edge != null) {
! //                    List<NetworkVertex> hiddenVertexes = edge.getHiddenVertexes();
! //                    for (NetworkVertex v:hiddenVertexes) {
! //                        Point2D vPoint = NetworkVertex.getVertexPoint2D(map, v);
! //                        if (vPoint != null) {
! //                            path.lineTo((float)vPoint.getX(), (float)vPoint.getY());
! //                        }
! //                    }
! //                }
!                 if (vertexPoint != null) {
                      path.lineTo((float)vertexPoint.getX(), (float)vertexPoint.getY());
+                 }
              }
              pathList.add(path);

Index: NetworkGraphBuilder.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkGraphBuilder.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** NetworkGraphBuilder.java	13 Apr 2010 23:21:12 -0000	1.6
--- NetworkGraphBuilder.java	27 Apr 2010 23:24:50 -0000	1.7
***************
*** 240,244 ****
      
      
!     public static Graph<NetworkVertex, NetworkEdge> optimizeGraph(Graph<NetworkVertex, NetworkEdge> graph) {
          
          // convert graph
--- 240,244 ----
      
      
!     public static SimpleGraph<NetworkVertex, NetworkEdge> optimizeGraph(SimpleGraph<NetworkVertex, NetworkEdge> graph) {
          
          // convert graph
***************
*** 297,302 ****
                      if (edges[0].isGreedy() && !graph.containsEdge(firstVertex, secondVertex)) {
                          int distance = edges[0].getDistance() + edges[1].getDistance();
!                         graph.addEdge(firstVertex, secondVertex,
!                                 new NetworkEdge(firstVertex, secondVertex, true, distance));
                          // remove vertex
                          graph.removeVertex(vertex);
--- 297,309 ----
                      if (edges[0].isGreedy() && !graph.containsEdge(firstVertex, secondVertex)) {
                          int distance = edges[0].getDistance() + edges[1].getDistance();
!                         List<NetworkVertex> hiddenVertexes = new ArrayList<NetworkVertex>();
!                         hiddenVertexes.addAll(edges[0].getHiddenVertexes());
!                         hiddenVertexes.add(vertex);
!                         hiddenVertexes.addAll(edges[1].getHiddenVertexes());
!                         NetworkEdge newEdge = 
!                                 new NetworkEdge(firstVertex, secondVertex, true, distance, hiddenVertexes);
!                         graph.addEdge(firstVertex, secondVertex, newEdge);
!                         log.info("NGB: Merged Edges removed Vertex = " + vertex);
!                         log.info("NGB: New Edge = " + newEdge.getConnection() + " with hidden Vertexes " + newEdge.getHiddenVertexes());
                          // remove vertex
                          graph.removeVertex(vertex);

Index: NetworkEdge.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkEdge.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** NetworkEdge.java	20 Apr 2010 19:45:40 -0000	1.4
--- NetworkEdge.java	27 Apr 2010 23:24:50 -0000	1.5
***************
*** 4,7 ****
--- 4,9 ----
  import java.awt.geom.Line2D;
  import java.awt.geom.Point2D;
+ import java.util.ArrayList;
+ import java.util.List;
  
  import rails.ui.swing.hexmap.HexMap;
***************
*** 17,20 ****
--- 19,25 ----
      private final int distance;
      
+     private final List<NetworkVertex> hiddenVertexes;
+     // list of vertexes that were merged into the 
+     
      public NetworkEdge(NetworkVertex source, NetworkVertex target, boolean greedy) {
          this.source = source;
***************
*** 25,35 ****
          else
              this.distance = 0;
      }
      
!     public NetworkEdge(NetworkVertex source, NetworkVertex target, boolean greedy, int distance) {
          this.source = source;
          this.target = target;
          this.greedy = greedy;
          this.distance = distance;
      }
      
--- 30,43 ----
          else
              this.distance = 0;
+         hiddenVertexes = new ArrayList<NetworkVertex>();
      }
      
!     public NetworkEdge(NetworkVertex source, NetworkVertex target, boolean greedy, 
!                 int distance, List<NetworkVertex> hiddenVertexes) {
          this.source = source;
          this.target = target;
          this.greedy = greedy;
          this.distance = distance;
+         this.hiddenVertexes = hiddenVertexes;
      }
      
***************
*** 54,57 ****
--- 62,69 ----
      }
      
+     public List<NetworkVertex> getHiddenVertexes() {
+         return hiddenVertexes;
+     }
+     
      public String getConnection() {
        return source + " - >" + target;

Index: NetworkTrain.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkTrain.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** NetworkTrain.java	15 Apr 2010 21:46:28 -0000	1.3
--- NetworkTrain.java	27 Apr 2010 23:24:50 -0000	1.4
***************
*** 5,9 ****
      private int cities;
      private int towns;
!     private final boolean townsCostNothing;
      private final int multiplyCities;
      private final int multiplyTowns;
--- 5,9 ----
      private int cities;
      private int towns;
!     private final boolean ignoreTowns;
      private final int multiplyCities;
      private final int multiplyTowns;
***************
*** 14,18 ****
          this.cities = cities;
          this.towns = towns;
!         this.townsCostNothing = townsCostNothing;
          this.multiplyCities = multiplyCities;
          this.multiplyTowns = multiplyTowns;
--- 14,18 ----
          this.cities = cities;
          this.towns = towns;
!         this.ignoreTowns = townsCostNothing;
          this.multiplyCities = multiplyCities;
          this.multiplyTowns = multiplyTowns;
***************
*** 21,25 ****
  
      void addToRevenueCalculator(RevenueCalculator rc, int trainId) {
!         rc.setTrain(trainId, cities, towns, townsCostNothing, multiplyCities, multiplyTowns);
      }
  
--- 21,25 ----
  
      void addToRevenueCalculator(RevenueCalculator rc, int trainId) {
!         rc.setTrain(trainId, cities, towns, ignoreTowns, multiplyCities, multiplyTowns);
      }