transitstub.java

High performance DB query

/*
 * @(#)$Id: TransitStub.java,v 1.24 2004/07/02 23:59:22 huebsch Exp $
 *
 * Copyright (c) 2001-2004 Regents of the University of California.
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached BERKELEY-LICENSE
 * file. If you do not find these files, copies can be found by writing to:
 * Computer Science Division, Database Group, Universite of California,
 * 617 Soda Hall #1776, Berkeley, CA 94720-1776. Attention: Berkeley License
 *
 * Copyright (c) 2003-2004 Intel Corporation. All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE file.
 * If you do not find these files, copies can be found by writing to:
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300,
 * Berkeley, CA, 94704.  Attention:  Intel License Inquiry.
 */


package simulator.schedulers.network.topology.transitstub;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.LineNumberReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
import java.util.StringTokenizer;
import org.apache.log4j.Logger;

/**
 * Class TransitStub
 *
 */
public class TransitStub {

    private static Logger logger = Logger.getLogger(TransitStub.class);
    short numVertices = -1;
    int numEdges = -1;
    HashMap vertices = new HashMap();
    HashMap edges = new HashMap();
    HashMap paths = new HashMap();    // matrix of all paths
    boolean directed;                 // whether edges read are directed
    String outputFile, filename;
    PrintWriter pw = null;
    Random random;

