[Rails-commits] 18xx/rails/algorithms NetworkTrain.java, 1.1, 1.2 RevenueCalculator.java, 1.1, 1.2 RevenueAdapter.java, 1.1, 1.2 NetworkEdge.java, 1.2, 1.3 NetworkVertex.java, 1.4, 1.5 NetworkGraphBuilder.java, 1.5, 1.6

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

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

Modified Files:
	NetworkTrain.java RevenueCalculator.java RevenueAdapter.java 
	NetworkEdge.java NetworkVertex.java NetworkGraphBuilder.java 
Log Message:
Updated revenue calculation: Added revenue prediction and several bug fixes.

Index: RevenueCalculator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueCalculator.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** RevenueCalculator.java	12 Apr 2010 17:37:32 -0000	1.1
--- RevenueCalculator.java	13 Apr 2010 23:21:12 -0000	1.2
***************
*** 29,33 ****
      // static train data
      private final int[] trainMaxCities;
!     private final int[] trainMaxCombined;
      private final boolean[] trainTownsCostNothing;
      private final int[] trainMultiplyCities;
--- 29,33 ----
      // static train data
      private final int[] trainMaxCities;
!     private final int[] trainMaxTowns;
      private final boolean[] trainTownsCostNothing;
      private final int[] trainMultiplyCities;
***************
*** 35,40 ****
      
      // dynamic train data
!     private final int[] trainCityValue;
!     private final int[] trainTownValue;
      private final int[] trainCities;
      private final int[] trainTowns;
--- 35,39 ----
      
      // dynamic train data
!     private final int[] trainCurrentValue;
      private final int[] trainCities;
      private final int[] trainTowns;
***************
*** 52,55 ****
--- 51,59 ----
      private int countEdges;
  
+     // prediction data
+     private int[] maxCityRevenues;
+     private int[] maxTownRevenues;
+     private int[] maxTrainRevenues;
+     
      
      protected static Logger log =
***************
*** 81,88 ****
          trainMultiplyTowns = new int[nbTrains];
          
!         trainCityValue = new int[nbTrains];
!         trainTownValue = new int[nbTrains];
          trainMaxCities = new int[nbTrains];
!         trainMaxCombined = new int[nbTrains];
          trainVisited = new boolean[nbTrains][nbVertexes];
          trainVertexStack = new int[nbTrains][nbVertexes];
--- 85,91 ----
          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];
