import java.util.*;
public abstract class AbstractGraph implements Graph {
protected List vertices = new ArrayList(); // Store vertices
protected List> neighbors
= new ArrayList>(); // Adjacency lists
/** Construct an empty graph */
protected AbstractGraph() {
}
/** Construct a graph from edges and vertices stored in arrays */
protected AbstractGraph(int[][] edges, V[] vertices) {
for (int i = 0; i < vertices.length; i++)
this.vertices.add(vertices[i]);
createAdjacencyLists(edges, vertices.length);
}
/** Construct a graph from edges and vertices stored in List */
protected AbstractGraph(List edges, List vertices) {
for (int i = 0; i < vertices.size(); i++)
this.vertices.add(vertices.get(i));
createAdjacencyLists(edges, vertices.size());
}
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
protected AbstractGraph(List edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
protected AbstractGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(
int[][] edges, int numberOfVertices) {
// Create a linked list
for (int i = 0; i < numberOfVertices; i++) {
neighbors.add(new ArrayList());
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
neighbors.get(u).add(v);
}
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(
List edges, int numberOfVertices) {
// Create a linked list for each vertex
for (int i = 0; i < numberOfVertices; i++) {
neighbors.add(new ArrayList());
}
for (Edge edge: edges) {
neighbors.get(edge.u).add(edge.v);
}
}
@Override /** Return the number of vertices in the graph */
public int getSize() {
return vertices.size();
}
@Override /** Return the vertices in the graph */
public List getVertices() {
return vertices;
}
@Override /** Return the object for the specified vertex */
public V getVertex(int index) {
return vertices.get(index);
}
@Override /** Return the index for the specified vertex object */
public int getIndex(V v) {
return vertices.indexOf(v);
}
@Override /** Return the neighbors of the specified vertex */
public List getNeighbors(int index) {
return neighbors.get(index);
}
@Override /** Return the degree for a specified vertex */
public int getDegree(int v) {
return neighbors.get(v).size();
}
@Override /** Print the edges */
public void printEdges() {
for (int u = 0; u < neighbors.size(); u++) {
System.out.print(getVertex(u) + " (" + u + "): ");
for (int j = 0; j < neighbors.get(u).size(); j++) {
System.out.print("(" + u + ", " +
neighbors.get(u).get(j) + ") ");
}
System.out.println();
}
}
@Override /** Clear graph */
public void clear() {
vertices.clear();
neighbors.clear();
}
@Override /** Add a vertex to the graph */
public void addVertex(V vertex) {
vertices.add(vertex);
neighbors.add(new ArrayList());
}
@Override /** Add an edge to the graph */
public void addEdge(int u, int v) {
neighbors.get(u).add(v);
neighbors.get(v).add(u);
}
/** Edge inner class inside the AbstractGraph class */
public static class Edge {
public int u; // Starting vertex of the edge
public int v; // Ending vertex of the edge
/** Construct an edge for (u, v) */
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
}
@Override /** Obtain a DFS tree starting from vertex v */
/** To be discussed in Section 27.6 */
public Tree dfs(int v) {
List searchOrder = new ArrayList();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1
// Mark visited vertices
boolean[] isVisited = new boolean[vertices.size()];
// Recursively search
dfs(v, parent, searchOrder, isVisited);
// Return a search tree
return new Tree(v, parent, searchOrder);
}
/** Recursive method for DFS search */
private void dfs(int v, int[] parent, List searchOrder,
boolean[] isVisited) {
// Store the visited vertex
searchOrder.add(v);
isVisited[v] = true; // Vertex v visited
for (int i : neighbors.get(v)) {
if (!isVisited[i]) {
parent[i] = v; // The parent of vertex i is v
dfs(i, parent, searchOrder, isVisited); // Recursive search
}
}
}
@Override /** Starting bfs search from vertex v */
/** To be discussed in Section 27.7 */
public Tree bfs(int v) {
List searchOrder = new ArrayList();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1
java.util.LinkedList queue =
new java.util.LinkedList(); // list used as a queue
boolean[] isVisited = new boolean[vertices.size()];
queue.offer(v); // Enqueue v
isVisited[v] = true; // Mark it visited
while (!queue.isEmpty()) {
int u = queue.poll(); // Dequeue to u
searchOrder.add(u); // u searched
for (int w : neighbors.get(u)) {
if (!isVisited[w]) {
queue.offer(w); // Enqueue w
parent[w] = u; // The parent of w is u
isVisited[w] = true; // Mark it visited
}
}
}
return new Tree(v, parent, searchOrder);
}
/** Tree inner class inside the AbstractGraph class */
/** To be discussed in Section 27.5 */
public class Tree {
private int root; // The root of the tree
private int[] parent; // Store the parent of each vertex
private List searchOrder; // Store the search order
/** Construct a tree with root, parent, and searchOrder */
public Tree(int root, int[] parent, List searchOrder) {
this.root = root;
this.parent = parent;
this.searchOrder = searchOrder;
}
/** Return the root of the tree */
public int getRoot() {
return root;
}
/** Return the parent of vertex v */
public int getParent(int v) {
return parent[v];
}
/** Return an array representing search order */
public List getSearchOrder() {
return searchOrder;
}
/** Return number of vertices found */
public int getNumberOfVerticesFound() {
return searchOrder.size();
}
/** Return the path of vertices from a vertex to the root */
public List getPath(int index) {
ArrayList path = new ArrayList();
do {
path.add(vertices.get(index));
index = parent[index];
}
while (index != -1);
return path;
}
/** Print a path from the root to vertex v */
public void printPath(int index) {
List path = getPath(index);
System.out.print("A path from " + vertices.get(root) + " to " +
vertices.get(index) + ": ");
for (int i = path.size() - 1; i >= 0; i--)
System.out.print(path.get(i) + " ");
}
/** Print the whole tree */
public void printTree() {
System.out.println("Root is: " + vertices.get(root));
System.out.print("Edges: ");
for (int i = 0; i < parent.length; i++) {
if (parent[i] != -1) {
// Display an edge
System.out.print("(" + vertices.get(parent[i]) + ", " +
vertices.get(i) + ") ");
}
}
System.out.println();
}
}
}