    /**
     * Constructor TransitStub
     *
     * @param filename
     * @param directed
     * @param dumpOutput
     * @param random
     */
    public TransitStub(String filename, boolean directed, boolean dumpOutput,
                       Random random) {
        this.filename = filename;
        this.random = random;
        this.directed = directed;

        try {

            // read and parse the file
            File file = new File(filename);
            LineNumberReader gtmReader =
                new LineNumberReader(new BufferedReader(new FileReader(file)));

            if (dumpOutput == true) {
                outputFile = filename + ".precompute";
                pw = new PrintWriter(
                    new BufferedWriter(new FileWriter(new File(outputFile))));
            } else {
                pw = null;
            }

            String str = gtmReader.readLine();

            while (str != null) {
                if (str.startsWith("GRAPH")) {
                    handleGraphHeader(str, gtmReader);
                }

                if (str.startsWith("VERTICES")) {
                    handleVertices(gtmReader);
                }

                if (str.startsWith("EDGES")) {
                    handleEdges(gtmReader);
                }

                str = gtmReader.readLine();
            }

            gtmReader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * Method getPaths
     * @return
     */
    public HashMap getPaths() {
        return paths;
    }

    /**
     * Method getPath
     *
     * @param sourceVertex
     * @param destinationVertex
     * @param cacheAllPaths
     * @return
     */
    public Path getPath(Vertex sourceVertex, Vertex destinationVertex,
                        boolean cacheAllPaths) {
        Path probePath =
            new Path(sourceVertex.getVertexNumber().shortValue(),
                     destinationVertex.getVertexNumber().shortValue());
        Path path = (Path) paths.get(probePath);

        if (path != null) {
            return path;
        }

        if (cacheAllPaths == true) {
            shortestPath(sourceVertex, null);

            return (Path) paths.get(probePath);
        }

        return shortestPath(sourceVertex, destinationVertex);
    }

    /**
     * Method numVertices
     * @return
     */
    public short numVertices() {
        return numVertices;
    }

    /**
     * Method getRandomVertex
     *
     * @param multipleNodes
     * @return
     */
    public Vertex getRandomVertex(boolean multipleNodes) {
        short vertexNumber = (short) (random.nextDouble() * numVertices);
        short counter = 0;

        while (counter <= numVertices) {
            counter++;

            Vertex v = (Vertex) vertices.get(new Short(vertexNumber));

            if (v.isStub() == true) {
                if (multipleNodes) {
                    return v;
                } else if (v.isAssigned() == false) {
                    v.setAssign(true);

                    return v;
                }
            }

            vertexNumber = (short) ((vertexNumber + 1) % numVertices);
        }

        return null;
    }

    private Path shortestPath(Vertex source, Vertex destination) {

        // generate shortest path from source to all other nodes in the universe
        DijkstraQueue dq = new DijkstraQueue();

        // initialize with my most immediate neighbors
        ArrayList v = (ArrayList) edges.get(source.getVertexNumber());

        if ((v == null) || (v.size() == 0)) {
            logger.error("No edges!");

            return null;
        }

        HashMap outstanding = new HashMap();

        // initialize all the vertices
        for (short k = 0; k < numVertices; k++) {
            Vertex vertex = (Vertex) vertices.get(new Short(k));
            DijkstraContainer dc = new DijkstraContainer(vertex);

            outstanding.put(dc.getVertex().getVertexNumber(), dc);

            if (vertex.getVertexNumber().equals(source.getVertexNumber())) {
                dc.setCurrentWeight(0);
            } else {
                dc.setCurrentWeight(Integer.MAX_VALUE);
            }

            dc.setPath(new ArrayList());
            dq.addElement(dc);
        }

        HashMap determined =
            new HashMap();    // set of vertices whose shortest path have been determined

        while (dq.isEmpty() == false) {
            DijkstraContainer dc = dq.getNext();

            determined.put(dc.getVertex().getVertexNumber(), dc);
            outstanding.remove(dc.getVertex().getVertexNumber());

            ArrayList path = dc.getPath();

            path.add(dc.getVertex());
            dc.setPath(path);

            if (destination != null) {

                // only interested in one path
                if (dc.getVertex().getVertexNumber().equals(
                        destination.getVertexNumber())) {
                    Path aPath =
                        new Path(source.getVertexNumber().shortValue(),
                                 dc.getVertex().getVertexNumber().shortValue());

                    aPath.setPath(dc.getPath().toArray());
                    paths.put(aPath, aPath);

                    dq = null;
                    determined = null;
                    outstanding = null;

                    return aPath;
                }
            }

            // relax neighbors
            ArrayList currentEdges =
                (ArrayList) edges.get(dc.getVertex().getVertexNumber());
            int baseWeight = dc.getCurrentWeight();

            if (currentEdges != null) {
                for (int k = 0; k < currentEdges.size(); k++) {
                    Edge edge = (Edge) currentEdges.get(k);
                    DijkstraContainer neighborDC =
                        (DijkstraContainer) outstanding.get(edge.getToVertex());

                    if (neighborDC != null) {
                        if (neighborDC.getCurrentWeight()
                                > (baseWeight + edge.getWeight())) {
                            int oldValue = neighborDC.getCurrentWeight();

                            // replace by our lower weight
                            neighborDC.setCurrentWeight(baseWeight
                                                        + edge.getWeight());

                            // change its current shortest path
                            ArrayList newPath =
                                (ArrayList) dc.getPath().clone();

                            neighborDC.setPath(newPath);
                            dq.changeElement(neighborDC, oldValue);
                        }
                    }
                }
            }
        }

        if (determined.size() < numVertices) {
            logger.error("Error: Some vertices unknown path");
        }

        // store all paths
        Iterator elements = determined.values().iterator();

        while (elements.hasNext()) {
            DijkstraContainer dc = (DijkstraContainer) elements.next();
            Path aPath =
                new Path(source.getVertexNumber().shortValue(),
                         dc.getVertex().getVertexNumber().shortValue());

            aPath.setPath(dc.getPath().toArray());

            if (pw != null) {
                pw.print(source.getVertexNumber() + " -> "
                         + dc.getVertex().getVertexNumber() + " : ");

                ArrayList path = dc.getPath();

                for (int k = 0; k < path.size(); k++) {
                    Vertex nextVertex = (Vertex) path.get(k);

                    pw.print("<" + nextVertex.getVertexNumber() + " "
                             + nextVertex.isStub() + "> ");
                }

                pw.println();
            }

            paths.put(aPath, aPath);
        }

        dq = null;
        determined = null;
        outstanding = null;

        return null;
    }

    /**
     * Method loadPrecompute
     */
    public void loadPrecompute() {
        try {
            File file = new File(this.filename + ".precompute");

            if ((file.exists() == false) || (file.length() == 0)) {
                generateShortestPaths();

                return;
            }

            LineNumberReader reader =
                new LineNumberReader(new BufferedReader(new FileReader(file)));
            String nextLine = reader.readLine();

            while (nextLine != null) {
                StringTokenizer st = new StringTokenizer(nextLine, ":->< ");
                short fromVertex = Short.parseShort(st.nextToken());
                short toVertex = Short.parseShort(st.nextToken());
                Path aPath = new Path(fromVertex, toVertex);
                ArrayList list = new ArrayList();

                while (st.hasMoreTokens()) {
                    short vertex = Short.parseShort(st.nextToken());
                    short type = Short.parseShort(st.nextToken());

                    list.add(new Vertex(vertex, type));
                }

                aPath.setPath(list.toArray());
                paths.put(aPath, aPath);

                nextLine = reader.readLine();
                st = null;
            }

            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * Method generateShortestPaths
     */
    public void generateShortestPaths() {
        Iterator elements = vertices.values().iterator();

        while (elements.hasNext()) {
            Vertex v = (Vertex) elements.next();

            shortestPath(v, null);
        }

        if (pw != null) {
            pw.close();
        }
    }

    private void handleEdges(LineNumberReader lnr) throws IOException {
        int iterations = numEdges / 2;

        if (directed == false) {
            iterations = numEdges;
        }

        for (int k = 0; k < numEdges / 2; k++) {
            String str = lnr.readLine();
            StringTokenizer st = new StringTokenizer(str);
            short fromVertex = Short.parseShort(st.nextToken());
            short toVertex = Short.parseShort(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            Edge edge = new Edge(fromVertex, toVertex, weight);

            if (edges.get(new Short(fromVertex)) != null) {
                ArrayList v = (ArrayList) edges.get(new Short(fromVertex));

                v.add(edge);
            } else {
                ArrayList v = new ArrayList();

                v.add(edge);
                edges.put(new Short(fromVertex), v);
            }

            if (directed == false) {
                edge = new Edge(toVertex, fromVertex, weight);

                if (edges.get(new Short(toVertex)) != null) {
                    ArrayList v = (ArrayList) edges.get(new Short(toVertex));

                    v.add(edge);
                } else {
                    ArrayList v = new ArrayList();

                    v.add(edge);
                    edges.put(new Short(toVertex), v);
                }
            }
        }
    }

    private void handleVertices(LineNumberReader lnr) throws IOException {
        for (int k = 0; k < numVertices; k++) {
            String str = lnr.readLine();
            StringTokenizer st = new StringTokenizer(str, "/: ");
            String token = st.nextToken();
            short vertexNumber = Short.parseShort(token);

            token = st.nextToken();

            short type = -1;

            if (token.equals("T")) {
                type = Vertex.TRANSIT_NODE;
            } else {
                type = Vertex.STUB_NODE;
            }

            Vertex newVertex = new Vertex(vertexNumber, type);

            vertices.put(new Short(vertexNumber), newVertex);
        }
    }

    private void handleGraphHeader(String string, LineNumberReader lnr)
            throws IOException {
        String str = lnr.readLine();
        StringTokenizer st = new StringTokenizer(str);

        numVertices = Short.parseShort(st.nextToken());
        numEdges = Integer.parseInt(st.nextToken());
    }

    /**
     * Method main
     *
     * @param args
     */
    public static void main(String args[]) {
        TransitStub ts = new TransitStub(args[0],
                                         new Boolean(args[1]).booleanValue(),
                                         new Boolean(args[2]).booleanValue(),
                                         new Random(0));

        ts.generateShortestPaths();
    }
}