***************
*** 112,116 ****
      void setTrain(int id, int cities, int towns, boolean townsCostNothing, int multiplyCities, int multiplyTowns) {
          trainMaxCities[id] = cities;
!         trainMaxCombined[id] = cities + towns;
          trainTownsCostNothing[id] = townsCostNothing;
          trainMultiplyCities[id] = multiplyCities;
--- 115,119 ----
      void setTrain(int id, int cities, int towns, boolean townsCostNothing, int multiplyCities, int multiplyTowns) {
          trainMaxCities[id] = cities;
!         trainMaxTowns[id] = towns;
          trainTownsCostNothing[id] = townsCostNothing;
          trainMultiplyCities[id] = multiplyCities;
***************
*** 118,121 ****
--- 121,129 ----
      }
      
+     void setPredictionData(int[] maxCityRevenues, int[] maxTownRevenues) {
+         this.maxCityRevenues = maxCityRevenues;
+         this.maxTownRevenues = maxTownRevenues;
+     }
+     
      int[][] getOptimalRun() {
          return currentBestRun;
***************
*** 123,127 ****
      
      int calculateRevenue(int startTrain, int finalTrain) {
!         log.debug("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
          
          this.finalTrain = finalTrain;
--- 131,142 ----
      
      int calculateRevenue(int startTrain, int finalTrain) {
!         log.info("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
!         
!         // 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];
!         }
          
          this.finalTrain = finalTrain;
***************
*** 131,135 ****
      
      private void runTrain(int trainId) {
!         log.debug("RC: startTrain " + trainId);
          
          // initialize the positions
--- 146,150 ----
      
      private void runTrain(int trainId) {
!         log.debug("RC: runTrain " + trainId);
          
          // initialize the positions
***************
*** 141,159 ****
              int vertexId = startVertexes[i];
              log.debug("RC: Using startVertex nr. " + i + " for train " + trainId);
!             encounterVertex(trainId, startVertexes[i], true);
              // and all edges of it
              boolean evaluateResult = true;
!             for (int j = 0; j < maxNeighbors; j++) {
!                 int neighborId = vertexNeighbors[vertexId][j];
!                 log.debug("RC: Testing Neighbor Nr. " + j + " of startVertex is " + neighborId);
!                 if (neighborId == -1) break; // no more neighbors
!                 if (travelEdge(vertexId, neighborId, true)) {
!                     evaluateResult = false;
!                     trainStartEdge[trainId] = j; // store edge
!                     nextVertex(trainId, neighborId, vertexId);
                  }
              }
              // no more edges to find
!             finalizeVertex(trainId, evaluateResult);
              encounterVertex(trainId, startVertexes[i], false);
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
--- 156,185 ----
              int vertexId = startVertexes[i];
              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;
!             if (!trainTerminated) {
!                 for (int j = 0; j < maxNeighbors; j++) {
!                     int neighborId = vertexNeighbors[vertexId][j];
!                     log.debug("RC: Testing Neighbor Nr. " + j + " of startVertex is " + neighborId);
!                     if (neighborId == -1) break; // no more neighbors
!                     if (travelEdge(vertexId, neighborId, true)) {
!                         evaluateResult = false;
!                         trainStartEdge[trainId] = j; // store edge
!                         nextVertex(trainId, neighborId, vertexId);
!                     }
                  }
              }
+ 
              // no more edges to find
!             finalizeVertex(trainId, startVertexes[i], evaluateResult);
              encounterVertex(trainId, startVertexes[i], false);
              log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
***************
*** 162,167 ****
      }
      
!     private void startBottom(int trainId) {
!         log.debug("RC: startBottom " +trainId);
          
          trainBottomPos[trainId] = trainStackPos[trainId]; // store the stack position where bottom starts
--- 188,193 ----
      }
      
!     private void runBottom(int trainId) {
!         log.debug("RC: runBottom " +trainId);
          
          trainBottomPos[trainId] = trainStackPos[trainId]; // store the stack position where bottom starts
***************
*** 198,203 ****
  
          // 1. add vertex to path and returns true if train terminated (if start = 0, otherwise it is a revisit of the start)
!         encounterVertex(trainId, vertexId, true);
!         boolean trainTerminated = trainTerminated(trainId);
          
          // 2a. visit neighbors, if train has not terminated
--- 224,233 ----
  
          // 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;
!         }
          
          // 2a. visit neighbors, if train has not terminated
***************
*** 219,228 ****
              // 2b. restart at startVertex for bottom part
              if (trainBottomPos[trainId] == 0 && (vertexCity[vertexId] || vertexTown[vertexId])){
!                 startBottom(trainId);
              }
          }
          
          // 3. no more edges to visit from here => evaluate or start new train
!         finalizeVertex(trainId, evaluateResult);
          
          // 4. then leave that vertex
--- 249,258 ----
              // 2b. restart at startVertex for bottom part
              if (trainBottomPos[trainId] == 0 && (vertexCity[vertexId] || vertexTown[vertexId])){
!                 runBottom(trainId);
              }
          }
          
          // 3. no more edges to visit from here => evaluate or start new train
!         finalizeVertex(trainId, vertexId, evaluateResult);
          
          // 4. then leave that vertex
***************
*** 231,235 ****
      }
      
!     private void encounterVertex(int trainId, int vertexId, boolean arrive) {
  
          log.debug("RC: EncounterVertex, trainId = " + trainId + " vertexId = " + vertexId + " arrive = " + arrive);
--- 261,265 ----
      }
      
!     private boolean encounterVertex(int trainId, int vertexId, boolean arrive) {
  
          log.debug("RC: EncounterVertex, trainId = " + trainId + " vertexId = " + vertexId + " arrive = " + arrive);
***************
*** 238,248 ****
          trainVisited[trainId][vertexId] = arrive;
          
          if (arrive) {
              if (vertexCity[vertexId]) {
                  trainCities[trainId]++;
!                 trainCityValue[trainId] += vertexValue[vertexId];
              } else if (vertexTown[vertexId]) {
                  trainTowns[trainId]++;
!                 trainTownValue[trainId] += vertexValue[vertexId];
              }
              trainVertexStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
--- 268,281 ----
          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]) {
                  trainTowns[trainId]++;
!                 trainCurrentValue[trainId] += vertexValue[vertexId] * trainMultiplyTowns[trainId];
!                 valueVertex = true;
              }
              trainVertexStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
***************
*** 251,258 ****
              if (vertexCity[vertexId]) {
                  trainCities[trainId]--;
!                 trainCityValue[trainId] -= vertexValue[vertexId];
              } else if (vertexTown[vertexId]) {
                  trainTowns[trainId]--;
!                 trainTownValue[trainId] -= vertexValue[vertexId];
              }
              trainStackPos[trainId]--; // pull from stack
--- 284,293 ----
              if (vertexCity[vertexId]) {
                  trainCities[trainId]--;
!                 trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyCities[trainId];
!                 valueVertex = true;
              } else if (vertexTown[vertexId]) {
                  trainTowns[trainId]--;
!                 trainCurrentValue[trainId] -= vertexValue[vertexId] * trainMultiplyTowns[trainId];
!                 valueVertex = true;
              }
              trainStackPos[trainId]--; // pull from stack
***************
*** 260,263 ****
--- 295,299 ----
          }
          log.debug("RC: Count Visits = " + countVisits);
+         return valueVertex;
      }
      
***************
*** 310,327 ****
          if (trainTownsCostNothing[trainId]) {
              terminated = trainCities[trainId] == trainMaxCities[trainId];
          } else {
!              terminated =  trainCities[trainId] > trainMaxCities[trainId] ||
!              (trainCities[trainId] + trainTowns[trainId] == trainMaxCombined[trainId]);
          }
          if (terminated) {
              log.debug ("RC: Train " + trainId + " has terminated: " +
              		"cities = " + trainCities[trainId] + " towns = " + trainTowns[trainId] +
!             		"maxCities = " + trainMaxCities[trainId] + "maxCombined = " + trainMaxCombined[trainId]);
          }
          return terminated;
      }
      
