[Rails-commits] 18xx/rails/algorithms RevenueCalculator.java, 1.4, 1.5 RevenueAdapter.java, 1.4, 1.5 NetworkIterator.java, 1.3, 1.4

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

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

Modified Files:
	RevenueCalculator.java RevenueAdapter.java 
	NetworkIterator.java 
Log Message:
Several bug fixes to the revenue calculation and network iterator

Index: RevenueCalculator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueCalculator.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** RevenueCalculator.java	16 Apr 2010 16:38:21 -0000	1.4
--- RevenueCalculator.java	19 Apr 2010 19:35:38 -0000	1.5
***************
*** 46,53 ****
--- 46,59 ----
      // dynamic run data
      private int finalTrain;
+     private boolean useRevenuePrediction;
+     
      private int currentBestValue;
      private final int [][] currentBestRun;
+     
      private int countVisits;
      private int countEdges;
+     private int nbEdges;
+     private int nbEvaluations;
+     private int nbPredictions;
  
      // prediction data
***************
*** 59,64 ****
      private RevenueAdapter revenueAdapter;
      
-     private boolean stopped;
-     
      protected static Logger log =
          Logger.getLogger(RevenueCalculator.class.getPackage().getName());
--- 65,68 ----
***************
*** 101,104 ****
--- 105,110 ----
          currentBestRun = new int[nbTrains][nbVertexes];
          
+         useRevenuePrediction = false;
+         
      }
  
***************
*** 130,133 ****
--- 136,140 ----
          this.maxCityRevenues = maxCityRevenues;
          this.maxTownRevenues = maxTownRevenues;
+         useRevenuePrediction = true;
      }
      
***************
*** 136,140 ****
--- 143,162 ----
      }
      
+     int getNumberOfEvaluations() {
+         return nbEvaluations;
+     }
+     
      private void notifyRevenueAdapter(final int revenue, final boolean finalResult) {
+         String modifier;
+         if (finalResult)
+             modifier = "final";
+         else
+             modifier = "new best";
+         StringBuffer statistics = new StringBuffer();
+         statistics.append(nbEvaluations + " evaluations");
+         if (useRevenuePrediction)
+             statistics.append(", " + nbPredictions + " predictions");
+         statistics.append(" and " + nbEdges + " edges travelled.");
+         log.info("Report " + modifier + " result of " +  revenue + " after " + statistics.toString());
          revenueAdapter.notifyRevenueListener(revenue, finalResult);
      }
***************
*** 143,153 ****
          log.info("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
          
!         stopped = false;
!         
          // initialize maximum train revenues 
!         maxTrainRevenues = new int[nbTrains];
!         for (int j=0; j < nbTrains; j++) {
!            maxTrainRevenues[j] = maxCityRevenues[trainMaxCities[j]] * trainMultiplyCities[j] + 
!                maxTownRevenues[trainMaxTowns[j]] * trainMultiplyTowns[j];
          }
          
--- 165,177 ----
          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];
!             }
          }
          
***************
*** 173,184 ****
              log.debug("RC: Using startVertex nr. " + i + " for train " + trainId);
  
!             // check train termination and revenue prediction after visit
!             boolean trainTerminated; 
!             if (encounterVertex(trainId, startVertexes[i], true)) {
!                 trainTerminated = trainTerminated(trainId) || (predictRevenues(trainId));
!             } else {
!                 trainTerminated = false;
              }
! 
              // and all edges of it
              boolean evaluateResult = true;
--- 197,214 ----
              log.debug("RC: Using startVertex nr. " + i + " for train " + trainId);
  
!             // encounterVertex adds value and returns true if value vertex
!             boolean trainTerminated = false; 
!             if (encounterVertex(trainId, vertexId, true)) {
!                 if (useRevenuePrediction && predictRevenues(trainId)) {
!                     // cannot beat current best value => leave immediately
!                     encounterVertex(trainId, vertexId, false);
!                     log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
!                     continue;
!                 } else  {
!                     // check usual train termination
!                     trainTerminated = trainTerminated(trainId);
!                 }
              }
!             
              // and all edges of it
              boolean evaluateResult = true;
***************
*** 197,202 ****
  
              // no more edges to find
!             finalizeVertex(trainId, startVertexes[i], evaluateResult);
!             encounterVertex(trainId, startVertexes[i], false);
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
          }
--- 227,232 ----
  
              // no more edges to find
!             finalizeVertex(trainId, vertexId, evaluateResult);
!             encounterVertex(trainId, vertexId, false);
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
          }
