rails-commits

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

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

Added Files:
	NetworkEdge.java NetworkVertex.java NetworkGraphBuilder.java 
	NetworkIterator.java 
Log Message:
Adding the experimental network code. Example graphs are shown under Info on the Map Panel.

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

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import rails.game.BaseToken;
import rails.game.City;
import rails.game.MapHex;
import rails.game.PublicCompanyI;
import rails.game.Station;
import rails.game.TokenI;

public final class NetworkVertex implements Comparable<NetworkVertex> {

    private static enum VertexType {
        STATION,
        SIDE,
        HQ
    }
    
    private final VertexType type;
    
    private final MapHex hex;
    
    private final Station station;
    private final int side;
    
    private boolean tokenable;
    private Set<PublicCompanyI> companiesHaveToken;
    private int tokenSlots;

    public NetworkVertex(MapHex hex, Station station) {
        this.type = VertexType.STATION;
        this.hex = hex;
        this.station = station;
        this.side = 0;
        
        if (station.getBaseSlots() == 0){
            this.tokenable = false;
        } else {
            this.tokenable = true;
            // find tokens
            List<TokenI> tokens = null;
            this.tokenSlots = 0;
            List<City> cities = hex.getCities();
            for (City city:cities) {
                if (station == city.getRelatedStation()) {
                    tokens = city.getTokens();
                    this.tokenSlots = city.getSlots();
                    break;
                }
            }
            if (tokens == null)
                this.companiesHaveToken = null;
            else {
                this.companiesHaveToken = new HashSet<PublicCompanyI>();
                for (TokenI token:tokens) {
                    if (token instanceof BaseToken) {
                        BaseToken baseToken = (BaseToken)token;
                        this.companiesHaveToken.add(baseToken.getCompany());
                    }
                }
            }
        }
    }
    
    public NetworkVertex(MapHex hex, int side) {
        this.type = VertexType.SIDE;
        this.hex = hex;
        this.station = null;
        this.side = (side % 6);
        this.tokenable = false;
        this.companiesHaveToken = null;
        this.tokenSlots = 0;
    }
    
    public NetworkVertex(PublicCompanyI company) {
        this.type = VertexType.HQ;
        this.hex = null;
        this.station = null;
        this.side = 0;
        this.tokenable = false;
        this.companiesHaveToken = null;
        this.tokenSlots = 0;
    }
    
    public boolean isStation(){
        return type == VertexType.STATION;
    }
    
    public boolean isSide(){
        return type == VertexType.SIDE;
    }
    
    public boolean isHQ(){
        return type == VertexType.HQ;
    }

    public MapHex getHex(){
        return hex;
    }
    
    public Station getStation(){
        return station;
    }
    
    public int getSide(){
        return side;
    }
    
    public boolean isFullyTokened(){
        return tokenable && companiesHaveToken.size() == tokenSlots;
    }

    public boolean hasCompanyToken(PublicCompanyI company) {
        return !(company == null) && companiesHaveToken.contains(company);
    }
    
    public String printTokens(){
        if (!tokenable) return "Not tokenable";
        
        StringBuffer result = new StringBuffer("Tokens:");
        for (PublicCompanyI company:companiesHaveToken)
            result.append(" " + company.getName());
        if (isFullyTokened()) result.append(", fully tokened"); 
        return result.toString();
    }
    
    public String getIdentifier(){
        if (isStation())
            return hex.getName() + "." + -station.getNumber();
        else if (isSide())
            return hex.getName() + "." + side; 
        else
            return "HQ";
    }
    
    @Override
    public String toString(){
        StringBuffer message = new StringBuffer();
        if (isStation()) 
            message.append( hex.getName() + "." + station.getNumber());
        else if (isSide())
            message.append(hex.getName() + "." + hex.getOrientationName(side));
        else 
            message.append("HQ");
        if (isFullyTokened())
            message.append("/*");
        return message.toString();
    }
    
    public int compareTo(NetworkVertex otherVertex) {
        return this.getIdentifier().compareTo(otherVertex.getIdentifier());
    }
    
}

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

public final class NetworkEdge {
    
    private final NetworkVertex source;

    private final NetworkVertex target;
    
    private final boolean autoEdge;
    