!     private void finalizeVertex(int trainId, boolean evaluate) {
!         log.debug("RC: No more edges found for " + trainId);
          if (trainId == finalTrain) {
              if (evaluate) evaluateResults();
--- 346,376 ----
          if (trainTownsCostNothing[trainId]) {
              terminated = trainCities[trainId] == trainMaxCities[trainId];
+         } else if (trainTowns[trainId] == 0) {
+             // default train
+             terminated = trainCities[trainId] + trainTowns[trainId] == trainMaxCities[trainId];
          } else {
!             // plus trains
!             int townDiff = trainMaxTowns[trainId] - trainTowns[trainId];
!             if (townDiff > 0) {
!                 terminated = false;
!             } else if (townDiff == 0) {
!                 terminated = trainCities[trainId] == trainMaxCities[trainId];
!             } else { // negative townDiff, thus too many towns already visited
!                 terminated = trainCities[trainId] == trainMaxCities[trainId] + townDiff;
!             }
          }
          if (terminated) {
              log.debug ("RC: Train " + trainId + " has terminated: " +
              		"cities = " + trainCities[trainId] + " towns = " + trainTowns[trainId] +
!             		"maxCities = " + trainMaxCities[trainId] + "maxTowns = " + trainMaxTowns[trainId]);
          }
          return terminated;
      }
      
!     private void finalizeVertex(int trainId, int vertexId, boolean evaluate) {
!         log.debug("RC: No more edges found at " + vertexId + " for train " + trainId);
!         
!         if (!vertexCity[vertexId] && !vertexTown[vertexId]) return;
!         
          if (trainId == finalTrain) {
              if (evaluate) evaluateResults();
***************
*** 335,347 ****
          int totalValue = 0;
          for (int j = 0; j <= finalTrain; j++) {
-             int trainValue;
              if (trainCities[j] + trainTowns[j] <= 1) {
!                 trainValue = 0; // one station is not enough
              } else {
!                 trainValue = trainCityValue[j] * trainMultiplyCities[j] + trainTownValue[j] * trainMultiplyTowns[j];
!             }   
!             totalValue += trainValue;
!             log.debug("RC: Train " + j + " has value of " + trainValue);
          }
          // compare to current best result
          if (totalValue > currentBestValue) {
--- 384,396 ----
          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);
!             }
          }
+         log.debug("RC: current total value " + totalValue);
+         
          // compare to current best result
          if (totalValue > currentBestValue) {
***************
*** 360,363 ****
--- 409,457 ----
      }
      
+     // 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 (trainTownsCostNothing[trainId]) {
+                     // still TODO
+                     trainValue = 0;
+                 } else if (trainTowns[trainId] == 0) {
+                     // default train
+                     trainValue = trainCurrentValue[j] + 
+                     maxCityRevenues[trainMaxCities[j] - trainCities[j]] * trainMultiplyCities[j];
+                 } else {
+                     // plus trains
+                     int townDiff = trainMaxTowns[trainId] - trainTowns[trainId];
+                     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];
+                     }
+                 }
+             }
+             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);
+ 
+         return terminate;
+     }
+     
+     
      
      @Override