***************
*** 239,248 ****
      private void nextVertex(int trainId, int vertexId, int previousId) {
  
!         // 1. add vertex to path and returns true if train terminated (if start = 0, otherwise it is a revisit of the start)
!         boolean trainTerminated; 
          if (encounterVertex(trainId, vertexId, true)) {
!             trainTerminated = trainTerminated(trainId) || (predictRevenues(trainId));
!         } else {
!             trainTerminated = false;
          }
          
--- 269,284 ----
      private void nextVertex(int trainId, int vertexId, int previousId) {
  
!         // 1. encounterVertex adds value and returns true if value vertex
!         boolean trainTerminated = false; 
          if (encounterVertex(trainId, vertexId, true)) {
!             if (useRevenuePrediction && predictRevenues(trainId)) {
!                 // cannot beat current best value => leave immediately
!                 encounterVertex(trainId, vertexId, false);
!                 returnEdge(trainId);
!                 return;
!             } else  {
!                 // check usual train termination
!                 trainTerminated = trainTerminated(trainId);
!             }
          }
          
***************
*** 322,326 ****
              edgeUsed[startVertex][endVertex] = true;
              edgeUsed[endVertex][startVertex] = true;
!             countEdges++;
              log.debug("RC: Count Edges = " + countEdges);
              return true;
--- 358,362 ----
              edgeUsed[startVertex][endVertex] = true;
              edgeUsed[endVertex][startVertex] = true;
!             countEdges++; nbEdges++;
              log.debug("RC: Count Edges = " + countEdges);
              return true;
***************
*** 407,410 ****
--- 443,447 ----
              }
          }
+         nbEvaluations++;
          log.debug("RC: current total value " + totalValue);
          
***************
*** 430,434 ****
      private boolean predictRevenues(int trainId){
          int totalValue = 0;
-         
          for (int j = 0; j <= finalTrain; j++) {
              int trainValue;
--- 467,470 ----
***************
*** 438,445 ****
                  trainValue =  maxTrainRevenues[j];
              } else { // the current train
!                 if (trainTownsCostNothing[trainId]) {
                      // still TODO
                      trainValue = 0;
!                 } else if (trainTowns[trainId] == 0) {
                      // default train
                      trainValue = trainCurrentValue[j] + 
--- 474,481 ----
                  trainValue =  maxTrainRevenues[j];
              } else { // the current train
!                 if (trainTownsCostNothing[j]) {
                      // still TODO
                      trainValue = 0;
!                 } else if (trainTowns[j] == 0) {
                      // default train
                      trainValue = trainCurrentValue[j] + 
***************
*** 447,451 ****
                  } else {
                      // plus trains
!                     int townDiff = trainMaxTowns[trainId] - trainTowns[trainId];
                      if (townDiff > 0) {
                          trainValue = trainCurrentValue[j] + 
--- 483,487 ----
                  } else {
                      // plus trains
!                     int townDiff = trainMaxTowns[j] - trainTowns[j];
                      if (townDiff > 0) {
                          trainValue = trainCurrentValue[j] + 
***************
*** 460,469 ****
                      }
                  }
              }
              log.debug("RC: Train " + j + " has value of " + trainValue);
!             totalValue += Math.min(trainValue, maxTrainRevenues[trainId]);
          }
  
!         boolean terminate = (totalValue < currentBestValue);
          if (terminate) log.debug("Run terminated due to predicted value of " +  totalValue);
  
--- 496,508 ----
                      }
                  }
+                 trainValue = Math.min(trainValue, maxTrainRevenues[j]); 
              }
              log.debug("RC: Train " + j + " has value of " + trainValue);
!             totalValue += trainValue;
          }
  
!         nbPredictions++;
!         
!         boolean terminate = (totalValue <= currentBestValue);
          if (terminate) log.debug("Run terminated due to predicted value of " +  totalValue);
  
***************
*** 472,477 ****
      
      
-     
-     
      @Override
      public String toString() {
--- 511,514 ----

Index: RevenueAdapter.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueAdapter.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** RevenueAdapter.java	16 Apr 2010 16:38:21 -0000	1.4
--- RevenueAdapter.java	19 Apr 2010 19:35:38 -0000	1.5
***************
*** 61,64 ****
--- 61,66 ----
      public void refreshRevenueCalculator() {
          rc = null;
+         // refresh startVertexes
+         this.startVertexes = new ArrayList<NetworkVertex>();
      }
      
***************
*** 76,80 ****
      }
      
!     public void activateRevenuePrediction() {
          
          // separate vertexes
--- 78,82 ----
      }
      
