JadeSolver.java

package edu.hawaii.ics.yucheng;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;

/**
 * A graph solver that runs in O(V*E) time.
 */
class JadeSolver extends GraphSolver {

    /**
     * A class that encapsulates the graph file conveniently for the algorithm.
     */
    class GraphData implements Iterable<VertexNode> {
        private final Matrix<Boolean>       myConnections;
        private final Graph                 myData;
        private final ArrayList<VertexNode> myVertices;


        /**
         * Initializes a new instance of the class.
         * 
         * @param graph The graph file data.
         */
        public GraphData(final Graph graph) {
            if (graph == null)
                throw new NullPointerException("g");

            // Keep the raw graph data.
            myData = graph;

            // This is similar to the SolutionMatrix, but it stores all possible
            // edges, not just the edges in the solution.
            final int vertices = graph.vertices();
            myConnections = new Matrix<Boolean>(vertices, vertices, Boolean.FALSE);
            for (final Edge edge : graph) {
                myConnections.set(edge.first(), edge.second(), Boolean.TRUE);
                myConnections.set(edge.second(), edge.first(), Boolean.TRUE);
            }

            // Create a collection of VertexNode instances.
            myVertices = new ArrayList<VertexNode>(vertices);
            for (int index = 0; index < vertices; index++)
                myVertices.add(new VertexNode(this, index));

            // Initialize the collection of neighbors.
            for (int index = 0; index < vertices; index++)
                myVertices.get(index).neighbors();
        }


        /**
         * Returns true if the specified vertices are connected.
         * 
         * @param first The first vertex.
         * 
         * @param second The second vertex.
         * 
         * @return True indicates the vertices are connected.
         */
        public boolean isConnected(final int first, final int second) {
            return myConnections.get(first, second).booleanValue();
        }


        /**
         * Returns a vertex node iterator.
         * 
         * @return A vertex node iterator.
         */
        public Iterator<VertexNode> iterator() {
            return myVertices.iterator();
        }


        /**
         * Returns the vertex node at the specified index.
         * 
         * @param index The index.
         * 
         * @return The vertex node at the specified index.
         */
        public VertexNode nodeAt(final int index) {
            return myVertices.get(index);
        }


        /**
         * Returns the string representation of the class data.
         * 
         * @return The string representation of the class data.
         */
        @Override
        public String toString() {
            final StringBuilder builder = new StringBuilder();
            builder.append("{\n");
            for (final VertexNode vertex : this)
                builder.append("  " + vertex + "\n");
            builder.append("}");
            return builder.toString();
        }


        /**
         * Returns the number of vertices.
         * 
         * @return The number of vertices.
         */
        public int vertices() {
            return myData.vertices();
        }


        /**
         * Returns the weight of the specified vertex.
         * 
         * @param index The vertex index.
         * 
         * @return The weight of the vertex.
         */
        public float weightAt(final int index) {
            return myData.vertexAt(index);
        }
    }

    /**
     * A queue used to hold a collection of vertex nodes.
     */
    class Queue extends LinkedListQueue<VertexNode> {
        // This class is used only to improve readability of the algorithm.
    }

    /**
     * A solution matrix, which is a matrix with v rows and v columns that holds
     * booleans indicating whether or not vertices are connected.
     */
    class SolutionMatrix extends Matrix<Boolean> {
        /**
         * Initializes a new instance of the class based on the number of vertices
         * in a graph.
         * 
         * @param g A graph.
         */
        public SolutionMatrix(final GraphData g) {
            super(g.vertices(), g.vertices(), Boolean.FALSE);
        }


        /**
         * Initializes a new instance of the class based on the specified matrix.
         * 
         * @param m The matrix.
         */
        private SolutionMatrix(final SolutionMatrix m) {
            super(m);
        }


        /**
         * Returns a clone of the solution matrix.
         * 
         * @return A clone of the solution matrix.
         */
        @Override
        public SolutionMatrix clone() {
            return new SolutionMatrix(this);
        }