***************
*** 365,375 ****
          StringBuffer buffer = new StringBuffer();
          
!         buffer.append("vertexValue:" + Arrays.toString(vertexValue));
!         buffer.append("vertexCity:" + Arrays.toString(vertexCity));
!         buffer.append("vertexTown:" + Arrays.toString(vertexTown));
!         buffer.append("vertexEdges:" + Arrays.deepToString(vertexNeighbors));
!         buffer.append("edgeGreedy:" + Arrays.deepToString(edgeGreedy));
!         buffer.append("edgeDistance:" + Arrays.deepToString(edgeDistance));
!         buffer.append("startVertexes:" + Arrays.toString(startVertexes)); 
        
          return buffer.toString();
--- 459,473 ----
          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("maxCityRevenues:" + Arrays.toString(maxCityRevenues) + "\n"); 
!         buffer.append("maxTownRevenues:" + Arrays.toString(maxTownRevenues) + "\n"); 
        
          return buffer.toString();

Index: NetworkVertex.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkVertex.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** NetworkVertex.java	12 Apr 2010 17:37:32 -0000	1.4
--- NetworkVertex.java	13 Apr 2010 23:21:12 -0000	1.5
***************
*** 1,4 ****
--- 1,6 ----
  package rails.algorithms;
  
+ import java.util.Collection;
+ import java.util.Comparator;
  import java.util.HashSet;
  import java.util.List;
***************
*** 28,31 ****
--- 30,35 ----
      private final int side;
      
+     private PhaseI phase;
+     
      private boolean tokenable;
      private Set<PublicCompanyI> companiesHaveToken;