!     private void prepareRevenuePrediction(boolean activatePrediction) {
          
          // separate vertexes
***************
*** 92,122 ****
          int maxCityLength = 0, maxTownLength = 0;
          for (NetworkTrain train: trains) {
!             int increaseTowns = 0;
              if (train.getCities() > maxCities) {
!                 increaseTowns = maxCities - train.getCities();
                  train.setCities(maxCities);
              }
!             int trainTowns = train.getTowns() + increaseTowns;
!             if (trainTowns > maxTowns) {
!                 train.setTowns(maxTowns);
!             }
              maxCityLength = Math.max(maxCityLength, train.getCities());
              maxTownLength = Math.max(maxTownLength, train.getTowns());
          }
          
!         // get max revenue results
!         int[] maxCityRevenues = revenueList(cities, maxCityLength);
!         int[] maxTownRevenues = revenueList(towns, maxTownLength);
  
!         // set revenue results in revenue calculator
!         rc.setPredictionData(maxCityRevenues, maxTownRevenues);
      }
      
      
!     public void populateRevenueCalculator(PublicCompanyI company, PhaseI phase){
          if (rc == null) initRevenueCalculator();
  
!         // set vertexes
! 
          // Define ordering on vertexes by value
          NetworkVertex.setPhaseForAll(vertexes, phase);
--- 94,125 ----
          int maxCityLength = 0, maxTownLength = 0;
          for (NetworkTrain train: trains) {
!             int trainTowns = train.getTowns();
              if (train.getCities() > maxCities) {
!                 trainTowns = trainTowns+ train.getCities() - maxCities;
                  train.setCities(maxCities);
              }
!             train.setTowns(Math.min(trainTowns, maxTowns));
! 
              maxCityLength = Math.max(maxCityLength, train.getCities());
              maxTownLength = Math.max(maxTownLength, train.getTowns());
          }
          
!         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);
!         }
      }
      
      
!     public void populateRevenueCalculator(PublicCompanyI company, PhaseI phase, boolean activatePrediction){
          if (rc == null) initRevenueCalculator();
  
!         // prepare and optionaly activate revenue prediction
!         prepareRevenuePrediction(activatePrediction);
!         
          // Define ordering on vertexes by value
          NetworkVertex.setPhaseForAll(vertexes, phase);

Index: NetworkIterator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkIterator.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** NetworkIterator.java	12 Apr 2010 17:37:32 -0000	1.3
--- NetworkIterator.java	19 Apr 2010 19:35:38 -0000	1.4
***************
*** 26,41 ****
           */
          WHITE,
! 
!         /**
!          * Vertex has not been returned via iterator yet, but has to use autoedge
!          */
!         YELLOW,
! 
!         /**
!          * 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
--- 26,34 ----
           */
          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
***************
*** 50,53 ****
--- 43,47 ----
       */
      private Map<NetworkVertex, VisitColor> seen = new HashMap<NetworkVertex, VisitColor>();
+     private Map<NetworkVertex, Boolean> mustUseGreedy = new HashMap<NetworkVertex, Boolean>();
      private NetworkVertex startVertex;
  
***************
*** 148,154 ****
       * @return <tt>true</tt> if vertex has already been seen
       */
!     private boolean isSeenVertex(NetworkVertex vertex)
      {
!         return seen.containsKey(vertex);
      }
      
--- 142,148 ----
       * @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) );
      }
      
***************
*** 188,192 ****
  
                  NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
!                 if (isSeenVertex(oppositeV)) {
                      encounterVertexAgain(oppositeV, edge);
                  } else {
--- 182,186 ----
  
                  NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
!                 if (isSeenVertex(oppositeV, vertex.isSide() && !edge.isGreedy() )) {
                      encounterVertexAgain(oppositeV, edge);
                  } else {
***************
*** 206,215 ****
      /** copy of standard dfs */
      private void encounterVertex(NetworkVertex vertex, NetworkEdge edge) {
!         VisitColor color = VisitColor.WHITE;
!         if (vertex.isSide() && !edge.isGreedy())
!             color = VisitColor.YELLOW;
!         putSeenData(vertex, color);
          stack.add(vertex);
!         log.debug("Iterator: Added to stack " + vertex + " with color " + color);
      }
  
--- 200,207 ----
      /** 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);
      }
  
***************
*** 217,221 ****
      private void encounterVertexAgain(NetworkVertex vertex, NetworkEdge edge) {
          VisitColor color = getSeenData(vertex);
!         if (color != VisitColor.WHITE && color != VisitColor.YELLOW) {
              // 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
--- 209,213 ----
      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
***************
*** 289,293 ****
      {
          NetworkVertex v = popStack();
!         putSeenData(v, VisitColor.BLACK);
          finishVertex(v);
      }
--- 281,286 ----
      {
          NetworkVertex v = popStack();
!         if (getSeenData(v) == VisitColor.WHITE)
!             putSeenData(v, VisitColor.BLACK);
          finishVertex(v);
      }