    public NetworkEdge(NetworkVertex source, NetworkVertex target, boolean autoEdge) {
        this.source = source;
        this.target = target;
        this.autoEdge = autoEdge;
    }
    
    public NetworkVertex getSource() {
        return source;
    }
    
    public NetworkVertex getTarget() {
        return target;
    }

    public boolean isAutoEdge() {
        return autoEdge;
    }
  
    public String getConnection() {
      return source + " - >" + target;
    }
    
    @Override
    // set to "" to faciltate visual graph
    public String toString() {
        if (!autoEdge)
            return "***";
        else
          return "";
    }
}

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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

import org.apache.log4j.Logger;
import org.jgrapht.*;
import org.jgrapht.traverse.*;

import rails.game.PublicCompanyI;

public class NetworkIterator extends 
    AbstractGraphIterator<NetworkVertex, NetworkEdge> {

    /**
     * Standard vertex visit state enumeration.
     * Copied from CrossComponentIterator due to visibility for generic definition above
     */
    protected static enum VisitColor
    {
        /**
         * Vertex has not been returned via iterator yet.
         */
        WHITE,

        /**
         * Vertex has not been returned via iterator yet, but has to use autoedge
         */
        YELLOW,

        /**
         * Vertex has been returned via iterator, but we're
         * not done with all of its out-edges yet.
         */
        GRAY,
        
        /**
         * Vertex has been returned via iterator, and we're
         * done with all of its out-edges.
         */
        BLACK
    }

    /**
     * Stores the vertices that have been seen during iteration and
     * some additional traversal info regarding each vertex.
     */
    private Map<NetworkVertex, VisitColor> seen = new HashMap<NetworkVertex, VisitColor>();
    private NetworkVertex startVertex;

    private final PublicCompanyI company;
    private final Graph<NetworkVertex, NetworkEdge> graph;
    
    /** LIFO stack for DFS */
    private List<NetworkVertex> stack = new ArrayList<NetworkVertex>();

    protected static Logger log =
        Logger.getLogger(NetworkIterator.class.getPackage().getName());

    
    public NetworkIterator(Graph<NetworkVertex, NetworkEdge> graph,
            NetworkVertex startVertex) {
        this(graph, startVertex, null);
    }

    /**
     * Returns NetworkIterator for specific company
     */
    public NetworkIterator(Graph<NetworkVertex, NetworkEdge> graph, NetworkVertex startVertex,
            PublicCompanyI company) {
        super();
        
        if (graph == null)
            throw new IllegalArgumentException("graph must not be null");
        
        if (!graph.containsVertex(startVertex))
            throw new IllegalArgumentException("graph must contain the start vertex");

        this.graph = graph;
        this.startVertex = startVertex;
        this.company = company;
    }
    
    
    /**
     * @return the graph being traversed
     */
    public Graph<NetworkVertex, NetworkEdge> getGraph()
    {
        return graph;
    }
    /**
     * @see java.util.Iterator#hasNext()
     */
    public boolean hasNext() {
        if (startVertex != null) {
            encounterStartVertex();
        }
        
        return !isConnectedComponentExhausted();
    }

    /**
     * @see java.util.Iterator#next()
     */
    public NetworkVertex next()
    {
        if (startVertex != null) {
            encounterStartVertex();
        }

        if (hasNext()) {

            NetworkVertex nextVertex = provideNextVertex();

            VisitColor previousColor = putSeenData(nextVertex , VisitColor.GRAY);
            
            addUnseenChildrenOf(nextVertex, previousColor);

            return nextVertex;
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * Access the data stored for a seen vertex.
     *
     * @param vertex a vertex which has already been seen.
     *
     * @return data associated with the seen vertex or <code>null</code> if no
     * data was associated with the vertex. A <code>null</code> return can also
     * indicate that the vertex was explicitly associated with <code>
     * null</code>.
     */
    private VisitColor getSeenData(NetworkVertex vertex) {
        return seen.get(vertex);
    }

    /**
     * Determines whether a vertex has been seen yet by this traversal.
     *
     * @param vertex vertex in question
     *
     * @return <tt>true</tt> if vertex has already been seen
     */
    private boolean isSeenVertex(NetworkVertex vertex)
    {
        return seen.containsKey(vertex);
    }
    
    /**
     * Stores iterator-dependent data for a vertex that has been seen.
     *
     * @param vertex a vertex which has been seen.
     * @param data data to be associated with the seen vertex.
     *
     * @return previous value associated with specified vertex or <code>
     * null</code> if no data was associated with the vertex. A <code>
     * null</code> return can also indicate that the vertex was explicitly
     * associated with <code>null</code>.
     */
    private VisitColor putSeenData(NetworkVertex vertex, VisitColor data)
    {
        return seen.put(vertex, data);
    }
    
    /**
     * Called when a vertex has been finished (meaning is dependent on traversal
     * represented by subclass).
     *
     * @param vertex vertex which has been finished
     */
    private void finishVertex(NetworkVertex vertex) {
        // do nothing
    }
    
    private void addUnseenChildrenOf(NetworkVertex vertex, VisitColor previousColor) {

        if (vertex.isFullyTokened() && !vertex.hasCompanyToken(company)) return;
        
        for (NetworkEdge edge : graph.edgesOf(vertex)) {
            
            if (previousColor == VisitColor.WHITE || edge.isAutoEdge()) {  

                NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
                if (isSeenVertex(oppositeV)) {
                    encounterVertexAgain(oppositeV, edge);
                } else {
                    encounterVertex(oppositeV, edge);
                }
            }
        }
    }
    
    private void encounterStartVertex() {
        putSeenData(startVertex, VisitColor.WHITE);
        stack.add(startVertex);
        startVertex = null;
        log.debug("Iterator: Added to stack " + startVertex);
    }

    /** copy of standard dfs */
    private void encounterVertex(NetworkVertex vertex, NetworkEdge edge) {
        VisitColor color = VisitColor.WHITE;
        if (vertex.isSide() && !edge.isAutoEdge())
            color = VisitColor.YELLOW;
        putSeenData(vertex, color);
        stack.add(vertex);
        log.debug("Iterator: Added to stack " + vertex + " with color " + color);
    }

    /** copy of standard dfs */
    private void encounterVertexAgain(NetworkVertex vertex, NetworkEdge edge) {
        VisitColor color = getSeenData(vertex);
        if (color != VisitColor.WHITE && color != VisitColor.YELLOW) {
            // We've already visited this vertex; no need to mess with the
            // stack (either it's BLACK and not there at all, or it's GRAY
            // and therefore just a sentinel).
            return;
        }
        int i = stack.indexOf(vertex);

        // Since we've encountered it before, and it's still WHITE or YELLOW, it
        // *must* be on the stack.
        assert (i > -1);
        stack.remove(i);
        stack.add(vertex);
    }

    /** copy of standard dfs */
    private boolean isConnectedComponentExhausted() {
        while (true) {
            if (stack.isEmpty()) {
                return true;
            }
            if (peekStack() != null) {
                // Found a non-sentinel.
                return false;
            }

            // Found a sentinel:  pop it, record the finish time,
            // and then loop to check the rest of the stack.

            // Pop null we peeked at above.
            popStack();

            // This will pop corresponding vertex to be recorded as finished.
            recordFinish();
        }
    }

    /** copy of standard dfs */
    private NetworkVertex provideNextVertex() {
        NetworkVertex v;
        while (true) {
            v = popStack();
            if (v == null) {
                // This is a finish-time sentinel we previously pushed.
                recordFinish();
                // Now carry on with another pop until we find a non-sentinel
            } else {
                // Got a real vertex to start working on
                break;
            }
        }

        // Push a sentinel for v onto the stack so that we'll know
        // when we're done with it.
        stack.add(v);
        stack.add(null);
        return v;
    }

    private NetworkVertex popStack()
    {
        return stack.remove(stack.size() - 1);
    }

    private NetworkVertex peekStack()
    {
        return stack.get(stack.size() - 1);
    }

    private void recordFinish()
    {
        NetworkVertex v = popStack();
        putSeenData(v, VisitColor.BLACK);
        finishVertex(v);
    }
}

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

import java.awt.Dimension;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import javax.swing.JFrame;
import javax.swing.JScrollPane;


import org.apache.log4j.Logger;
import org.jgraph.JGraph;
import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.ext.JGraphModelAdapter;
import org.jgrapht.graph.SimpleGraph;
import org.jgrapht.graph.Subgraph;

import com.jgraph.layout.JGraphFacade;
import com.jgraph.layout.JGraphLayout;
import com.jgraph.layout.organic.JGraphFastOrganicLayout;

import rails.game.BaseToken;
import rails.game.City;
import rails.game.MapHex;
import rails.game.PublicCompanyI;
import rails.game.Station;
import rails.game.TileI;
import rails.game.TokenHolder;
import rails.game.TokenI;
import rails.game.Track;

public final class NetworkGraphBuilder implements Iterable<NetworkVertex> {

    protected static Logger log =
        Logger.getLogger(NetworkGraphBuilder.class.getPackage().getName());
    
    private SimpleGraph<NetworkVertex, NetworkEdge> mapGraph;  
    private Map<String, NetworkVertex> mapVertexes;
    private NetworkIterator iterator;
    
    public NetworkGraphBuilder() {
        this.mapGraph = null;
    }

    public void generateGraph(List<MapHex> mHexes) {
        
        mapGraph = new SimpleGraph<NetworkVertex, NetworkEdge>(NetworkEdge.class);
        mapVertexes = new HashMap<String, NetworkVertex> ();
        
        for (MapHex hex:mHexes) {
            // get Tile
            TileI tile = hex.getCurrentTile();
            
            // then get stations
            List<Station> stations = tile.getStations(); 
            // and add those to the mapGraph
            for (Station station: stations) {
                NetworkVertex stationVertex = new NetworkVertex(hex, station);
                mapGraph.addVertex(stationVertex);
                mapVertexes.put(stationVertex.getIdentifier(), stationVertex);
                log.debug("Added " + stationVertex + " / " + stationVertex.printTokens());
            }
            
            // get tracks per side to add that vertex
            for (int side=0; side<6; side++) 
                if (tile.getTracksPerSide(side).size() != 0) {
                    NetworkVertex sideVertex = new NetworkVertex(hex, side + hex.getCurrentTileRotation());
                    mapGraph.addVertex(sideVertex);
                    mapVertexes.put(sideVertex.getIdentifier(), sideVertex);
                    log.debug("Added " + sideVertex);
                }
        }
        
        // loop over all maps and add tracks
        for (MapHex hex:mHexes) {
            // get Tile
            TileI tile = hex.getCurrentTile();
            // get Tracks
            List<Track> tracks = tile.getTracks();

            for (Track track:tracks) {
                int[] points = track.points();
                NetworkVertex startVertex = getVertexRotated(hex, points[0]);
                NetworkVertex endVertex = getVertexRotated(hex, points[1]);
                log.debug("Track: " + track);
                NetworkEdge edge =  new NetworkEdge(startVertex, endVertex, false);
                mapGraph.addEdge(startVertex, endVertex, edge);
                log.debug("Added edge " + edge.getConnection());
            }

            // and connect to neighbouring hexes (for sides 0-2)
            for (int side=0; side <= 2; side++) {
                NetworkVertex vertex = getVertex(hex, side);
                MapHex neighborHex = hex.getNeighbor(side);
                if (neighborHex == null) {
                    log.debug("No connection for Hex " + hex.getName() + " at "
                            + hex.getOrientationName(side) + ", No Neighbor");
                    continue;
                }
                NetworkVertex otherVertex = getVertex(neighborHex, side + 3);
                if (vertex == null && otherVertex == null){
                    log.debug("Hex " + hex.getName() + " has no track at "
                            + hex.getOrientationName(side));
                    log.debug("And Hex " + neighborHex.getName() + " has no track at "
                            + neighborHex.getOrientationName(side + 3));
                    continue;
                }
                else if (vertex == null && otherVertex != null) { 
                    log.debug("Deadend connection for Hex " + neighborHex.getName() + " at "
                            + neighborHex.getOrientationName(side + 3) + ", NeighborHex "
                            + hex.getName() + " has no track at side " +
                            hex.getOrientationName(side));
                    vertex = new NetworkVertex(hex, side);
                    mapGraph.addVertex(vertex);
                    mapVertexes.put(vertex.getIdentifier(), vertex);
                    log.debug("Added deadend vertex " + vertex);
                }
                else if (otherVertex == null)  {
                    log.debug("Deadend connection for Hex " + hex.getName() + " at "
                            + hex.getOrientationName(side) + ", NeighborHex "
                            + neighborHex.getName() + " has no track at side " +
                            neighborHex.getOrientationName(side+3));
                    otherVertex = new NetworkVertex(neighborHex, side + 3);
                    mapGraph.addVertex(otherVertex);
                    mapVertexes.put(otherVertex.getIdentifier(), otherVertex);
                    log.debug("Added deadend vertex " + otherVertex);
                }
                NetworkEdge edge =  new NetworkEdge(vertex, otherVertex, true);
                mapGraph.addEdge(vertex, otherVertex, 
                        edge);
                log.debug("Added edge " + edge.getConnection());
            }
        }
    }        

    
    public SimpleGraph<NetworkVertex, NetworkEdge> getMapGraph() {
        return mapGraph;
    }

    public SimpleGraph<NetworkVertex, NetworkEdge> getRailRoadGraph(PublicCompanyI company) {
        
        // 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<TokenI> tokens = company.getTokens();
        Set<NetworkVertex> vertexes = new HashSet<NetworkVertex>();
        
        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
            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());
        }

        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);
        
        return graph;
    }
    
    public void setIteratorStart(MapHex hex, Station station) {
        iterator = new NetworkIterator(mapGraph, getVertex(hex, station));
    }
    
    @Override
    public Iterator<NetworkVertex> iterator() {
        return iterator; 
    }
    
    private NetworkVertex getVertex(MapHex hex, Station station) {
        return mapVertexes.get(hex.getName() + "." + -station.getNumber());
    }
    
    private NetworkVertex getVertex(MapHex hex, int side) {
        if (side >= 0)
            side = side % 6;
        return mapVertexes.get(hex.getName() + "." + side);
    }
    
    private NetworkVertex getVertexRotated(MapHex hex, int side) {
        if (side >= 0)
            side = (side + hex.getCurrentTileRotation()) % 6;
        return mapVertexes.get(hex.getName() + "." + side);
    }

    public static void optimizeGraph(Graph<NetworkVertex, NetworkEdge> graph) {
        while (removeVertexes(graph));
    }
    
    /** remove deadend and vertex with only two edges */ 
    private static boolean removeVertexes(Graph<NetworkVertex, NetworkEdge> graph){
        
        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 autoEdge = edges[0].isAutoEdge() || edges[1].isAutoEdge();
                graph.addEdge(firstVertex, secondVertex,
                        new NetworkEdge(firstVertex, secondVertex, autoEdge));
                // remove vertex
                graph.removeVertex(vertex);
                removed = true;
                break;
            }
        }     
        return removed;
    }
    
    public static void visualize(Graph<NetworkVertex, NetworkEdge> graph, String title) {
        // show network graph
        JGraphModelAdapter<NetworkVertex, NetworkEdge> jGAdapter =
            new JGraphModelAdapter<NetworkVertex, NetworkEdge>(graph);
        
        JGraph jgraph = new JGraph(jGAdapter);
        
        List<NetworkVertex> vertexes= new ArrayList<NetworkVertex>(graph.vertexSet());
         
        Object[] rootCell = new Object[1];
        rootCell[0] =  jGAdapter.getVertexCell(vertexes.get(0));
        
        JGraphFacade facade = new JGraphFacade(jgraph, rootCell);
        JGraphLayout layout = new JGraphFastOrganicLayout();
        layout.run(facade);
        
        facade.scale(new Rectangle(1600,1200));
        @SuppressWarnings("unchecked")
        Map nested = facade.createNestedMap(true,true);
        jgraph.getGraphLayoutCache().edit(nested);

        jgraph.setScale(0.8);
        
        JFrame frame = new JFrame();
        frame.setTitle(title + "(V=" + graph.vertexSet().size() + 
        		",E=" + graph.edgeSet().size() + ")");
        frame.setSize(new Dimension(800,600));
        frame.getContentPane().add(new JScrollPane(jgraph));
        frame.pack();
        frame.setVisible(true);
    }
}