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