        /**
         * Returns the edges in the collection.
         * 
         * @return The edges.
         */
        private Collection<Edge> getEdges() {
            final int rows = rows();
            final int columns = columns();
            final Collection<Edge> edges = new ArrayList<Edge>(rows);
            for (int a = 0; a < rows; a++)
                for (int b = a + 1; b < columns; b++)
                    if (isMarked(a, b))
                        edges.add(new Edge(a, b));
            return edges;
        }


        /**
         * Returns a partial solution, i.e. no root node and no weight.
         * 
         * @return A partial solution.
         */
        public GraphSolution getSolution() {
            return new GraphSolution(getEdges());
        }


        /**
         * Returns a solution with a root vertex selection and a weight.
         * 
         * @param root The root vertex.
         * 
         * @param weight The total weight.
         * 
         * @return The solution.
         */
        public GraphSolution getSolution(final VertexNode root, final float weight) {
            if (root == null)
                throw new NullPointerException("root");
            return new GraphSolution(getEdges(), root.index, weight);
        }


        /**
         * Returns true if an item in the matrix is marked true.
         * 
         * @param a The first vertex.
         * 
         * @param b The second vertex.
         * 
         * @return True indicates the vertices edge is marked.
         */
        public boolean isMarked(final int a, final int b) {
            return get(a, b).booleanValue();
        }


        /**
         * Marks two vertices to define an edge.
         * 
         * @param a One vertex.
         * 
         * @param b Another vertex.
         */
        public void mark(final int a, final int b) {
            set(a, b, Boolean.TRUE);
        }


        /**
         * Marks two vertices to define an edge.
         * 
         * @param a One vertex.
         * 
         * @param b Another vertex.
         */
        public void mark(final VertexNode a, final VertexNode b) {
            if (a == null)
                throw new NullPointerException("a");
            if (b == null)
                throw new NullPointerException("b");
            mark(a.index, b.index);
        }


        /**
         * Un-marks all vertices.
         */
        public void reset() {
            final int rows = rows();
            final int columns = columns();
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < columns; j++)
                    set(i, j, Boolean.FALSE);
        }


