package edu.hawaii.ics.yucheng;
import java.net.URL;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Scanner;
/**
* A weighted, connected, undirected graph. This class is immutable.
*/
final class Graph implements Iterable<Edge> {
/**
* This method verifies a graph is connected.
*
* @param graph The graph.
*
* @throws GraphException if the graph is invalid.
*/
private static void verifyConnectedGraph(final Graph graph) {
final int numVertices = graph.vertices();
// Create a matrix that marks which vertices are connected.
final Matrix<Boolean> matrix = new Matrix<Boolean>(numVertices,
numVertices, Boolean.FALSE);
for (final Edge e : graph) {
matrix.set(e.first(), e.second(), Boolean.TRUE);
matrix.set(e.second(), e.first(), Boolean.TRUE);
}
// Define an array of marked vertices that are initially false. The array
// elements are set to true when it is known the vertex is connected. The
// first vertex is always considered connected.
final boolean[] markedVertices = new boolean[numVertices];
Arrays.fill(markedVertices, false);
markedVertices[0] = true;
int markCount = 1;
// Implement a BFS search with this queue of vertices. In this while loop,
// each connected vertex is marked in the boolean array.
final LinkedListQueue<Integer> vertexQueue = new LinkedListQueue<Integer>();
vertexQueue.push(Integer.valueOf(0));
while (!vertexQueue.isEmpty()) {
final int u = vertexQueue.pop().intValue();
for (int i = 1; i < numVertices; i++)
if (matrix.get(u, i).booleanValue())
if (!markedVertices[i]) {
markedVertices[i] = true;
markCount++;
vertexQueue.push(Integer.valueOf(i));
}
}
// If not all vertices have been marked, the graph is not fully connected.
// Throw an exception if this is the case.
if (markCount < numVertices)
throw new GraphException("Invalid graph (unconnected graph detected)");
}
/**
* Verifies the graph has no duplicate edges.
*
* @param edges The collection of edges.
*
* @throws GraphException if the graph is invalid.
*/
private static void verifyNoDuplicateEdges(final Collection<Edge> edges) {
final Hashtable<Edge, Edge> temp = new Hashtable<Edge, Edge>();
for (final Edge e : edges) {
if (temp.containsKey(e))
throw new GraphException("Invalid graph (duplicate edge " + e
+ " detected)");
temp.put(e, e);
}
}
private final ArrayList<Edge> myEdges;
private final URL myUrl;
private final float[] myVertices;
/**
* Initializes a new instance of the class.
*
* @param vertices The vertices.
*
* @param edges The edges.
*/
public Graph(final float[] vertices, final Collection<Edge> edges) {
if (vertices == null)
throw new NullPointerException("vertices");
if (edges == null)
throw new NullPointerException("edges");
if (vertices.length < 1)
throw new GraphException("Not enough vertices");
if (vertices.length - 1 > edges.size())
throw new GraphException("Not enough edges");
for (final Edge e : edges)
if (e == null)
throw new GraphException("Null edge");
// Verify there are no duplicate edges in the collection.
verifyNoDuplicateEdges(edges);
// Make a copy of the collection to protect the class data.
myEdges = new ArrayList<Edge>(edges);
// Sort the collection so toString looks good.
Collections.sort(myEdges);
// Initialize the rest of the class data, and verify the graph is connected.
myVertices = vertices;
myUrl = null;
verifyConnectedGraph(this);
}
/**
* Initializes a new instance of the class.
*
* @param scanner The scanner.
*
* @param url The url.
*
* @throws GraphException Thrown if there are any errors reading from the
* scanner.
*/
public Graph(final Scanner scanner, final URL url) throws GraphException {
if (scanner == null)
throw new NullPointerException("scanner");
if (url == null)
throw new NullPointerException("url");
// Save the URL.
myUrl = url;
// Rethrow any exceptions as GraphException types.
try {
// Read the number of vertices.
final int vertexCount = Integer.parseInt(scanner.nextLine().trim());
if (vertexCount < 1)
throw new GraphException("Invalid graph (no vertices)");
// Read the number of edges.
final int edgeCount = Integer.parseInt(scanner.nextLine().trim());
if (edgeCount < vertexCount - 1)
throw new GraphException("Invalid graph (not enough edges)");
// Read each vertex weight.
final String[] fields = scanner.nextLine().split("\t");
if (fields.length != vertexCount)
throw new GraphException("Invalid graph (inconsistent vertex count)");
myVertices = new float[vertexCount];
for (int i = 0; i < vertexCount; i++)
myVertices[i] = Float.parseFloat(fields[i].trim());
// Loop over each edge.
myEdges = new ArrayList<Edge>(edgeCount);
for (int i = 0; i < edgeCount; i++) {
// Read and add the next edge, checking for duplicates.
if (!scanner.hasNextLine())
throw new GraphException("Invalid graph (inconsistent edge count)");
final Edge edge = new Edge(scanner);
myEdges.add(edge);
// Check the constraints.
if (edge.first() >= vertexCount || edge.second() >= vertexCount)
throw new GraphException(
"Invalid graph (Vertex index for edge too large)");
}
// Verify there are no duplicate edges in the collection.
verifyNoDuplicateEdges(myEdges);
// Check there are not too many vertices defined.
while (scanner.hasNextLine())
if (scanner.nextLine().trim().length() > 0)
throw new GraphException("Invalid graph (inconsistent edge count)");
} catch (final GraphException e) {
throw e;
} catch (final NumberFormatException e) {
throw new GraphException("Invalid graph (invalid number format)");
} catch (final Exception e) {
final String name = e.getClass().getName();
throw new GraphException("Invalid graph (" + name + ")", e);
}
verifyConnectedGraph(this);
}
/**
* Returns the edge at the specified index.
*
* @param index The index.
*
* @return The edge.
*/
public Edge edgeAt(final int index) {
if (index < 0 || index >= myEdges.size())
throw new IllegalArgumentException("index");
return myEdges.get(index);
}
/**
* Returns the number of edges.
*
* @return The number of edges.
*/
public int edges() {
return myEdges.size();
}
/**
* Returns an iterator for the edges.
*
* @return An Edge iterator.
*/
public Iterator<Edge> iterator() {
return myEdges.iterator();
}
/**
* Returns the string representation of the class.
*
* @return The string representation of the class.
*/
@Override
public String toString() {
final StringBuilder builder = new StringBuilder();
builder.append("V = {");
for (final float v : myVertices)
builder.append(" " + v);
builder.append(" }; E = {");
for (final Edge e : myEdges)
builder.append(" " + e);
builder.append(" }");
return builder.toString();
}
/**
* Returns the URL, if one was assigned.
*
* @return The URL.
*/
public URL url() {
return myUrl;
}
/**
* Returns the vertex weight at the specified index.
*
* @param index The index.
*
* @return The weight.
*/
public float vertexAt(final int index) {
if (index < 0 || index >= myVertices.length)
throw new IllegalArgumentException("index");
return myVertices[index];
}
/**
* Returns the number of vertices.
*
* @return The number of vertices.
*/
public int vertices() {
return myVertices.length;
}
}