***************
*** 33,36 ****
--- 37,44 ----
  
      public NetworkVertex(MapHex hex, Station station) {
+         this(hex, station, null);
+     }
+     
+     public NetworkVertex(MapHex hex, Station station, PhaseI phase) {
          this.type = VertexType.STATION;
          this.hex = hex;
***************
*** 38,41 ****
--- 46,51 ----
          this.side = 0;
          
+         this.phase = phase;
+         
          String t = station.getType();
          if (t.equals(Station.TOWN)){
***************
*** 71,74 ****
--- 81,86 ----
          this.station = null;
          this.side = (side % 6);
+         
+         this.phase = null;
          this.tokenable = false;
          this.companiesHaveToken = null;
***************
*** 81,84 ****
--- 93,98 ----
          this.station = null;
          this.side = 0;
+         
+         this.phase = null;
          this.tokenable = false;
          this.companiesHaveToken = null;
***************
*** 133,136 ****
--- 147,162 ----
      }
      
+     public int getValue() {
+         return getValue(this.phase);
+     }
+ 
+     public PhaseI getPhase(){
+         return phase;
+     }
+     
+     public void setPhase(PhaseI phase){
+         this.phase = phase;
+     }
+     
      /**
       * Checks if a vertex is fully tokened
***************
*** 201,203 ****
--- 227,244 ----
      }
      
+     public static final class ValueOrder implements Comparator<NetworkVertex> {
+         
+         public int compare(NetworkVertex vA, NetworkVertex vB) {
+             int result = -((Integer)vA.getValue()).compareTo(vB.getValue()); // compare by value, descending
+             if (result == 0)
+                 result = vA.compareTo(vB); // otherwise use natural ordering
+             return result;
+         }
+     }
+ 
+     public static void setPhaseForAll(Collection<NetworkVertex> vertexes, PhaseI phase) {
+         for (NetworkVertex v:vertexes)
+             v.setPhase(phase);
+     }
+     
  }

Index: RevenueAdapter.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueAdapter.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** RevenueAdapter.java	12 Apr 2010 17:37:32 -0000	1.1
--- RevenueAdapter.java	13 Apr 2010 23:21:12 -0000	1.2
***************
*** 2,5 ****
--- 2,7 ----
  
  import java.util.ArrayList;
+ import java.util.Arrays;
+ import java.util.Collections;
  import java.util.HashMap;
  import java.util.List;
***************
*** 22,25 ****
--- 24,28 ----
      private List<NetworkVertex> vertexes;
      private List<NetworkEdge> edges;
+     private List<NetworkVertex> startVertexes;
      private List<NetworkTrain> trains;
      
***************
*** 30,33 ****
--- 33,37 ----
          this.edges = new ArrayList<NetworkEdge>(graph.edgeSet());
          this.trains = new ArrayList<NetworkTrain>();
+         this.startVertexes = new ArrayList<NetworkVertex>();
      }
      
***************
*** 48,68 ****
      }
      
      public void populateRevenueCalculator(PublicCompanyI company, PhaseI phase){
          if (rc == null) initRevenueCalculator();
!         
          // set vertexes
          for (int id=0; id < vertexes.size(); id++){ 
              NetworkVertex v = vertexes.get(id);
              if (v.isHQ()) {
!             // HQ is not added to list, but used to assign startVertexes 
!                 List<NetworkVertex> hqNeighbors = Graphs.neighborListOf(graph, v);
!                 int[] startVertexes = new int[hqNeighbors.size()];
!                 for (int j=0; j < hqNeighbors.size(); j++) {
!                     startVertexes[j] = vertexes.lastIndexOf(hqNeighbors.get(j));
!                 }
!                 rc.setStartVertexes(startVertexes);
              } else {
                  // prepare values
!                 int value = v.getValue(phase);
                  boolean city = v.isCityType();
                  boolean town = v.isTownType();
--- 52,111 ----
      }
      
+     
+     private int[] revenueList(List<NetworkVertex> vertexes, int maxLength) {
+         Collections.sort(vertexes, new NetworkVertex.ValueOrder());
+         
+         int[] revenue = new int[maxLength + 1];
+         revenue[0] = 0;
+         for (int j=1; j <= maxLength; j++) {
+             revenue[j] = revenue[j-1] + vertexes.get(j-1).getValue();
+         }
+         
+         return revenue;
+     }
+     
+     public void activateRevenuePrediction() {
+         
+         // separate vertexes
+         List<NetworkVertex> cities = new ArrayList<NetworkVertex>();
+         List<NetworkVertex> towns = new ArrayList<NetworkVertex>();
+         for (NetworkVertex vertex: vertexes) {
+             if (vertex.isCityType()) cities.add(vertex);
+             if (vertex.isTownType()) towns.add(vertex);
+         }
+         
+         // check train lengths
+         int maxCityLength = 0, maxTownLength = 0;
+         for (NetworkTrain train: trains) {
+             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);
+         Collections.sort(vertexes, new NetworkVertex.ValueOrder());
+         
          for (int id=0; id < vertexes.size(); id++){ 
              NetworkVertex v = vertexes.get(id);
              if (v.isHQ()) {
!             // HQ is not added to list, but used to assign startVertexes
!                 startVertexes.addAll(Graphs.neighborListOf(graph, v));
              } else {
                  // prepare values
!                 int value = v.getValue();
                  boolean city = v.isCityType();
                  boolean town = v.isTownType();
***************
*** 75,83 ****
                      }
                  }
                  e[j] = -1; // stop 
                  rc.setVertex(id, value, city, town, e);
              }
          }
!             
          // set edges
          for (int id=0; id < edges.size(); id++) {
--- 118,136 ----
                      }
                  }
+                 // sort by value order
+                 Arrays.sort(e, 0, j);
                  e[j] = -1; // stop 
                  rc.setVertex(id, value, city, town, e);
              }
          }
! 
!         // set startVertexes
!         int[] sv = new int[startVertexes.size()];
!         for (int j=0; j < startVertexes.size(); j++) {
!             sv[j] = vertexes.lastIndexOf(startVertexes.get(j));
!         }
!         Arrays.sort(sv); // sort by value order 
!         rc.setStartVertexes(sv);
! 
          // set edges
          for (int id=0; id < edges.size(); id++) {
***************
*** 115,120 ****
          String trainName = railsTrain.getName();
          
!         NetworkTrain networkTrain = new NetworkTrain(cities, towns, townsCostNothing, multiplyCities, multiplyTowns, trainName); 
!         trains.add(networkTrain);
      }
      
--- 168,175 ----
          String trainName = railsTrain.getName();
          
!         if (cities > 0 || towns > 0) { // protection against pullman
!             NetworkTrain networkTrain = new NetworkTrain(cities, towns, townsCostNothing, multiplyCities, multiplyTowns, trainName); 
!             trains.add(networkTrain);
!         }
      }
      
***************
*** 147,150 ****
--- 202,209 ----
      }
      
+     public void addStartVertex(NetworkVertex v) {
+         startVertexes.add(v);
+     }
+     
      public Map<NetworkTrain, List<NetworkVertex>> getOptimalRun() {
          int[][] optimalRunRaw = rc.getOptimalRun();

Index: NetworkGraphBuilder.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkGraphBuilder.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** NetworkGraphBuilder.java	12 Apr 2010 17:37:32 -0000	1.5
--- NetworkGraphBuilder.java	13 Apr 2010 23:21:12 -0000	1.6
***************
*** 20,23 ****
--- 20,24 ----
  import org.jgrapht.Graphs;
  import org.jgrapht.ext.JGraphModelAdapter;
+ import org.jgrapht.graph.Multigraph;
  import org.jgrapht.graph.SimpleGraph;
  import org.jgrapht.graph.Subgraph;
***************
*** 163,173 ****
          
          for (TokenI token:tokens){
!             if (!(token instanceof BaseToken)) continue;
!             TokenHolder holder = token.getHolder();
!             if (!(holder instanceof City)) continue;
!             City city = (City)holder;
!             MapHex hex = city.getHolder();
!             Station station = city.getRelatedStation();
!             NetworkVertex vertex = getVertex(hex, station);
              vertexes.add(vertex);
              // add connection to graph
--- 164,169 ----
          
          for (TokenI token:tokens){
!             NetworkVertex vertex = getVertex(token);
!             if (vertex == null) continue;
              vertexes.add(vertex);
              // add connection to graph
***************
*** 196,199 ****
--- 192,205 ----
      }
      
+     public NetworkVertex getVertex(TokenI token) {
+         if (!(token instanceof BaseToken)) return null;
+         TokenHolder holder = token.getHolder();
+         if (!(holder instanceof City)) return null;
+         City city = (City)holder;
+         MapHex hex = city.getHolder();
+         Station station = city.getRelatedStation();
+         return getVertex(hex, station);
+     }
+     
      private NetworkVertex getVertex(MapHex hex, Station station) {
          return mapVertexes.get(hex.getName() + "." + -station.getNumber());
***************
*** 234,239 ****
      
      
!     public static void optimizeGraph(Graph<NetworkVertex, NetworkEdge> graph) {
          while (removeVertexes(graph));
      }
      
--- 240,262 ----
      
      
!     public static Graph<NetworkVertex, NetworkEdge> optimizeGraph(Graph<NetworkVertex, NetworkEdge> graph) {
!         
!         // convert graph
! //        Graph<NetworkVertex, NetworkEdge> graph = new Multigraph<NetworkVertex, NetworkEdge>(NetworkEdge.class);
! //        Graphs.addGraph(graph, graphIn);
!         
!         // increase greedness
!         for (NetworkEdge edge:graph.edgeSet()) {
!             NetworkVertex source = edge.getSource();
!             NetworkVertex target = edge.getTarget();
!             if ((source.isSide() && graph.edgesOf(source).size() == 2 || source.isStation()) &&
!                     target.isSide() && graph.edgesOf(target).size() == 2 || target.isStation()) {
!                 edge.setGreedy(true);
!             }
!         }
!       
          while (removeVertexes(graph));
+         
+         return graph;
      }
      
***************
*** 243,265 ****
          boolean removed = false;
          for (NetworkVertex vertex:graph.vertexSet()) {
!             if (!vertex.isSide()) continue;
              
!             if (graph.edgesOf(vertex).size() == 1) { 
                  graph.removeVertex(vertex);
                  removed = true;
                  break;
!             } else  if (graph.edgesOf(vertex).size() == 2) { // vertex is not necessary
!                 // reconnect
!                 NetworkEdge[] edges = graph.edgesOf(vertex).toArray(new NetworkEdge[2]);
!                 NetworkVertex firstVertex = Graphs.getOppositeVertex(graph, edges[0], vertex);
!                 NetworkVertex secondVertex = Graphs.getOppositeVertex(graph, edges[1], vertex);
!                 boolean greedy = edges[0].isGreedy() || edges[1].isGreedy();
!                 int distance = edges[0].getDistance() + edges[1].getDistance();
!                 graph.addEdge(firstVertex, secondVertex,
!                         new NetworkEdge(firstVertex, secondVertex, greedy, distance));
!                 // remove vertex
                  graph.removeVertex(vertex);
                  removed = true;
                  break;
              }
          }     
--- 266,308 ----
          boolean removed = false;
          for (NetworkVertex vertex:graph.vertexSet()) {
!             Set<NetworkEdge> vertexEdges = graph.edgesOf(vertex);
              
!             // remove singletons
!             if (vertexEdges.size() == 0) {
                  graph.removeVertex(vertex);
                  removed = true;
                  break;
!             }
!             
!             // the following only for side vertexes
!             if (!vertex.isSide()) continue;
! 
!             if (vertexEdges.size() == 1) { 
                  graph.removeVertex(vertex);
                  removed = true;
                  break;
+             } else  if (vertexEdges.size() == 2) { // vertex is not necessary
+                 NetworkEdge[] edges = vertexEdges.toArray(new NetworkEdge[2]);
+                 if (edges[0].isGreedy() == edges[1].isGreedy()) {
+                     if (!edges[0].isGreedy()) {
+                         // two non greedy edges indicate a deadend
+                         graph.removeVertex(vertex);
+                         removed = true;
+                         break;
+                     } 
+                     // greedy case:
+                     NetworkVertex firstVertex = Graphs.getOppositeVertex(graph, edges[0], vertex);
+                     NetworkVertex secondVertex = Graphs.getOppositeVertex(graph, edges[1], vertex);
+                     // merge greed edges if the vertexes are not already connected
+                     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);
+                         removed = true;
+                         break;
+                     }
+                 }
              }
          }     

Index: NetworkEdge.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkEdge.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** NetworkEdge.java	12 Apr 2010 17:37:32 -0000	1.2
--- NetworkEdge.java	13 Apr 2010 23:21:12 -0000	1.3
***************
*** 7,11 ****
      private final NetworkVertex target;
      
!     private final boolean greedy;
      
      private final int distance;
--- 7,11 ----
      private final NetworkVertex target;
      
!     private boolean greedy;
      
      private final int distance;
***************
*** 40,43 ****
--- 40,47 ----
      }
    
+     public void setGreedy(boolean greedy) {
+        this.greedy = greedy;
+     }
+     
      public int getDistance() {
          return distance;

Index: NetworkTrain.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkTrain.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** NetworkTrain.java	12 Apr 2010 17:37:32 -0000	1.1
--- NetworkTrain.java	13 Apr 2010 23:21:12 -0000	1.2
***************
*** 24,27 ****
--- 24,39 ----
      }
  
+     int getCities(){
+         return cities;
+     }
+     
+     int getTowns() {
+         return towns;
+     }
+     
+     int calculateRevenue(int[] cityValues, int[] townValues) {
+         return cityValues[cities] * multiplyCities + townValues[towns] * multiplyTowns; 
+     }
+     
      public String toString() {
          return trainName;