Menu
▾
▴
[Rails-commits] 18xx/rails/algorithms RevenueCalculator.java, 1.8, 1.9 RevenueAdapter.java, 1.8, 1.9 NetworkEdge.java, 1.5, 1.6 NetworkGraphBuilder.java, 1.7, 1.8
|
From: Stefan F. <ste...@us...> - 2010-05-01 16:07:13
|
Update of /cvsroot/rails/18xx/rails/algorithms In directory sfp-cvsdas-4.v30.ch3.sourceforge.com:/tmp/cvs-serv23419/rails/algorithms Modified Files: RevenueCalculator.java RevenueAdapter.java NetworkEdge.java NetworkGraphBuilder.java Log Message: Improved display of run paths (hidden vertices are shown) Index: RevenueCalculator.java =================================================================== RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueCalculator.java,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** RevenueCalculator.java 27 Apr 2010 23:24:50 -0000 1.8 --- RevenueCalculator.java 1 May 2010 16:07:05 -0000 1.9 *************** *** 315,319 **** // no more edges to find ! finalizeVertex(trainId, vertexId, valueStation); encounterVertex(trainId, vertexId, false); // keep them on the visited vertex list to avoid route duplication --- 315,319 ---- // no more edges to find ! finalizeVertex(trainId, vertexId); encounterVertex(trainId, vertexId, false); // keep them on the visited vertex list to avoid route duplication *************** *** 402,406 **** // 3. no more edges to visit from here => evaluate or start new train ! finalizeVertex(trainId, vertexId, valueStation); // 4. then leave that vertex --- 402,407 ---- // 3. no more edges to visit from here => evaluate or start new train ! if (valueStation) ! finalizeVertex(trainId, vertexId); // 4. then leave that vertex *************** *** 512,520 **** } ! private void finalizeVertex(int trainId, int vertexId, boolean evaluate) { log.debug("RC: No more edges found at " + vertexId + " for train " + trainId); if (trainId == finalTrain) { ! if (evaluate) evaluateResults(); } else { runTrain(trainId + 1); --- 513,521 ---- } ! private void finalizeVertex(int trainId, int vertexId) { log.debug("RC: No more edges found at " + vertexId + " for train " + trainId); if (trainId == finalTrain) { ! evaluateResults(); } else { runTrain(trainId + 1); Index: NetworkEdge.java =================================================================== RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkEdge.java,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** NetworkEdge.java 27 Apr 2010 23:24:50 -0000 1.5 --- NetworkEdge.java 1 May 2010 16:07:05 -0000 1.6 *************** *** 5,13 **** --- 5,20 ---- import java.awt.geom.Point2D; import java.util.ArrayList; + import java.util.Collections; import java.util.List; + import org.apache.log4j.Logger; + import org.jgrapht.Graph; + import rails.ui.swing.hexmap.HexMap; public final class NetworkEdge { + + protected static Logger log = + Logger.getLogger(NetworkEdge.class.getPackage().getName()); private final NetworkVertex source; *************** *** 66,71 **** } public String getConnection() { ! return source + " - >" + target; } --- 73,87 ---- } + public String toFullInfoString() { + StringBuffer info = new StringBuffer(); + info.append("Edge " + getConnection()); + info.append(", greedy = " + greedy); + info.append(", distance = " + distance); + info.append(", hidden vertexes = " + hiddenVertexes); + return info.toString(); + } + public String getConnection() { ! return source + " -> " + target; } *************** *** 79,82 **** --- 95,166 ---- } + public static boolean mergeEdges(Graph<NetworkVertex, NetworkEdge> graph, + NetworkEdge edgeA, NetworkEdge edgeB) { + + log.info("Merge of edge " + edgeA.toFullInfoString() + " and edge " + edgeB.toFullInfoString()); + + NetworkVertex sourceA = edgeA.getSource(); + NetworkVertex targetA = edgeA.getTarget(); + NetworkVertex sourceB = edgeB.getSource(); + NetworkVertex targetB = edgeB.getTarget(); + + NetworkVertex newSource, newTarget, vertex = null; + + boolean reverseA = false, reverseB = false; + if (sourceA == sourceB) { + newSource = targetA; + newTarget = targetB; + vertex = sourceA; + reverseA = true; + } else if (sourceA == targetB) { + newSource = targetA; + newTarget = sourceB; + vertex = sourceA; + reverseA = true; + reverseB = true; + } else if (targetA == sourceB) { + newSource = sourceA; + newTarget = targetB; + vertex = targetA; + } else if (targetA == targetB) { + newSource = sourceA; + newTarget = sourceB; + vertex = targetA; + reverseB = true; + } else { + return false; + } + + log.info("Merge newSource = " + newSource + " newTarget = " + newTarget + " remove vertex = " + vertex); + + // check if graph contains the edge already + if (graph.containsEdge(newSource, newTarget)) return false; + + // define new edge + int distance = edgeA.getDistance() + edgeB.getDistance(); + + // create new hiddenVertexes + List<NetworkVertex> hiddenVertexes = new ArrayList<NetworkVertex>(); + List<NetworkVertex> hiddenA = edgeA.getHiddenVertexes(); + if (reverseA) + Collections.reverse(hiddenA); + List<NetworkVertex> hiddenB = edgeB.getHiddenVertexes(); + if (reverseB) + Collections.reverse(hiddenB); + hiddenVertexes.addAll(hiddenA); + hiddenVertexes.add(vertex); + hiddenVertexes.addAll(hiddenB); + NetworkEdge newEdge = + new NetworkEdge(newSource, newTarget, true, distance, hiddenVertexes); + graph.addEdge(newSource, newTarget, newEdge); + + log.info("New edge = " + newEdge.toFullInfoString()); + + // remove vertex + graph.removeVertex(vertex); + + return true; + } + public static Shape getEdgeShape(HexMap map, NetworkEdge edge){ Point2D source = NetworkVertex.getVertexPoint2D(map, edge.getSource()); Index: RevenueAdapter.java =================================================================== RCS file: /cvsroot/rails/18xx/rails/algorithms/RevenueAdapter.java,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** RevenueAdapter.java 29 Apr 2010 19:47:32 -0000 1.8 --- RevenueAdapter.java 1 May 2010 16:07:05 -0000 1.9 *************** *** 12,15 **** --- 12,16 ---- + import org.apache.log4j.Logger; import org.jgrapht.Graphs; import org.jgrapht.graph.SimpleGraph; *************** *** 24,27 **** --- 25,31 ---- public class RevenueAdapter implements Runnable { + protected static Logger log = + Logger.getLogger(RevenueAdapter.class.getPackage().getName()); + private SimpleGraph<NetworkVertex, NetworkEdge> graph; *************** *** 322,325 **** --- 326,330 ---- NetworkVertex previousVertex = null; for (NetworkVertex vertex:run.get(train)) { + log.debug("RA: Next vertex " + vertex); Point2D vertexPoint = NetworkVertex.getVertexPoint2D(map, vertex); if (startVertex == null) { *************** *** 334,348 **** } // draw hidden vertexes ! // NetworkEdge edge = graph.getEdge(previousVertex, vertex); ! // if (edge != null) { ! // List<NetworkVertex> hiddenVertexes = edge.getHiddenVertexes(); ! //// if (edge.getTarget() == vertex) Collections.reverse(hiddenVertexes); ! // for (NetworkVertex v:hiddenVertexes) { ! // Point2D vPoint = NetworkVertex.getVertexPoint2D(map, v); ! // if (vPoint != null) { ! // path.lineTo((float)vPoint.getX(), (float)vPoint.getY()); ! // } ! // } ! // } if (vertexPoint != null) { path.lineTo((float)vertexPoint.getX(), (float)vertexPoint.getY()); --- 339,364 ---- } // draw hidden vertexes ! NetworkEdge edge = graph.getEdge(previousVertex, vertex); ! if (edge != null) { ! log.debug("RA: draw edge "+ edge.toFullInfoString()); ! List<NetworkVertex> hiddenVertexes = edge.getHiddenVertexes(); ! if (edge.getSource() == vertex) { ! log.debug("RA: reverse hiddenVertexes"); ! for (int i = hiddenVertexes.size() - 1; i >= 0; i--) { ! NetworkVertex v = hiddenVertexes.get(i); ! Point2D vPoint = NetworkVertex.getVertexPoint2D(map, v); ! if (vPoint != null) { ! path.lineTo((float)vPoint.getX(), (float)vPoint.getY()); ! } ! } ! } else { ! for (NetworkVertex v:hiddenVertexes) { ! Point2D vPoint = NetworkVertex.getVertexPoint2D(map, v); ! if (vPoint != null) { ! path.lineTo((float)vPoint.getX(), (float)vPoint.getY()); ! } ! } ! } ! } if (vertexPoint != null) { path.lineTo((float)vertexPoint.getX(), (float)vertexPoint.getY()); Index: NetworkGraphBuilder.java =================================================================== RCS file: /cvsroot/rails/18xx/rails/algorithms/NetworkGraphBuilder.java,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** NetworkGraphBuilder.java 27 Apr 2010 23:24:50 -0000 1.7 --- NetworkGraphBuilder.java 1 May 2010 16:07:05 -0000 1.8 *************** *** 292,312 **** } // 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(); ! List<NetworkVertex> hiddenVertexes = new ArrayList<NetworkVertex>(); ! hiddenVertexes.addAll(edges[0].getHiddenVertexes()); ! hiddenVertexes.add(vertex); ! hiddenVertexes.addAll(edges[1].getHiddenVertexes()); ! NetworkEdge newEdge = ! new NetworkEdge(firstVertex, secondVertex, true, distance, hiddenVertexes); ! graph.addEdge(firstVertex, secondVertex, newEdge); ! log.info("NGB: Merged Edges removed Vertex = " + vertex); ! log.info("NGB: New Edge = " + newEdge.getConnection() + " with hidden Vertexes " + newEdge.getHiddenVertexes()); ! // remove vertex ! graph.removeVertex(vertex); ! removed = true; break; } --- 292,298 ---- } // greedy case: // merge greed edges if the vertexes are not already connected ! if (edges[0].isGreedy()) { ! removed = NetworkEdge.mergeEdges(graph, edges[0], edges[1]); break; } |
