## Thursday, 16 February 2017

### Chapter 28 Exercise 5, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

28.5 (Find paths) Add a new method in AbstractGraph to find a path between two vertices with the following header:
public List<Integer> getPath(int u, int v);
The method returns a List<Integer> that contains all the vertices in a path
from u to v in this order. Using the BFS approach, you can obtain a shortest
path from u to v . If there isn’t a path from u to v , the method returns null .

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Exercise05 {

public static void main(String[] args) {
String[] vertices = { "Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston" };

int[][] edges = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

UnweightedGraph<String> graph1 = new UnweightedGraph<String>(edges, vertices);
System.out.println(graph1.getPath(0, 11));
System.out.println(graph1.getPath(11, 0));
}

static class UnweightedGraph<V> extends AbstractGraph<V> {
/** Construct an empty graph */
public UnweightedGraph() {
}

/** Construct a graph from edges and vertices stored in arrays */
public UnweightedGraph(int[][] edges, V[] vertices) {
super(edges, vertices);
}

/** Construct a graph from edges and vertices stored in List */
public UnweightedGraph(List<Edge> edges, List<V> vertices) {
super(edges, vertices);
}

/** Construct a graph for integer vertices 0, 1, 2 and edge list */
public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
super(edges, numberOfVertices);
}

/** Construct a graph from integer vertices 0, 1, and edge array */
public UnweightedGraph(int[][] edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
}

static abstract class AbstractGraph<V> implements Graph<V> {
protected List<V> vertices = new ArrayList<V>(); // Store vertices
protected List<List<Integer>> neighbors = new ArrayList<List<Integer>>(); // 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++)

}

/** Construct a graph from edges and vertices stored in List */
protected AbstractGraph(List<Edge> edges, List<V> vertices) {
for (int i = 0; i < vertices.size(); i++)

}

/** Construct a graph for integer vertices 0, 1, 2 and edge list */
@SuppressWarnings("unchecked")
protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V) (new Integer(i))); // vertices is {0, 1, ...}

}

/** Construct a graph from integer vertices 0, 1, and edge array */
@SuppressWarnings("unchecked")
protected AbstractGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
vertices.add((V) (new Integer(i))); // vertices is {0, 1, ...}

}

/** Create adjacency lists for each vertex */
private void createAdjacencyLists(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++) {
}

for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
}
}

/** Create adjacency lists for each vertex */
private void createAdjacencyLists(List<Edge> edges, int numberOfVertices) {
// Create a linked list for each vertex
for (int i = 0; i < numberOfVertices; i++) {
}

for (Edge edge : edges) {
}
}

@Override
/** Return the number of vertices in the graph */
public int getSize() {
return vertices.size();
}

@Override
/** Return the vertices in the graph */
public List<V> 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<Integer> 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 */
}

@Override
/** Add an edge to the graph */
public void addEdge(int u, int v) {
}

/** 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<Integer> searchOrder = new ArrayList<Integer>();
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<Integer> searchOrder,
boolean[] isVisited) {
// Store the visited vertex
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
}
}
}

public List<Integer> getPath(int u, int v) {
Tree tree = bfs(u);
ArrayList<Integer> path = new ArrayList<>();

do {
v = tree.parent[v];
} while (v != -1);

Collections.reverse(path);
return path;
}

@Override
/** Starting bfs search from vertex v */
/** To be discussed in Section 27.7 */
public Tree bfs(int v) {
List<Integer> searchOrder = new ArrayList<Integer>();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1

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
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<Integer> searchOrder; // Store the search order

/** Construct a tree with root, parent, and searchOrder */
public Tree(int root, int[] parent, List<Integer> 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<Integer> 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<V> getPath(int index) {
ArrayList<V> path = new ArrayList<V>();

do {
index = parent[index];
} while (index != -1);

return path;
}

/** Print a path from the root to vertex v */
public void printPath(int index) {
List<V> 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();
}
}
}

interface Graph<V> {
/** Return the number of vertices in the graph */
public int getSize();

/** Return the vertices in the graph */
public java.util.List<V> getVertices();

/** Return the object for the specified vertex index */
public V getVertex(int index);

/** Return the index for the specified vertex object */
public int getIndex(V v);

/** Return the neighbors of vertex with the specified index */
public java.util.List<Integer> getNeighbors(int index);

/** Return the degree for a specified vertex */
public int getDegree(int v);

/** Print the edges */
public void printEdges();

/** Clear graph */
public void clear();

/** Add a vertex to the graph */

/** Add an edge to the graph */
public void addEdge(int u, int v);

/** Obtain a depth-first search tree */
public AbstractGraph<V>.Tree dfs(int v);

/** Obtain a breadth-first search tree */
public AbstractGraph<V>.Tree bfs(int v);
}

}