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); } }