[Rails-commits] 18xx/rails/algorithms RevenueCalculatorSimple.java, NONE, 1.1 NetworkCompanyGraph.java, NONE, 1.1 RevenueCalculatorMulti.java, NONE, 1.1 RevenueCalculator.java, 1.17, 1.18 RevenueAdapter.java, 1.21, 1.22 RevenueTrainRun.java, 1.8, 1.9 NetworkEdge.java, 1.8, 1.9 NetworkVertex.java, 1.17, 1.18 NetworkIterator.java, 1.6, 1.7 NetworkGraphBuilder.java, 1.14, 1.15

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

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

Modified Files:
	RevenueCalculator.java RevenueAdapter.java 
	RevenueTrainRun.java NetworkEdge.java NetworkVertex.java 
	NetworkIterator.java NetworkGraphBuilder.java 
Added Files:
	RevenueCalculatorSimple.java NetworkCompanyGraph.java 
	RevenueCalculatorMulti.java 
Log Message:
First commit of the multigraph revenue calculation, still the old algorithm active

Index: NetworkVertex.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkVertex.java,v
retrieving revision 1.17
retrieving revision 1.18
diff -C2 -d -r1.17 -r1.18
*** NetworkVertex.java	24 May 2010 20:37:17 -0000	1.17
--- NetworkVertex.java	17 Jun 2010 22:10:53 -0000	1.18
***************
*** 398,402 ****
      
      /**
!      * Returns all vertices in a specified collection of hexes
       */
      public static Set<NetworkVertex> getVerticesByHexes(Collection<NetworkVertex> vertices, Collection<MapHex> hexes) {
--- 398,402 ----
      
      /**
!      * Filters all vertices from a collection of vertices that lay in a specified collection of hexes
       */
      public static Set<NetworkVertex> getVerticesByHexes(Collection<NetworkVertex> vertices, Collection<MapHex> hexes) {

--- NEW FILE: NetworkCompanyGraph.java ---
package rails.algorithms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;
import org.jgrapht.Graphs;
import org.jgrapht.graph.Multigraph;
import org.jgrapht.graph.SimpleGraph;
import org.jgrapht.graph.Subgraph;

import rails.algorithms.RevenueAdapter.EdgeTravel;
import rails.game.PublicCompanyI;
import rails.game.TokenI;

/**
 * This class stores and creates the various graphs
 * defined for each company
 *
 */
public class NetworkCompanyGraph {
    protected static Logger log =
        Logger.getLogger(NetworkCompanyGraph.class.getPackage().getName());

    private final NetworkGraphBuilder graphBuilder;
    private final PublicCompanyI company;
    
    private SimpleGraph<NetworkVertex, NetworkEdge> routeGraph;
    private SimpleGraph<NetworkVertex, NetworkEdge> revenueGraph;

    private Multigraph<NetworkVertex, NetworkEdge> phase2Graph;
    private Map<NetworkEdge, Set<NetworkEdge>> partial2route;
    private Map<NetworkEdge, Set<NetworkEdge>> route2partial;
    
    private Collection<NetworkVertex> protectedVertices;
    
    private NetworkCompanyGraph(NetworkGraphBuilder graphBuilder, PublicCompanyI company) {
        this.graphBuilder = graphBuilder;
        this.company = company;
        this.routeGraph = null;
        this.revenueGraph = null;
        this.phase2Graph = null;
    }
    
    public static NetworkCompanyGraph create(NetworkGraphBuilder graphBuilder, PublicCompanyI company) {
       return new NetworkCompanyGraph(graphBuilder, company);
    }
    
    public SimpleGraph<NetworkVertex, NetworkEdge> createRouteGraph(boolean addHQ) {
        // get mapgraph from builder
        SimpleGraph<NetworkVertex, NetworkEdge> mapGraph = graphBuilder.getMapGraph();
        
        // set sinks on mapgraph
        NetworkVertex.initAllRailsVertices(mapGraph.vertexSet(), company, null);
        
        // initialized simple graph
        SimpleGraph<NetworkVertex, NetworkEdge> graph = new SimpleGraph<NetworkVertex, NetworkEdge>(NetworkEdge.class);
        // add Company HQ
        NetworkVertex hqVertex = new NetworkVertex(company); 
        graph.addVertex(hqVertex);
        
        // create vertex set for subgraph
        List<NetworkVertex> tokenVertexes = getCompanyBaseTokenVertexes(company);
        Set<NetworkVertex> vertexes = new HashSet<NetworkVertex>();
        
        for (NetworkVertex vertex:tokenVertexes){
            // allow to leave tokenVertices even if those are sinks
            boolean storeSink = vertex.isSink(); vertex.setSink(false);
            vertexes.add(vertex);
            // add connection to graph
            graph.addVertex(vertex);
            graph.addEdge(vertex, hqVertex, new NetworkEdge(vertex, hqVertex, false));
            NetworkIterator iterator = new NetworkIterator(mapGraph, vertex, company);
            for (;iterator.hasNext();)
                vertexes.add(iterator.next());
            // restore sink property
            vertex.setSink(storeSink);
        }

        Subgraph<NetworkVertex, NetworkEdge, SimpleGraph<NetworkVertex, NetworkEdge>> subGraph = 
            new Subgraph<NetworkVertex, NetworkEdge, SimpleGraph<NetworkVertex, NetworkEdge>>
            (mapGraph, vertexes);
        // now add all vertexes and edges to the graph
        Graphs.addGraph(graph, subGraph);

        // if addHQ is not set remove HQ vertex
        if (!addHQ) graph.removeVertex(hqVertex);
        
        // deactivate sinks on mapgraph
        NetworkVertex.initAllRailsVertices(mapGraph.vertexSet(), null, null);
        
        // store and return
        routeGraph = graph;
        return graph;
    }
    
    public List<NetworkVertex> getCompanyBaseTokenVertexes(PublicCompanyI company) {
        List<NetworkVertex> vertexes = new ArrayList<NetworkVertex>();
        for (TokenI token:company.getTokens()){
            NetworkVertex vertex = graphBuilder.getVertex(token);
            if (vertex == null) continue;
            vertexes.add(vertex);
        }
        return vertexes;
    }
    
    public SimpleGraph<NetworkVertex, NetworkEdge> createRevenueGraph(Collection<NetworkVertex> protectedVertices) {
 
        // store protected vertices
        this.protectedVertices = protectedVertices;
            
        // optimize graph (optimizeGraph clones the graph)
        revenueGraph = NetworkGraphBuilder.optimizeGraph(routeGraph, protectedVertices);

        return revenueGraph;
    }

    Map<NetworkEdge, EdgeTravel> getPhaseTwoEdgeSets(RevenueAdapter revenueAdapter) {
        
        Map<NetworkEdge, EdgeTravel> edgeSets = new HashMap<NetworkEdge, EdgeTravel>();
        // convert route2partial and partial2route into edgesets
        for (NetworkEdge route:route2partial.keySet()){
            EdgeTravel edgeTravel = revenueAdapter.new EdgeTravel(); 
            for (NetworkEdge partial:route2partial.get(route)) {
                if (partial2route.get(partial).size() >= 2) { // only keep true sets
                    edgeTravel.set.addAll(partial2route.get(partial));
                }
            }
            edgeTravel.set.remove(route);
          route.setRouteCosts(edgeTravel.set.size());
//          route.setRouteCosts(-(route.getSource().getValue() + route.getTarget().getValue()));
            // define route costs as the size of the travel set
            if (edgeTravel.set.size() != 0) {
                edgeSets.put(route, edgeTravel);
            }
        }
        
        
        
        return edgeSets;
        
        
    }
    
    public Multigraph<NetworkVertex, NetworkEdge> createPhaseTwoGraph() {
       
       // clone the revenueGraph
       SimpleGraph<NetworkVertex, NetworkEdge> graph = new SimpleGraph<NetworkVertex, NetworkEdge>(NetworkEdge.class);
       Graphs.addGraph(graph, revenueGraph);
       
       // the phase 2 graph is a multigraph due to the multiple routes between vertices
       Multigraph<NetworkVertex, NetworkEdge> graph2 = new Multigraph<NetworkVertex, NetworkEdge>(NetworkEdge.class); 

       // define the relevant vertices: stations and protected
       Set<NetworkVertex> relevantVertices = new HashSet<NetworkVertex>();
       if (protectedVertices != null) {
           // check if they are in the graph
           for (NetworkVertex vertex:protectedVertices) {
               if (graph.containsVertex(vertex)) {
                   relevantVertices.add(vertex);
               }
           }
               
       }
       
       // add station vertices
       for (NetworkVertex vertex:graph.vertexSet()) {
           if (vertex.isStation()) {
               relevantVertices.add(vertex);
           }
       }
       
       // change to sink and store them
       List<NetworkVertex> sinkVertices = new ArrayList<NetworkVertex>();
       for (NetworkVertex vertex:relevantVertices) {
           if (!vertex.isSink()) {
               vertex.setSink(true);
           } else {
              sinkVertices.add(vertex);
           }
       }
       
       // add all the relevantVertices to the phase 2 graph
       Graphs.addAllVertices(graph2, relevantVertices);
       
       // define the storage for the new edges to the old edges
       partial2route = new HashMap<NetworkEdge, Set<NetworkEdge>>();
       for (NetworkEdge edge:graph.edgeSet()) {
           partial2route.put(edge, new HashSet<NetworkEdge>());
       }
       route2partial = new HashMap<NetworkEdge, Set<NetworkEdge>>();
       
       List<NetworkVertex> relevantVertices2 = new ArrayList<NetworkVertex>(relevantVertices);
//       Collections.sort(relevantVertices2);
       
       // run the iterator for routes for each vertex
       for (NetworkVertex startVertex:relevantVertices2) {
           startVertex.setSink(false); // deactivate sink for that vertex
           // define iterator to find all routes from here
           NetworkIterator iterator = new NetworkIterator(graph, startVertex).setRouteIterator(true);
           log.info("Phase 2 Graph: Start routes from " + startVertex);
           for (;iterator.hasNext();) {
               // found new route
               NetworkVertex nextVertex = iterator.next();
               if (nextVertex.isSink() && nextVertex != startVertex) {
                   List<NetworkVertex> route = iterator.getCurrentRoute();
                   log.info("Phase 2 Graph: Route found to " + nextVertex + " with route = " + route);
                   // define routeEdge
                   NetworkEdge routeEdge = null;
                   Set<NetworkEdge> partialEdges = new HashSet<NetworkEdge>();
                   // previousVertex
                   NetworkVertex currentVertex = null;
                   // define new edge by going through the route edges
                   for (NetworkVertex routeVertex:route) {
                       if (currentVertex != null) {
                           NetworkEdge partialEdge = graph.getEdge(currentVertex, routeVertex); 
                           if (routeEdge == null) {
                               routeEdge = partialEdge;
                           } else {
                              routeEdge = NetworkEdge.mergeEdges(routeEdge, partialEdge).newEdge;
                           }
                           partialEdges.add(partialEdge);
                       }
                       currentVertex = routeVertex;
                   }
                   // define partial2route entries
                   for (NetworkEdge partialEdge:partialEdges) {
                       partial2route.get(partialEdge).add(routeEdge);
                   }
                   // store route2partial
                   route2partial.put(routeEdge, partialEdges);
                   // add new route
                   graph2.addEdge(startVertex, currentVertex, routeEdge);
               }
           }
           // remove that vertex from the graph to avoid duplication of the routes
           graph.removeVertex(startVertex);
       }

       // restore sinkVertices
       for (NetworkVertex vertex:sinkVertices) {
            vertex.setSink(true);
       }
       
       log.info("Defined graph phase 2 = " + graph2);
       
       List<NetworkEdge> edges = new ArrayList<NetworkEdge>(graph2.edgeSet());
       Collections.sort(edges);
       StringBuffer s = new StringBuffer();
       for (NetworkEdge e:edges) {
           s.append("\n" + e.getOrderedConnection());
       }
       log.info("Edges = " + s.toString());

       // store and return
       phase2Graph = graph2;
       
       return graph2;
    }
    
}

Index: RevenueCalculator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueCalculator.java,v
retrieving revision 1.17
retrieving revision 1.18
diff -C2 -d -r1.17 -r1.18
*** RevenueCalculator.java	25 May 2010 20:33:58 -0000	1.17
--- RevenueCalculator.java	17 Jun 2010 22:10:53 -0000	1.18
***************
*** 5,97 ****
  import org.apache.log4j.Logger;
  
! final class RevenueCalculator {
      
!     private final int nbVertexes;
!     private final int nbTrains;
!     private final int nbEdges;
!     private final int nbBonuses;
      
      // static vertex data
!     private final int[][] vertexValueByTrain; // dimensions: vertexId, trainId
!     private final boolean[] vertexMajor;
!     private final boolean[] vertexMinor;
!     private final boolean[] vertexSink;
!     private final int[] vertexNbNeighbors;
!     private final int[] vertexNbVisitSets;
!     private final int[] vertexNbBonusSets;
      
!     private final int[][] vertexNeighbors;
!     private final int[][] vertexEdges;
!     private final int[][] vertexVisitSets; // vertex belongs to a visit set, dimension: nbVertex x maxBlocks
!     private final int[][] vertexBonusSets; // vertex belongs to a bonus set, dimension: nbVertex x nbBonuses
  
      // start vertexes
!     private int[] startVertexes;
      
      // static edge data
!     private final boolean[] edgeGreedy;
!     private final int[] edgeDistance;
!     
!     // dynamic edge data
!     private final boolean[] edgeUsed;
      
      // static train data
!     private final int[] trainMaxMajors;
!     private final int[] trainMaxMinors;
!     private final int[] trainMaxBonuses;
!     private final boolean[] trainIgnoreMinors;
      
      // dynamic train data
!     private final int[] trainCurrentValue;
!     private final int[] trainMajors;
!     private final int[] trainMinors;
!     private final int[] trainBonuses; // counts the number of bonuses received
!     private final boolean[][] trainVisited;
!     private final int[][] trainVertexStack;
! //    private final int[][] trainEdgeStack;
!     private final int[] trainStackPos;
!     private final int [] trainBottomPos;
!     private final int [] trainStartEdge;
      
      // static bonus data
!     private final int [] bonusValue;
!     private final boolean [][] bonusActiveForTrain; // dimensions: bonus x train
!     private final int [] bonusRequiresVertices;
      
      // dynamic bonus data
!     private final int [][] bonusTrainVertices;
      
      // run settings
!     private int startTrainSet;
!     private int finalTrainSet;
!     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;
!     private int nbEdgesTravelled;
!     private int nbEvaluations;
!     private int nbPredictions;
  
      // revenue Adapter
!     private RevenueAdapter revenueAdapter;
      
      // activate dynamic revenue modifiers
!     private boolean callDynamicModifiers;
      
      // termination results
!     private static enum Terminated {
          WithEvaluation,
          WithoutEvaluation,
--- 5,93 ----
  import org.apache.log4j.Logger;
  
! abstract class RevenueCalculator {
      
!     protected final int nbVertexes;
!     protected final int nbTrains;
!     protected final int nbEdges;
!     protected final int nbBonuses;
      
      // static vertex data
!     protected final int[][] vertexValueByTrain; // dimensions: vertexId, trainId
!     protected final boolean[] vertexMajor;
!     protected final boolean[] vertexMinor;
!     protected final boolean[] vertexSink;
!     protected final int[] vertexNbNeighbors;
!     protected final int[] vertexNbVisitSets;
!     protected final int[] vertexNbBonusSets;
      
!     protected final int[][] vertexNeighbors;
!     protected final int[][] vertexEdges;
!     protected final int[][] vertexVisitSets; // vertex belongs to a visit set, dimension: nbVertex x maxVertexSets
!     protected final int[][] vertexBonusSets; // vertex belongs to a bonus set, dimension: nbVertex x nbBonuses
  
      // start vertexes
!     protected int[] startVertexes;
      
      // static edge data
!     protected final boolean[] edgeGreedy;
!     protected final int[] edgeDistance;
      
      // static train data
!     protected final int[] trainMaxMajors;
!     protected final int[] trainMaxMinors;
!     protected final int[] trainMaxBonuses;
!     protected final boolean[] trainIgnoreMinors;
      
      // dynamic train data
!     protected final int[] trainCurrentValue;
!     protected final int[] trainMajors;
!     protected final int[] trainMinors;
!     protected final int[] trainBonuses; // counts the number of bonuses received
!     protected final boolean[][] trainVisited;
!     protected final int[][] trainStack; // store either vertices or edges 
!     protected final int[] trainStackPos;
!     protected final boolean [] trainBottomActive;
!     protected final int [] trainStartEdge;
      
      // static bonus data
!     protected final int [] bonusValue;
!     protected final boolean [][] bonusActiveForTrain; // dimensions: bonus x train
!     protected final int [] bonusRequiresVertices;
      
      // dynamic bonus data
!     protected final int [][] bonusTrainVertices;
      
      // run settings
!     protected int startTrainSet;
!     protected int finalTrainSet;
!     protected int startTrain;
!     protected int finalTrain;
!     protected boolean useRevenuePrediction;
      
      // current best run results
!     protected int currentBestValue;
!     protected final int [][] currentBestRun;
      
      // prediction data
!     protected int[] maxCumulatedTrainRevenues;
!     protected int[][] maxMajorRevenues; // dimensions trainId x nb vertex; 
!     protected int[][] maxMinorRevenues; // dimensions trainId x nb vertex;
!     protected int[][] maxBonusRevenues; // dimensions trainId x nb bonuses
  
      // statistic data
!     protected int countVisits;
!     protected int countEdges;
!     protected int nbEdgesTravelled;
!     protected int nbEvaluations;
!     protected int nbPredictions;
  
      // revenue Adapter
!     protected RevenueAdapter revenueAdapter;
      
      // activate dynamic revenue modifiers
!     protected boolean callDynamicModifiers;
      
      // termination results
!     protected static enum Terminated {
          WithEvaluation,
          WithoutEvaluation,
***************
*** 105,112 ****
      
      public RevenueCalculator (RevenueAdapter revenueAdapter, int nbVertexes, int nbEdges, 
!             int maxNeighbors, int maxVertexSets, int nbTrains, int nbBonuses) {
          
          log.info("RC defined: nbVertexes = " + nbVertexes + ", nbEdges = " + nbEdges + ", maxNeighbors = " + maxNeighbors +
!                 ", maxVertexSets = " + maxVertexSets + ", nbTrains = " + nbTrains + ", nbBonuses = " + nbBonuses );
  
          this.revenueAdapter = revenueAdapter;
--- 101,108 ----
      
      public RevenueCalculator (RevenueAdapter revenueAdapter, int nbVertexes, int nbEdges, 
!             int maxNeighbors, int maxVertexSets, int maxEdgeSets, int nbTrains, int nbBonuses) {
          
          log.info("RC defined: nbVertexes = " + nbVertexes + ", nbEdges = " + nbEdges + ", maxNeighbors = " + maxNeighbors +
!                 ", maxVertexSets = " + maxVertexSets + ", maxEdgeSets = " + maxEdgeSets + ", nbTrains = " + nbTrains + ", nbBonuses = " + nbBonuses );
  
          this.revenueAdapter = revenueAdapter;
***************
*** 131,135 ****
          edgeGreedy = new boolean[nbEdges];
          edgeDistance = new int[nbEdges];
-         edgeUsed = new boolean[nbEdges];
          
          trainMaxMajors = new int[nbTrains];
--- 127,130 ----
***************
*** 143,151 ****
          trainBonuses = new int[nbTrains];
          trainVisited = new boolean[nbTrains][nbVertexes];
-         trainVertexStack = new int[nbTrains][nbVertexes + 1];
          // increase necessary due to buttom train
! //        trainEdgeStack = new int[nbTrains][nbVertexes + 1];
          trainStackPos = new int[nbTrains];
!         trainBottomPos = new int[nbTrains];
          trainStartEdge = new int[nbTrains];
          
--- 138,145 ----
          trainBonuses = new int[nbTrains];
          trainVisited = new boolean[nbTrains][nbVertexes];
          // increase necessary due to buttom train
!         trainStack = new int[nbTrains][nbVertexes + 1];
          trainStackPos = new int[nbTrains];
!         trainBottomActive = new boolean[nbTrains];
          trainStartEdge = new int[nbTrains];
          
***************
*** 162,166 ****
      }
  
!     void setVertex(int id, boolean major, boolean minor, boolean sink) {
          vertexMajor[id] = major;
          vertexMinor[id] = minor;
--- 156,160 ----
      }
  
!     final void setVertex(int id, boolean major, boolean minor, boolean sink) {
          vertexMajor[id] = major;
          vertexMinor[id] = minor;
***************
*** 172,180 ****
      }
      
!     void setVertexValue(int vertexId, int trainId, int value) {
          vertexValueByTrain[vertexId][trainId] = value;
      }
  
!     void setVertexNeighbors(int id, int[] neighbors, int[] edges) {
          // copy neighbors
          for (int j=0; j < neighbors.length; j++) {
--- 166,174 ----
      }
      
!     final void setVertexValue(int vertexId, int trainId, int value) {
          vertexValueByTrain[vertexId][trainId] = value;
      }
  
!     final void setVertexNeighbors(int id, int[] neighbors, int[] edges) {
          // copy neighbors
          for (int j=0; j < neighbors.length; j++) {
***************
*** 186,190 ****
      }
     
!     void setStartVertexes(int[] startVertexes) {
          this.startVertexes = startVertexes;
      }
--- 180,184 ----
      }
     
!     final void setStartVertexes(int[] startVertexes) {
          this.startVertexes = startVertexes;
      }
***************
*** 194,200 ****
          edgeGreedy[edgeId] = greedy;
          edgeDistance[edgeId] = distance;
      }
      
!     void setTrain(int id, int majors, int minors, boolean ignoreMinors) {
          trainMaxMajors[id] = majors;
          trainMaxMinors[id] = minors;
--- 188,196 ----
          edgeGreedy[edgeId] = greedy;
          edgeDistance[edgeId] = distance;
+         // default travel sets
+ //        edgeNbTravelSets[edgeId] = 0;
      }
      
!     final void setTrain(int id, int majors, int minors, boolean ignoreMinors) {
          trainMaxMajors[id] = majors;
          trainMaxMinors[id] = minors;
***************
*** 203,207 ****
      }
      
!     void setVisitSet(int[] vertices) {
          for (int j=0; j < vertices.length; j++) {
              int vertexId = vertices[j];
--- 199,203 ----
      }
      
!     final void setVisitSet(int[] vertices) {
          for (int j=0; j < vertices.length; j++) {
              int vertexId = vertices[j];
***************
*** 213,217 ****
      }
      
!     void setBonus(int id, int value, int[] vertices, boolean[] bonusForTrain) {
          log.info("RC: define bonus value = " + value + ", vertices = " + Arrays.toString(vertices) +
                  ", bonusForTrain = " + Arrays.toString(bonusForTrain));
--- 209,214 ----
      }
      
!     
!     final void setBonus(int id, int value, int[] vertices, boolean[] bonusForTrain) {
          log.info("RC: define bonus value = " + value + ", vertices = " + Arrays.toString(vertices) +
                  ", bonusForTrain = " + Arrays.toString(bonusForTrain));
***************
*** 226,244 ****
      }
      
!     void setDynamicModifiers(boolean activate) {
          callDynamicModifiers = activate;
      }
      
!     int[][] getOptimalRun() {
          log.info("RC: currentBestRun = " + Arrays.deepToString(currentBestRun));
          return currentBestRun;
      }
      
!     int[][] getCurrentRun() {
          int[][] currentRun = new int[nbTrains][nbVertexes+1];
          for (int j = startTrainSet; j <= finalTrainSet; j++) {
              for (int v = 0; v < nbVertexes + 1; v++) {
                  if (v < trainStackPos[j]) {
!                     currentRun[j][v] = trainVertexStack[j][v];
                  } else {
                      currentRun[j][v] = -1; // terminator
--- 223,241 ----
      }
      
!     final void setDynamicModifiers(boolean activate) {
          callDynamicModifiers = activate;
      }
      
!     final int[][] getOptimalRun() {
          log.info("RC: currentBestRun = " + Arrays.deepToString(currentBestRun));
          return currentBestRun;
      }
      
!     final int[][] getCurrentRun() {
          int[][] currentRun = new int[nbTrains][nbVertexes+1];
          for (int j = startTrainSet; j <= finalTrainSet; j++) {
              for (int v = 0; v < nbVertexes + 1; v++) {
                  if (v < trainStackPos[j]) {
!                     currentRun[j][v] = trainStack[j][v];
                  } else {
                      currentRun[j][v] = -1; // terminator
***************
*** 250,258 ****
      }
      
!     int getNumberOfEvaluations() {
          return nbEvaluations;
      }
      
!     String getStatistics() {
          StringBuffer statistics = new StringBuffer();
          statistics.append(nbEvaluations + " evaluations");
--- 247,255 ----
      }
      
!     final int getNumberOfEvaluations() {
          return nbEvaluations;
      }
      
!     final String getStatistics() {
          StringBuffer statistics = new StringBuffer();
          statistics.append(nbEvaluations + " evaluations");
***************
*** 263,267 ****
      }
      
!     private void notifyRevenueAdapter(final int revenue, final boolean finalResult) {
          String modifier;
          if (finalResult)
--- 260,264 ----
      }
      
!     final private void notifyRevenueAdapter(final int revenue, final boolean finalResult) {
          String modifier;
          if (finalResult)
***************
*** 273,277 ****
      }
  
!     private int[] bestRevenues(int[] values, int length) {
          int[] bestRevenues = new int[length + 1];
          Arrays.sort(values);
--- 270,274 ----
      }
  
!     final private int[] bestRevenues(final int[] values, final int length) {
          int[] bestRevenues = new int[length + 1];
          Arrays.sort(values);
***************
*** 285,289 ****
      }
      
!     private void initRevenueValues(int startTrain, int finalTrain){
          
        // intialize values
--- 282,286 ----
      }
      
!     final private void initRevenueValues(final int startTrain, final int finalTrain){
          
        // intialize values
***************
*** 328,332 ****
      }
      
!     void initialPredictionRuns(int startTrain, int finalTrain) {
          
          if (startTrain > finalTrain) return;
--- 325,329 ----
      }
      
!     final void initialPredictionRuns(final int startTrain, final int finalTrain) {
          
          if (startTrain > finalTrain) return;
***************
*** 381,385 ****
      }
      
!     int calculateRevenue(int startTrain, int finalTrain) {
          log.info("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
  
--- 378,382 ----
      }
      
!     final int calculateRevenue(final int startTrain, final int finalTrain) {
          log.info("RC: calculateRevenue trains from " + startTrain + " to " + finalTrain);
  
***************
*** 404,574 ****
      }
     
!     private void runTrain(int trainId) {
!         log.debug("RC: runTrain " + trainId);
!         
!         // initialize value
!         trainCurrentValue[trainId] = 0;
! 
!         // initialize train lengths
!         trainMajors[trainId] = trainMaxMajors[trainId];
!         trainMinors[trainId] = trainMaxMinors[trainId];
!         trainBonuses[trainId] = trainMaxBonuses[trainId];
!         
!         // initialize the positions
!         trainStackPos[trainId] = 0;
!         trainBottomPos[trainId] = 0;
!         
!         // initialize bonuses
!         for (int b=0; b < nbBonuses; b++) {
!             bonusTrainVertices[b][trainId] = bonusRequiresVertices[b];
!         }
!         
!         // check if the revenue is enough
!         if (useRevenuePrediction && predictRevenues(trainId))
!             return;
! 
!         // try all startVertexes
!         for (int i=0; i < startVertexes.length; i++) {
!             int vertexId = startVertexes[i];
!             log.debug("RC: Using startVertex nr. " + i + " for train " + trainId);
!             boolean stationVertex = encounterVertex(trainId, vertexId, true);
!             if (stationVertex) {
!                 // train cannot terminate at start vertex
!                 if (useRevenuePrediction && predictRevenues(trainId)) {
!                     // cannot beat current best value => leave immediately
!                     encounterVertex(trainId, vertexId, false);
!                     // but keep them on the visited vertex list to avoid route duplication
!                     trainVisited[trainId][vertexId] = true;
!                     log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
!                     continue;
!                 }
!             }
! 
!             // then try all edges of it
!             // for startVertices the sink property is ignored
!             for (int j = 0; j < vertexNbNeighbors[vertexId]; j++) {
!                 int edgeId = vertexEdges[vertexId][j];
!                 if (edgeUsed[edgeId]) continue; 
!                 log.debug("RC: Testing Neighbor Nr. " + j + " of startVertex");
!                 int neighborId = vertexNeighbors[vertexId][j];
!                 if (trainVisited[trainId][neighborId]) {
!                     log.debug("RC: Hex already visited");
!                     continue;
!                 }
!                 if (travelEdge(trainId, edgeId, true)) {
!                     trainStartEdge[trainId] = j; // store start edge
!                     nextVertex(trainId, neighborId, edgeGreedy[edgeId]);
!                     returnEdge(edgeId);
!                 }
!             }
! 
!             // no more edges to find
!             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);
!         }
! 
!         // finished all tries
!         for (int i=0; i < startVertexes.length; i++) {
!             // remove all of them from the visited vertex list
!             trainVisited[trainId][startVertexes[i]] = false;
!         }
! 
!         // allow that the train does not run at all
!         finalizeVertex(trainId, -1);
!         
!         log.debug("RC: finishTrain " + trainId);
!     }
      
!     private void runBottom(int trainId) {
!         log.debug("RC: runBottom " +trainId);
!         
!         // use startvertex, check if it is a sink
!         int vertexId = trainVertexStack[trainId][0];
!         if (vertexSink[vertexId]) {
!             log.debug("RC: startvertex is sink, finished bottom of " + trainId);
!             return;
!         }
!                 
!         // push to stack
!         trainBottomPos[trainId] = trainStackPos[trainId]; // store the stack position where bottom starts
!         trainVertexStack[trainId][trainStackPos[trainId]++] = vertexId;
!         log.debug("RC: Restart at bottom at stack position " + trainBottomPos[trainId]);
!         
!         for (int j = trainStartEdge[trainId] + 1; j < vertexNbNeighbors[vertexId]; j++) {
!             int edgeId = vertexEdges[vertexId][j]; 
!             if (edgeUsed[edgeId]) continue; 
!             int neighborId = vertexNeighbors[vertexId][j];
!             log.debug("RC: Testing Neighbor Nr. " + j + " of bottomVertex is " + neighborId);
!             if (trainVisited[trainId][neighborId]) {
!                 log.debug(" RC: Hex already visited");
!                 continue;
!             }
!             if (travelEdge(trainId, edgeId, true)) {
!                 nextVertex(trainId, neighborId, edgeGreedy[edgeId]);
!                 returnEdge(edgeId);
!             }
!         }
!         
!         trainStackPos[trainId]--; // pull from stack
!         trainBottomPos[trainId] = 0;
!         log.debug("RC: finished bottom of " + trainId);
!     }
! 
!     /**
!      * arrives at an unvisited vertex
!      */
!     private void nextVertex(int trainId, int vertexId, boolean previousGreedy) {
  
-         // 1. encounterVertex adds value and returns true if value vertex
-         Terminated trainTerminated = Terminated.NotYet; 
-         boolean stationVertex = encounterVertex(trainId, vertexId, true);
-         if (stationVertex) {
-             // check usual train termination
-             trainTerminated = trainTerminated(trainId);
-             if (trainTerminated == Terminated.WithoutEvaluation ||
-                     useRevenuePrediction && predictRevenues(trainId)) {
-                 // cannot beat current best value => leave immediately
-                 encounterVertex(trainId, vertexId, false);
- //                returnEdge(trainId);
-                 return;
-             }
-         }
-         
-         // 2a. visit neighbors, if train has not terminated and vertex is not a sink
-         if (trainTerminated == Terminated.NotYet) {
-             if (!vertexSink[vertexId]) {
-                 for (int j = 0; j < vertexNbNeighbors[vertexId]; j++) {
-                     int edgeId = vertexEdges[vertexId][j];
-                     if (edgeUsed[edgeId]) continue;
-                     int neighborId = vertexNeighbors[vertexId][j];
-                     log.debug("RC: Testing Neighbor Nr. " + j + " of " + vertexId + " is " + neighborId);
-                     if (trainVisited[trainId][neighborId]) {
-                         log.debug("RC: Hex already visited");
-                         continue;
-                     }
-                     if (travelEdge(trainId, edgeId, previousGreedy)) {
-                         nextVertex(trainId, neighborId, edgeGreedy[edgeId]);
-                         returnEdge(edgeId);
-                     }
-                 }
-             }
-             // 2b. restart at startVertex for bottom part
-             if (stationVertex && trainBottomPos[trainId] == 0){
-                 runBottom(trainId);
-             }
-         }
-         
-         // 3. no more edges to visit from here => evaluate or start new train
-         if (stationVertex)
-             finalizeVertex(trainId, vertexId);
-         
-         // 4. then leave that vertex
-         encounterVertex(trainId, vertexId, false);
- //        returnEdge(trainId);
-     }
      
!     private boolean encounterVertex(int trainId, int vertexId, boolean arrive) {
  
          log.debug("RC: EncounterVertex, trainId = " + trainId + " vertexId = " + vertexId + " arrive = " + arrive);
--- 401,414 ----
      }
     
!     abstract protected void runTrain(final int trainId);
      
!     abstract protected void runBottom(final int trainId);
  
      
!     // next vertex is either:
!     // protected void nextVertex(int trainId, int vertexId, boolean previousGreedy);
!     // protected void nextVertex(int trainId, int vertexId);
!     
!     protected final boolean encounterVertex(final int trainId, final int vertexId, final boolean arrive) {
  
          log.debug("RC: EncounterVertex, trainId = " + trainId + " vertexId = " + vertexId + " arrive = " + arrive);
***************
*** 587,591 ****
                  stationVertex = !trainIgnoreMinors[trainId];
              }
-             trainVertexStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
              countVisits++;
          } else {
--- 427,430 ----
***************
*** 598,602 ****
                  stationVertex = !trainIgnoreMinors[trainId];
              }
-             trainStackPos[trainId]--; // pull from stack
              countVisits--;
          }   
--- 437,440 ----
***************
*** 635,665 ****
          return stationVertex;
      }
-     
-     private boolean travelEdge(int trainId, int edgeId, boolean previousGreedy) {
-         if (previousGreedy || edgeGreedy[edgeId]) {
-             log.debug("RC: Travel edge id " + edgeId);
-             edgeUsed[edgeId] = true;
- //            trainEdgeStack[trainId][trainStackPos[trainId]] = edgeId;
-             countEdges++; nbEdgesTravelled++;
-             log.debug("RC: Count Edges = " + countEdges);
-             return true;
-         } else {
-             log.debug("RC: Cannot travel edge id " + edgeId + ", because of greedy rule");
-             return false;
-         }
-     }
  
!     private void returnEdge(int edgeId) {
!         if (edgeUsed[edgeId]) {
!             edgeUsed[edgeId] = false;
!             countEdges--;
!             log.debug("RC: Cleared edge id " + edgeId);
!             log.debug("RC: Count Edges = " + countEdges);
!         } else {
!             log.debug("RC: Error return edge id used: " + edgeId);
!         }
!     }
      
!     private Terminated trainTerminated(int trainId) {
          Terminated terminated = Terminated.NotYet;
          if (trainIgnoreMinors[trainId]) {
--- 473,484 ----
          return stationVertex;
      }
  
!     // travel edge is either:
! //      protected boolean travelEdge(int trainId, int edgeId, boolean previousGreedy);
! //      protected boolean travelEdge(int trainId, int edgeId);
! 
!     abstract protected void returnEdge(final int edgeId);
      
!     protected final Terminated trainTerminated(final int trainId) {
          Terminated terminated = Terminated.NotYet;
          if (trainIgnoreMinors[trainId]) {
***************
*** 680,684 ****
      }
      
!     private void finalizeVertex(int trainId, int vertexId) {
          log.debug("RC: Finalize Vertex id " + vertexId + " for train " + trainId);
          
--- 499,503 ----
      }
      
!     protected final void finalizeVertex(final int trainId, final int vertexId) {
          log.debug("RC: Finalize Vertex id " + vertexId + " for train " + trainId);
          
***************
*** 690,694 ****
      }
  
!     private void evaluateResults() {
          // sum to total value
          int totalValue = 0;
--- 509,513 ----
      }
  
!     protected final void evaluateResults() {
          // sum to total value
          int totalValue = 0;
***************
*** 717,721 ****
                  for (int v = 0; v < nbVertexes + 1; v++) {
                      if (v < trainStackPos[j]) {
!                         currentBestRun[j][v] = trainVertexStack[j][v];
                      } else {
                          currentBestRun[j][v] = -1; // terminator
--- 536,540 ----
                  for (int v = 0; v < nbVertexes + 1; v++) {
                      if (v < trainStackPos[j]) {
!                         currentBestRun[j][v] = trainStack[j][v];
                      } else {
                          currentBestRun[j][v] = -1; // terminator
***************
*** 731,735 ****
      
      // 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;
--- 550,554 ----
      
      // predict revenues and returns true if best value can still be exceeded
!     protected final boolean predictRevenues(final int trainId){
          // the potential revenues of the future trains
          int totalValue = 0;
***************
*** 799,802 ****
--- 618,623 ----
          buffer.append("edgeGreedy:" + Arrays.toString(edgeGreedy) + "\n");
          buffer.append("edgeDistance:" + Arrays.toString(edgeDistance) + "\n");
+ //        buffer.append("edgeTravelSets:" + Arrays.deepToString(edgeTravelSets) + "\n");
+ //        buffer.append("egdeNbTravelSets:" + Arrays.toString(edgeNbTravelSets) + "\n");
          buffer.append("startVertexes:" + Arrays.toString(startVertexes) + "\n"); 
          buffer.append("trainMaxMajors:" + Arrays.toString(trainMaxMajors) + "\n"); 

Index: NetworkIterator.java
===================================================================
RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkIterator.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** NetworkIterator.java	11 May 2010 21:47:21 -0000	1.6
--- NetworkIterator.java	17 Jun 2010 22:10:53 -0000	1.7
***************
*** 23,30 ****
--- 23,36 ----
      }
      
+     // settings
      private NetworkVertex startVertex;
+     private boolean startVertexVisited;
+     private boolean routeIterator;
+ 
+     // internal data
      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 Graph<NetworkVertex, NetworkEdge> graph;
***************
*** 54,59 ****
--- 60,71 ----
          this.graph = graph;
          this.startVertex = startVertex;
+         this.startVertexVisited = false;
+         this.routeIterator = false;
      }
      
+     NetworkIterator setRouteIterator(boolean routeIterator) {
+         this.routeIterator = routeIterator;
+         return this;
+     }
      
      /**
***************
*** 64,72 ****
          return graph;
      }
      /**
       * @see java.util.Iterator#hasNext()
       */
      public boolean hasNext() {
!         if (startVertex != null) {
              encounterStartVertex();
          }
--- 76,98 ----
          return graph;
      }
+ 
+     public List<NetworkVertex> getCurrentRoute() {
+         // extract all networkvertices just before a null
+         List<NetworkVertex> route = new ArrayList<NetworkVertex>();
+         NetworkVertex previousVertex = null;
+         for (NetworkVertex vertex:stack) {
+             if (previousVertex != null && vertex == null) {
+                 route.add(previousVertex);
+             }
+             previousVertex = vertex;
+         }
+         return route;
+     }
+     
      /**
       * @see java.util.Iterator#hasNext()
       */
      public boolean hasNext() {
!         if (!startVertexVisited) {
              encounterStartVertex();
          }
***************
*** 87,91 ****
      public NetworkVertex next()
      {
!         if (startVertex != null) {
              encounterStartVertex();
          }
--- 113,117 ----
      public NetworkVertex next()
      {
!         if (!startVertexVisited) {
              encounterStartVertex();
          }
***************
*** 150,157 ****
--- 176,186 ----
  
          if (vertex.isSink()) return;
+         log.debug("Iterator: Add unseen children of " + vertex);
  
          for (NetworkEdge edge : graph.edgesOf(vertex)) {
+             log.debug("Iterator: Check edge for neighbor in edge " + edge.toFullInfoString());
              if (!greedy || edge.isGreedy()) {
                  NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
+                 log.debug("Iterator: Neighbor is " + oppositeV);
                  encounterVertex(oppositeV, edge);
              }
***************
*** 160,179 ****
      
      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());
--- 189,222 ----
      
      private void encounterStartVertex() {
!         putSeenData(startVertex, false);
          stack.add(startVertex);
          greedyStack.add(false);
          log.debug("Iterator: Added to stack " + startVertex +  " with greedy set to false");
!         startVertexVisited = true;
      }
  
  
      private void encounterVertex(NetworkVertex v, NetworkEdge e){
! 
!         if (routeIterator) {
! //            if (v == startVertex) return;
!             // check the stack
!             if (getCurrentRoute().contains(v))
!                 return;
!             // check the seen components 
! //            if (seen.containsKey(v) && (seen.get(v) == greedyState.seen && !v.isSink() 
! //                    || seen.get(v) == greedyState.done || (e.isGreedy() && seen.get(v) == greedyState.nonGreedy)
! //                    || (!e.isGreedy() && seen.get(v) == greedyState.greedy) )) {
! //                log.debug("Do not add vertex " + v  + " to stack");
! //                return;
! //            }
!         } else {
!             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());
***************
*** 181,185 ****
      }
  
- 
- 
  }
--- 224,226 ----

--- NEW FILE: RevenueCalculatorSimple.java ---
package rails.algorithms;

final class RevenueCalculatorSimple extends RevenueCalculator {

    // dynamic edge data
    private final boolean[] edgeUsed;
  
    public RevenueCalculatorSimple (RevenueAdapter revenueAdapter, int nbVertexes, int nbEdges, 
            int maxNeighbors, int maxVertexSets, int nbTrains, int nbBonuses) {
    
        // maxEdgeSet set to zero
        super(revenueAdapter, nbVertexes, nbEdges, 
                maxNeighbors, maxVertexSets, 0, nbTrains, nbBonuses);

        // edge used is boolean here
        edgeUsed = new boolean[nbEdges];

    }
    
   @Override
   protected final void runTrain(final int trainId) {
        log.debug("RC: runTrain " + trainId);
        
        // initialize value
        trainCurrentValue[trainId] = 0;

        // initialize train lengths
        trainMajors[trainId] = trainMaxMajors[trainId];
        trainMinors[trainId] = trainMaxMinors[trainId];
        trainBonuses[trainId] = trainMaxBonuses[trainId];
        
        // initialize the positions
        trainStackPos[trainId] = 0;
        trainBottomActive[trainId] = false;
        
        // initialize bonuses
        for (int b=0; b < nbBonuses; b++) {
            bonusTrainVertices[b][trainId] = bonusRequiresVertices[b];
        }
        
        // check if the revenue is enough
        if (useRevenuePrediction && predictRevenues(trainId))
            return;

        // try all startVertexes
        for (int i=0; i < startVertexes.length; i++) {
            int vertexId = startVertexes[i];
            log.debug("RC: Using startVertex nr. " + i + " for train " + trainId);
            boolean stationVertex = encounterVertex(trainId, vertexId, true);
            trainStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
            if (stationVertex) {
                // train cannot terminate at start vertex
                if (useRevenuePrediction && predictRevenues(trainId)) {
                    // cannot beat current best value => leave immediately
                    encounterVertex(trainId, vertexId, false);
                    trainStackPos[trainId]--; // pull from stack
                    // but keep them on the visited vertex list to avoid route duplication
                    trainVisited[trainId][vertexId] = true;
                    log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
                    continue;
                }
            }

            // then try all edges of it
            // for startVertices the sink property is ignored
            for (int j = 0; j < vertexNbNeighbors[vertexId]; j++) {
                int edgeId = vertexEdges[vertexId][j];
                if (edgeUsed[edgeId]) continue; 
                log.debug("RC: Testing Neighbor Nr. " + j + " of startVertex");
                int neighborId = vertexNeighbors[vertexId][j];
                if (trainVisited[trainId][neighborId]) {
                    log.debug("RC: Hex already visited");
                    continue;
                }
                if (travelEdge(trainId, edgeId, true)) {
                    trainStartEdge[trainId] = j; // store start edge
                    nextVertex(trainId, neighborId, edgeGreedy[edgeId]);
                    returnEdge(edgeId);
                }
            }

            // no more edges to find
            encounterVertex(trainId, vertexId, false);
            trainStackPos[trainId]--; // pull from stack
            // keep them on the visited vertex list to avoid route duplication
            trainVisited[trainId][vertexId] = true;
            log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
        }

        // finished all tries
        for (int i=0; i < startVertexes.length; i++) {
            // remove all of them from the visited vertex list
            trainVisited[trainId][startVertexes[i]] = false;
        }

        // allow that the train does not run at all
        finalizeVertex(trainId, -1);
        
        log.debug("RC: finishTrain " + trainId);
    }

   @Override
   protected final void runBottom(final int trainId) {
       log.debug("RC: runBottom " +trainId);
       
       // use startvertex, check if it is a sink
       int vertexId = trainStack[trainId][0];
       if (vertexSink[vertexId]) {
           log.debug("RC: startvertex is sink, finished bottom of " + trainId);
           return;
       }
               
       trainBottomActive[trainId] = true;
       // push to stack
       log.debug("RC: Restart at bottom at stack position " + trainStackPos[trainId]);
       trainStack[trainId][trainStackPos[trainId]++] = vertexId;
       
       for (int j = trainStartEdge[trainId] + 1; j < vertexNbNeighbors[vertexId]; j++) {
           int edgeId = vertexEdges[vertexId][j]; 
           if (edgeUsed[edgeId]) continue; 
           int neighborId = vertexNeighbors[vertexId][j];
           log.debug("RC: Testing Neighbor Nr. " + j + " of bottomVertex is " + neighborId);
           if (trainVisited[trainId][neighborId]) {
               log.debug(" RC: Hex already visited");
               continue;
           }
           if (travelEdge(trainId, edgeId, true)) {
               nextVertex(trainId, neighborId, edgeGreedy[edgeId]);
               returnEdge(edgeId);
           }
       }
       
       trainStackPos[trainId]--; // pull from stack
       trainBottomActive[trainId] = false;
       log.debug("RC: finished bottom of " + trainId);

   }
   
   final private void nextVertex(final int trainId, final int vertexId, final boolean previousGreedy) {

       // 1. encounterVertex adds value and returns true if value vertex
       Terminated trainTerminated = Terminated.NotYet; 
       boolean stationVertex = encounterVertex(trainId, vertexId, true);
       trainStack[trainId][trainStackPos[trainId]++] = vertexId; // push to stack
       if (stationVertex) {
           // check usual train termination
           trainTerminated = trainTerminated(trainId);
           if (trainTerminated == Terminated.WithoutEvaluation ||
                   useRevenuePrediction && predictRevenues(trainId)) {
               // cannot beat current best value => leave immediately
               encounterVertex(trainId, vertexId, false);
               trainStackPos[trainId]--; // pull from stack
               return;
           }
       }
       
       // 2a. visit neighbors, if train has not terminated and vertex is not a sink
       if (trainTerminated == Terminated.NotYet) {
           if (!vertexSink[vertexId]) {
               for (int j = 0; j < vertexNbNeighbors[vertexId]; j++) {
                   int edgeId = vertexEdges[vertexId][j];
                   if (edgeUsed[edgeId]) continue;
                   int neighborId = vertexNeighbors[vertexId][j];
                   log.debug("RC: Testing Neighbor Nr. " + j + " of " + vertexId + " is " + neighborId);
                   if (trainVisited[trainId][neighborId]) {
                       log.debug("RC: Hex already visited");
                       continue;
                   }
                   if (travelEdge(trainId, edgeId, previousGreedy)) {
                       nextVertex(trainId, neighborId, edgeGreedy[edgeId]);
                       returnEdge(edgeId);
                   }
               }
           }
           // 2b. restart at startVertex for bottom part
           if (stationVertex && !trainBottomActive[trainId]){
               runBottom(trainId);
           }
       }
       
       // 3. no more edges to visit from here => evaluate or start new train
       if (stationVertex)
           finalizeVertex(trainId, vertexId);
       
       // 4. then leave that vertex
       encounterVertex(trainId, vertexId, false);
       trainStackPos[trainId]--; // pull from stack
   }
 
   protected final boolean travelEdge(final int trainId, final int edgeId, final boolean previousGreedy) {
       if (previousGreedy || edgeGreedy[edgeId]) {
           log.debug("RC: Travel edge id " + edgeId);
           edgeUsed[edgeId] = true;
//           edgeUsed[edgeId]++;
           // trainEdgeStack[trainId][trainStackPos[trainId]] = edgeId;
           countEdges++; nbEdgesTravelled++;
           log.debug("RC: Count Edges = " + countEdges);

           // check edge sets
//           for (int j=0; j < edgeNbTravelSets[edgeId]; j++) {
//               edgeUsed[edgeTravelSets[edgeId][j]]++;
//               log.debug("RC: travelled edge " + edgeTravelSets[edgeId][j]  + " due to edge set.");
//           }
           
           return true;
       } else {
           log.debug("RC: Cannot travel edge id " + edgeId + ", because of greedy rule");
           return false;
       }
   }
   
   @Override
   protected final void returnEdge(final int edgeId) {
       if (edgeUsed[edgeId]) {
           edgeUsed[edgeId] = false;
           countEdges--;
           log.debug("RC: Cleared edge id " + edgeId);
           log.debug("RC: Count Edges = " + countEdges);
       } else {
           log.debug("RC: Error return edge id used: " + edgeId);
       }
   }
    
}

--- NEW FILE: RevenueCalculatorMulti.java ---
package rails.algorithms;

import rails.algorithms.RevenueCalculator.Terminated;

final class RevenueCalculatorMulti extends RevenueCalculator {

    protected final int[] edgeNbTravelSets;
    protected final int[][] edgeTravelSets; // edge belongs to a travel set, dimension: nbEdges x nbTravelSets

    // dynamic edge data
    private final int[] edgeUsed;
    
    // dynamic train data
    private final int[] startVertexActive;
    
      
    public RevenueCalculatorMulti (RevenueAdapter revenueAdapter, int nbVertexes, int nbEdges, 
            int maxNeighbors, int maxVertexSets, int maxEdgeSets, int nbTrains, int nbBonuses) {
    
        // maxEdgeSet set to zero
        super(revenueAdapter, nbVertexes, nbEdges, 
                maxNeighbors, maxVertexSets, maxEdgeSets, nbTrains, nbBonuses);

        edgeNbTravelSets = new int[nbEdges];
        edgeTravelSets = new int[nbEdges][maxEdgeSets];
        
        // edge used is integer here
        edgeUsed = new int[nbEdges];
        
        startVertexActive = new int[nbTrains];

    }
    
    @Override
    void setEdge(int edgeId, boolean greedy, int distance) {
        super.setEdge(edgeId, greedy, distance);
        // default number for travel sets
        edgeNbTravelSets[edgeId] = 0;
    }
    
    // define edgeTravelSets
    void setTravelSet(int edgeId, int[] edges) {
        for (int j=0; j < edges.length; j++) {
            edgeTravelSets[edgeId][edgeNbTravelSets[edgeId]++] = edges[j];
        }
    }
    
    @Override
    protected final void runTrain(final int trainId) {
        log.debug("RC: runTrain " + trainId);
        
        // initialize value
        trainCurrentValue[trainId] = 0;

        // initialize train lengths
        trainMajors[trainId] = trainMaxMajors[trainId];
        trainMinors[trainId] = trainMaxMinors[trainId];
        trainBonuses[trainId] = trainMaxBonuses[trainId];
        
        // initialize the positions
        trainStackPos[trainId] = 0;
        trainBottomActive[trainId] = false;
        
        // initialize bonuses
        for (int b=0; b < nbBonuses; b++) {
            bonusTrainVertices[b][trainId] = bonusRequiresVertices[b];
        }
        
        // check if the revenue is enough
        if (useRevenuePrediction && predictRevenues(trainId))
            return;

        // try all startVertexes
        for (int i=0; i < startVertexes.length; i++) {
            int vertexId = startVertexes[i];
            log.debug("RC: Using startVertex nr. " + i + " for train " + trainId);
            boolean stationVertex = encounterVertex(trainId, vertexId, true);
            if (stationVertex) {
                // train cannot terminate at start vertex
                if (useRevenuePrediction && predictRevenues(trainId)) {
                    // cannot beat current best value => leave immediately
                    encounterVertex(trainId, vertexId, false);
                    // but keep them on the visited vertex list to avoid route duplication
                    trainVisited[trainId][vertexId] = true;
                    log.debug("RC: finished startVertex " + vertexId + " for train " +trainId);
                    continue;
                }
            }

            // then try all edges of it
            startVertexActive[trainId] = vertexId;
            // for startVertices the sink property is ignored
            for (int j = 0; j < vertexNbNeighbors[vertexId]; j++) {
                int edgeId = vertexEdges[vertexId][j];
                if (edgeUsed[edgeId] != 0) continue; 
                log.debug("RC: Testing Neighbor Nr. " + j + " of startVertex");
                int neighborId = vertexNeighbors[vertexId][j];
                if (trainVisited[trainId][neighborId]) {
                    log.debug("RC: Hex already visited");
                    continue;
                }
                travelEdge(trainId, edgeId);
                trainStartEdge[trainId] = j; // store start edge
                nextVertex(trainId, neighborId);
                returnEdge(edgeId);
                trainStackPos[trainId]--; // pull from stack
            }

            // no more edges to find
            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);
        }

        // finished all tries
        for (int i=0; i < startVertexes.length; i++) {
            // remove all of them from the visited vertex list
            trainVisited[trainId][startVertexes[i]] = false;
        }

        // allow that the train does not run at all
        finalizeVertex(trainId, -1);
        
        log.debug("RC: finishTrain " + trainId);

    }

    @Override
    final protected void runBottom(final int trainId) {
        log.debug("RC: runBottom " + trainId);
        
        // use startvertex, check if it is a sink
        int vertexId = startVertexActive[trainId];
        if (vertexSink[vertexId]) {
        ...
 
[truncated message content]