        /**
         * Sets a value in the matrix. The values are mirrored so edges can be
         * defined in any order.
         * 
         * @param a One vertex
         * 
         * @param b Another vertex.
         */
        @Override
        public void set(final int a, final int b, final Boolean value) {
            super.set(a, b, value);
            super.set(b, a, value);
        }
    }

    /**
     * Implementation of a vertex node. Each node holds a vertex index, weight, a
     * list of connected vertices, and an array that provides O(1) time to
     * determine if another vertex is connected.
     */
    class VertexNode {
        /**
         * The index of the vertex.
         */
        public final int               index;

        private final GraphData        myGraph;
        private int                    myHops;
        private Collection<VertexNode> myNeighborCache;

        /**
         * The weight of the vertex.
         */
        public final float             weight;


        /**
         * Initializes a new instance of the class.
         * 
         * @param g The graph data.
         * 
         * @param index The vertex index for this instance.
         */
        public VertexNode(final GraphData g, final int index) {
            if (g == null)
                throw new NullPointerException("g");
            if (index < 0 || index >= g.vertices())
                throw new IndexOutOfBoundsException("index");

            this.index = index;
            weight = g.weightAt(index);

            myGraph = g;
            myHops = 0;
            myNeighborCache = null;
        }


        /**
         * Returns the degree (the number of edges).
         * 
         * @return The degree.
         */
        public int degree() {
            return neighbors().size();
        }


        /**
         * Returns the number of hops.
         * 
         * @return The number of hops.
         */
        public int hops() {
            return myHops;
        }


        /**
         * Returns a collection of neighboring vertices.
         * 
         * @return A collection of neighboring vertices.
         */
        public Collection<VertexNode> neighbors() {
            if (myNeighborCache == null) {
                final int vertices = myGraph.vertices();

                final ArrayList<VertexNode> neighbors = new ArrayList<VertexNode>(
                    vertices);

                for (int i = 0; i < vertices; i++)
                    if (myGraph.isConnected(index, i))
                        neighbors.add(myGraph.nodeAt(i));

                myNeighborCache = Collections.unmodifiableCollection(neighbors);
            }

            return myNeighborCache;
        }


        /**
         * Sets the number of hops associated with this vertex to the root.
         * 
         * @param hops The number of hops.
         */
        public void setHops(final int hops) {
            myHops = hops;
        }


        /**
         * Returns the string representation of the class data.
         * 
         * @return The string representation of the class data.
         */
        @Override
        public String toString() {
            final StringBuilder builder = new StringBuilder();
            builder.append("[" + index + ":" + weight + "] --> ");
            if (degree() == 0)
                builder.append("null");
            else {
                builder.append("{");
                for (final VertexNode node : neighbors())
                    builder.append(" " + node.index);
                builder.append(" }");
            }
            return builder.toString();
        }
    }

    private static final int   INFINITE_HOPS   = Integer.MAX_VALUE;
    private static final float INFINITE_WEIGHT = Float.MAX_VALUE;


    /**
     * Static methods cannot be declared in inner classes due to a java
     * limitation, so this method is implemented here instead of the
     * SolutionMatrix class. This method returns the GraphSolution for a
     * SolutionMatrix, VertexNode, and a weight.
     * 
     * @param bestWeight The best weight.
     * 
     * @param bestRoot The best root index.
     * 
     * @param bestSolution The best solution.
     * 
     * @return A GraphSolution object understood by the rest of the package.
     */
    static GraphSolution getSolution(final float bestWeight,
        final VertexNode bestRoot, final SolutionMatrix bestSolution) {

        if (bestSolution == null)
            throw new NullPointerException("bestSolution");

        return bestSolution.getSolution(bestRoot, bestWeight);
    }


    /**
     * Animates a partial solution.
     * 
     * @param solution The partial solution.
     */
    private void animate(final SolutionMatrix solution) {
        if (isAnimating())
            publish(solution.getSolution());
    }


    /**
     * Solves a graph or returns null if there is no solution.
     * 
     * @param g The graph.
     * 
     * @return The solution.
     */
    @Override
    public GraphSolution solve(final Graph g) {
        if (g == null)
            throw new NullPointerException("g");

        // Put the graph file data into a convenient data structure.
        final GraphData graph = new GraphData(g);

        // Determine the node with the maximum weight.
        VertexNode maxVertex = null;
        for (final VertexNode vertex : graph)
            if (maxVertex == null || vertex.weight > maxVertex.weight)
                maxVertex = vertex;

        // Determine the possible candidates for the root node.
        final Queue rootCandidates = new Queue();
        for (final VertexNode vertex : graph)
            if (vertex.degree() != 1 || vertex == maxVertex)
                rootCandidates.push(vertex);

        // The following three values are assigned when a solution is found below.
        float bestWeight = INFINITE_WEIGHT;
        VertexNode bestRoot = null;
        SolutionMatrix bestSolution = null;

        // Declare the solution matrix outside the loop to increase speed.
        final SolutionMatrix solution = new SolutionMatrix(graph);

        // Loop while there are remaining candidates.
        while (!rootCandidates.isEmpty()) {

            // Try the next candidate as the root.
            final VertexNode root = rootCandidates.pop();
            final Queue queue = new Queue();
            queue.push(root);
            root.setHops(0);

            // Set all non-root vertices to infinite hops to indicate no path exists.
            for (final VertexNode vertex : graph)
                if (vertex != root)
                    vertex.setHops(INFINITE_HOPS);

            // The famous BFS algorithm...
            solution.reset();
            while (!queue.isEmpty()) {
                final VertexNode vertex = queue.pop();
                for (final VertexNode neighbor : vertex.neighbors())
                    if (neighbor.hops() == INFINITE_HOPS) {
                        neighbor.setHops(1 + vertex.hops());
                        solution.mark(neighbor, vertex);
                        queue.push(neighbor);

                        animate(solution);
                    }
            }

            // Add the weight for each vertex to the total weight.
            float weight = 0.0f;
            for (final VertexNode vertex : graph)
                weight += vertex.weight * vertex.hops();

            // Keep this solution, weight, and root if it is best.
            if (weight < bestWeight) {
                bestWeight = weight;
                bestSolution = solution.clone();
                bestRoot = root;
            }
        }

        // Return the best solution as something usable by the outside world.
        return getSolution(bestWeight, bestRoot, bestSolution);
    }
}
Valid HTML 4.01 Valid CSS