Using the Files \"E02_Graph.java,\" \"E03_AbstractGraph.java\" and \"E04_Unweigh
ID: 3592559 • Letter: U
Question
Using the Files "E02_Graph.java," "E03_AbstractGraph.java" and "E04_UnweightedGraph.java" as a Graph library, write the required code in file "E01_TestGraph.java" to create a visual Graph of what exists in the following image.
The code must be extended in the next class activity.
/***********************************************************************************/
E01_TestGraph.java
/***********************************************************************************/
package chapter28;
import java.awt.Graphics;
import java.util.*;
import javafx.scene.layout.Pane;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.scene.text.Text;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class E01_TestGraph {
public E01_TestGraph() throws Exception{
}
public void main(String[] args, E02_Graph<? extends E05_Displayable> graph) throws Exception {// Main function definition
String[] vertices = {"Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston"};
// Edge array for graph in Figure 28.1
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}
};
E03_AbstractGraph<String> graph1 = new E04_UnweightedGraph<>(vertices, edges);
System.out.println("The number of vertices in graph1: "
+ graph1.getSize());
System.out.println("The vertex with index 1 is "
+ graph1.getVertex(1));
System.out.println("The index for Miami is " +
graph1.getIndex("Miami"));
System.out.println("The edges for graph1:");
graph1.printEdges();
// List of Edge objects for graph in Figure 30.3a
String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
ArrayList<E03_AbstractGraph.Edge> edgeList = new ArrayList<>();
edgeList.add(new E03_AbstractGraph.Edge(0, 2));
edgeList.add(new E03_AbstractGraph.Edge(1, 2));
edgeList.add(new E03_AbstractGraph.Edge(2, 4));
edgeList.add(new E03_AbstractGraph.Edge(3, 4));
// Create a graph with 5 vertices
E02_Graph<String> graph2 = new E04_UnweightedGraph<>(Arrays.asList(names), edgeList);
E02_Graph<String> graph3;
graph3 = new <String>() {};
System.out.println(" The number of vertices in graph2: " + graph2.getSize());
System.out.println("The edges for graph2:");
graph2.printEdges();
E01_TestGraph frame = new E01_TestGraph();// create the object the class
} // main() method end
}
/***********************************************************************************/
End of E01_TestGraph.java
/***********************************************************************************/
/***********************************************************************************/
E02_Graph.java
/***********************************************************************************/
package chapter28;
public interface E02_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 the graph */ public void clear();
/** Add a vertex to the graph */ public boolean addVertex(V vertex);
/** Add an edge to the graph */ public boolean addEdge(int u, int v);
/** Obtain a depth-first search tree */ public E03_AbstractGraph<V>.Tree dfs(int v);
/** Obtain a breadth-first search tree */ public E03_AbstractGraph<V>.Tree bfs(int v);
}
/***********************************************************************************/
End of E02_Graph.java
/***********************************************************************************/
/***********************************************************************************/
E0_.java
/***********************************************************************************/
package chapter28;
import java.util.*;
public abstract class E03_AbstractGraph<V> implements E02_Graph<V> {
protected List<V> vertices = new ArrayList<>(); // Store vertices
protected List<List<Edge>> neighbors = new ArrayList<>(); // Adjacency lists
/** Construct an empty graph */
protected E03_AbstractGraph() {
}
/** Construct a graph from vertices and edges stored in arrays */
protected E03_AbstractGraph(V[] vertices, int[][] edges) {
for (int i = 0; i < vertices.length; i++)
addVertex(vertices[i]);
createAdjacencyLists(edges, vertices.length);
}
/** Construct a graph from vertices and edges stored in List */
protected E03_AbstractGraph(List<V> vertices, List<Edge> edges) {
for (int i = 0; i < vertices.size(); i++)
addVertex(vertices.get(i));
createAdjacencyLists(edges, vertices.size());
}
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
protected E03_AbstractGraph(List<Edge> edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
protected E03_AbstractGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(int[][] edges, int numberOfVertices) {
for (int i = 0; i < edges.length; i++) {
addEdge(edges[i][0], edges[i][1]);
}
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(List<Edge> edges, int numberOfVertices) {
for (Edge edge: edges) {
addEdge(edge.u, 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<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) {
List<Integer> result = new ArrayList<>();
for (Edge e: neighbors.get(index))
result.add(e.v);
return result;
}
@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 (Edge e: neighbors.get(u)) {
System.out.print("(" + getVertex(e.u) + ", " +
getVertex(e.v) + ") ");
}
System.out.println();
}
}
@Override /** Clear the graph */
public void clear() {
vertices.clear();
neighbors.clear();
}
@Override /** Add a vertex to the graph */
public boolean addVertex(V vertex) {
if (!vertices.contains(vertex)) {
vertices.add(vertex);
neighbors.add(new ArrayList<Edge>());
return true;
}
else {
return false;
}
}
/** Add an edge to the graph */
protected boolean addEdge(Edge e) {
if (e.u < 0 || e.u > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.u);
if (e.v < 0 || e.v > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.v);
if (!neighbors.get(e.u).contains(e)) {
neighbors.get(e.u).add(e);
return true;
}
else {
return false;
}
}
@Override /** Add an edge to the graph */
public boolean addEdge(int u, int v) {
return addEdge(new Edge(u, v));
}
/** Edge inner class inside the E03_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;
}
public boolean equals(Object o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
}
}
@Override /** Obtain a DFS tree starting from vertex v */
/** To be discussed in Section 28.6 */
public Tree dfs(int v) {List<Integer> 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 u, int[] parent, List<Integer> searchOrder, boolean[] isVisited) {
// Store the visited vertex
searchOrder.add(u);
isVisited[u] = true; // Vertex v visited
for (Edge e : neighbors.get(u)) {
if (!isVisited[e.v]) {
parent[e.v] = u; // The parent of vertex e.v is u
dfs(e.v, parent, searchOrder, isVisited); // Recursive search
}
}
}
@Override /** Starting bfs search from vertex v */
/** To be discussed in Section 28.7 */
public Tree bfs(int v) {
List<Integer> 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<Integer> 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 (Edge e: neighbors.get(u)) {
if (!isVisited[e.v]) {
queue.offer(e.v); // Enqueue w
parent[e.v] = u; // The parent of w is u
isVisited[e.v] = true; // Mark it visited
}
}
}
return new Tree(v, parent, searchOrder);
}
/** Tree inner class inside the AbstractGraph class */
/** To be discussed in Section 28.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<>();
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<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();
}
}
}
/***********************************************************************************/
End of E03_AbstractGraph.java
/***********************************************************************************/
/***********************************************************************************/
E04_UnweightedGraph.java
/***********************************************************************************/
package chapter28;
import java.util.*;
public class E04_UnweightedGraph<V> extends E03_AbstractGraph<V> {
/** Construct an empty graph */
public E04_UnweightedGraph() {
}
/** Construct a graph from vertices and edges stored in arrays */
public E04_UnweightedGraph(V[] vertices, int[][] edges) {
super(vertices, edges);
}
/** Construct a graph from vertices and edges stored in List */
public E04_UnweightedGraph(List<V> vertices, List<Edge> edges) {
super(vertices, edges);
}
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
public E04_UnweightedGraph(List<Edge> edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
public E04_UnweightedGraph(int[][] edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
}
/***********************************************************************************/
End of E04_UnweightedGraph.java
/***********************************************************************************/
/***********************************************************************************/
E05_Displayable.java
/***********************************************************************************/
package chapter28;
public interface E05_Displayable {
public int getX(); // Get x-coordinate of the vertex
public int getY(); // Get x-coordinate of the vertex
public String getName(); // Get display name of the vertex
}
/***********************************************************************************/
End of E05_Displayable.java
/***********************************************************************************/
/***********************************************************************************/
E06_GraphView.java
/***********************************************************************************/
package chapter28;
import javafx.scene.layout.Pane;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.scene.text.Text;
public class E06_GraphView extends Pane {
private E02_Graph<? extends E05_Displayable> graph;
public E06_GraphView(E02_Graph<? extends E05_Displayable> graph) {
this.graph = graph;
// Draw vertices
java.util.List<? extends E05_Displayable> vertices = graph.getVertices();
for (int i = 0; i < graph.getSize(); i++) {
int x = vertices.get(i).getX();
int y = vertices.get(i).getY();
String name = vertices.get(i).getName();
getChildren().add(new Circle(x, y, 16)); // Display a vertex
getChildren().add(new Text(x - 8, y - 18, name));
}
// Draw edges for pairs of vertices
for (int i = 0; i < graph.getSize(); i++) {
java.util.List<Integer> neighbors = graph.getNeighbors(i);
int x1 = graph.getVertex(i).getX();
int y1 = graph.getVertex(i).getY();
for (int v: neighbors) {
int x2 = graph.getVertex(v).getX();
int y2 = graph.getVertex(v).getY();
// Draw an edge for (i, v)
getChildren().add(new Line(x1, y1, x2, y2));
}
}
}
}
/***********************************************************************************/
End of E06_GraphView.java
/***********************************************************************************/
/***********************************************************************************/
E07_DisplayUSMap.java
/***********************************************************************************/
package chapter28;
import javafx.application.Application;
import javafx.scene.Scene;
import javafx.stage.Stage;
public class E07_DisplayUSMap extends Application {
@Override // Override the start method in the Application class
public void start(Stage primaryStage) {
City[] vertices = {new City("Seattle", 75, 50),
new City("San Francisco", 50, 210),
new City("Los Angeles", 75, 275), new City("Denver", 275, 175),
new City("Kansas City", 400, 245),
new City("Chicago", 450, 100), new City("Boston", 700, 80),
new City("New York", 675, 120), new City("Atlanta", 575, 295),
new City("Miami", 600, 400), new City("Dallas", 408, 325),
new City("Houston", 450, 360) };
// Edge array for graph in Figure 28.1
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}
};
E02_Graph<City> graph = new E04_UnweightedGraph<>(vertices, edges);
// Create a scene and place it in the stage
Scene scene = new Scene(new E06_GraphView(graph), 750, 450);
primaryStage.setTitle("DisplayUSMap"); // Set the stage title
primaryStage.setScene(scene); // Place the scene in the stage
primaryStage.show(); // Display the stage
}
static class City implements E05_Displayable {
private int x, y;
private String name;
City(String name, int x, int y) {
this.name = name;
this.x = x;
this.y = y;
}
@Override
public int getX() {
return x;
}
@Override
public int getY() {
return y;
}
@Override
public String getName() {
return name;
}
}
/**
* The main method is only needed for the IDE with limited
* JavaFX support. Not needed for running from the command line.
*/
public static void main(String[] args) {
launch(args);
}
}
/***********************************************************************************/
End of E07_DisplayUSMap.java
/***********************************************************************************/
/***********************************************************************************/
E09_TestDFS.java
/***********************************************************************************/
package chapter28;
public class E09_TestDFS {
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}
};
E02_Graph<String> graph = new E04_UnweightedGraph<>(vertices, edges);
E03_AbstractGraph<String>.Tree dfsTree =
graph.dfs(graph.getIndex("Chicago"));
java.util.List<Integer> searchOrders = dfsTree.getSearchOrder();
System.out.println(dfsTree.getNumberOfVerticesFound() +
" vertices are searched in this DFS order:");
for (int i = 0; i < searchOrders.size(); i++)
System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
System.out.println();
for (int i = 0; i < searchOrders.size(); i++)
if (dfsTree.getParent(i) != -1)
System.out.println("parent of " + graph.getVertex(i) +
" is " + graph.getVertex(dfsTree.getParent(i)));
}
}
/***********************************************************************************/
End of E09_TestDFS.java
/***********************************************************************************/
/***********************************************************************************/
E12_TestBFS.java
/***********************************************************************************/
package chapter28;
public class E12_TestBFS {
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}
};
E02_Graph<String> graph = new E04_UnweightedGraph<>(vertices, edges);
E03_AbstractGraph<String>.Tree bfsTree =
graph.bfs(graph.getIndex("Chicago"));
java.util.List<Integer> searchOrders = bfsTree.getSearchOrder();
System.out.println(bfsTree.getNumberOfVerticesFound() +
" vertices are searched in this order:");
for (int i = 0; i < searchOrders.size(); i++)
System.out.println(graph.getVertex(searchOrders.get(i)));
for (int i = 0; i < searchOrders.size(); i++)
if (bfsTree.getParent(i) != -1)
System.out.println("parent of " + graph.getVertex(i) +
" is " + graph.getVertex(bfsTree.getParent(i)));
}
}
/***********************************************************************************/
End of E12_TestBFS.java
/***********************************************************************************/
Explanation / Answer
import java.awt.Graphics;
import java.util.*;
import javafx.scene.layout.Pane;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.scene.text.Text;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class E01_TestGraph {
public E01_TestGraph() throws Exception{
}
public void main(String[] args, E02_Graph<? extends E05_Displayable> graph) throws Exception {// Main function definition
String[] vertices = {"Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston"};
// Edge array for graph in Figure 28.1
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}
};
E03_AbstractGraph<String> graph1 = new E04_UnweightedGraph<>(vertices, edges);
System.out.println("The number of vertices in graph1: "
+ graph1.getSize());
System.out.println("The vertex with index 1 is "
+ graph1.getVertex(1));
System.out.println("The index for Miami is " +
graph1.getIndex("Miami"));
System.out.println("The edges for graph1:");
graph1.printEdges();
// List of Edge objects for graph in Figure 30.3a
String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
ArrayList<E03_AbstractGraph.Edge> edgeList = new ArrayList<>();
edgeList.add(new E03_AbstractGraph.Edge(0, 2));
edgeList.add(new E03_AbstractGraph.Edge(1, 2));
edgeList.add(new E03_AbstractGraph.Edge(2, 4));
edgeList.add(new E03_AbstractGraph.Edge(3, 4));
// Create a graph with 5 vertices
E02_Graph<String> graph2 = new E04_UnweightedGraph<>(Arrays.asList(names), edgeList);
E02_Graph<String> graph3;
graph3 = new <String>() {};
System.out.println(" The number of vertices in graph2: " + graph2.getSize());
System.out.println("The edges for graph2:");
graph2.printEdges();
E01_TestGraph frame = new E01_TestGraph();// create the object the class
} // main() method end
}
/***********************************************************************************/
End of E01_TestGraph.java
/***********************************************************************************/
/***********************************************************************************/
E02_Graph.java
/***********************************************************************************/
package chapter28;
public interface E02_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 the graph */ public void clear();
/** Add a vertex to the graph */ public boolean addVertex(V vertex);
/** Add an edge to the graph */ public boolean addEdge(int u, int v);
/** Obtain a depth-first search tree */ public E03_AbstractGraph<V>.Tree dfs(int v);
/** Obtain a breadth-first search tree */ public E03_AbstractGraph<V>.Tree bfs(int v);
}
/***********************************************************************************/
End of E02_Graph.java
/***********************************************************************************/
/***********************************************************************************/
E0_.java
/***********************************************************************************/
package chapter28;
import java.util.*;
public abstract class E03_AbstractGraph<V> implements E02_Graph<V> {
protected List<V> vertices = new ArrayList<>(); // Store vertices
protected List<List<Edge>> neighbors = new ArrayList<>(); // Adjacency lists
/** Construct an empty graph */
protected E03_AbstractGraph() {
}
/** Construct a graph from vertices and edges stored in arrays */
protected E03_AbstractGraph(V[] vertices, int[][] edges) {
for (int i = 0; i < vertices.length; i++)
addVertex(vertices[i]);
createAdjacencyLists(edges, vertices.length);
}
/** Construct a graph from vertices and edges stored in List */
protected E03_AbstractGraph(List<V> vertices, List<Edge> edges) {
for (int i = 0; i < vertices.size(); i++)
addVertex(vertices.get(i));
createAdjacencyLists(edges, vertices.size());
}
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
protected E03_AbstractGraph(List<Edge> edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
protected E03_AbstractGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(int[][] edges, int numberOfVertices) {
for (int i = 0; i < edges.length; i++) {
addEdge(edges[i][0], edges[i][1]);
}
}
/** Create adjacency lists for each vertex */
private void createAdjacencyLists(List<Edge> edges, int numberOfVertices) {
for (Edge edge: edges) {
addEdge(edge.u, 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<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) {
List<Integer> result = new ArrayList<>();
for (Edge e: neighbors.get(index))
result.add(e.v);
return result;
}
@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 (Edge e: neighbors.get(u)) {
System.out.print("(" + getVertex(e.u) + ", " +
getVertex(e.v) + ") ");
}
System.out.println();
}
}
@Override /** Clear the graph */
public void clear() {
vertices.clear();
neighbors.clear();
}
@Override /** Add a vertex to the graph */
public boolean addVertex(V vertex) {
if (!vertices.contains(vertex)) {
vertices.add(vertex);
neighbors.add(new ArrayList<Edge>());
return true;
}
else {
return false;
}
}
/** Add an edge to the graph */
protected boolean addEdge(Edge e) {
if (e.u < 0 || e.u > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.u);
if (e.v < 0 || e.v > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.v);
if (!neighbors.get(e.u).contains(e)) {
neighbors.get(e.u).add(e);
return true;
}
else {
return false;
}
}
@Override /** Add an edge to the graph */
public boolean addEdge(int u, int v) {
return addEdge(new Edge(u, v));
}
/** Edge inner class inside the E03_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;
}
public boolean equals(Object o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
}
}
@Override /** Obtain a DFS tree starting from vertex v */
/** To be discussed in Section 28.6 */
public Tree dfs(int v) {List<Integer> 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 u, int[] parent, List<Integer> searchOrder, boolean[] isVisited) {
// Store the visited vertex
searchOrder.add(u);
isVisited[u] = true; // Vertex v visited
for (Edge e : neighbors.get(u)) {
if (!isVisited[e.v]) {
parent[e.v] = u; // The parent of vertex e.v is u
dfs(e.v, parent, searchOrder, isVisited); // Recursive search
}
}
}
@Override /** Starting bfs search from vertex v */
/** To be discussed in Section 28.7 */
public Tree bfs(int v) {
List<Integer> 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<Integer> 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 (Edge e: neighbors.get(u)) {
if (!isVisited[e.v]) {
queue.offer(e.v); // Enqueue w
parent[e.v] = u; // The parent of w is u
isVisited[e.v] = true; // Mark it visited
}
}
}
return new Tree(v, parent, searchOrder);
}
/** Tree inner class inside the AbstractGraph class */
/** To be discussed in Section 28.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<>();
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<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();
}
}
}
/***********************************************************************************/
End of E03_AbstractGraph.java
/***********************************************************************************/
/***********************************************************************************/
E04_UnweightedGraph.java
/***********************************************************************************/
package chapter28;
import java.util.*;
public class E04_UnweightedGraph<V> extends E03_AbstractGraph<V> {
/** Construct an empty graph */
public E04_UnweightedGraph() {
}
/** Construct a graph from vertices and edges stored in arrays */
public E04_UnweightedGraph(V[] vertices, int[][] edges) {
super(vertices, edges);
}
/** Construct a graph from vertices and edges stored in List */
public E04_UnweightedGraph(List<V> vertices, List<Edge> edges) {
super(vertices, edges);
}
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
public E04_UnweightedGraph(List<Edge> edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
public E04_UnweightedGraph(int[][] edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
}
/***********************************************************************************/
End of E04_UnweightedGraph.java
/***********************************************************************************/
/***********************************************************************************/
E05_Displayable.java
/***********************************************************************************/
package chapter28;
public interface E05_Displayable {
public int getX(); // Get x-coordinate of the vertex
public int getY(); // Get x-coordinate of the vertex
public String getName(); // Get display name of the vertex
}
/***********************************************************************************/
End of E05_Displayable.java
/***********************************************************************************/
/***********************************************************************************/
E06_GraphView.java
/***********************************************************************************/
package chapter28;
import javafx.scene.layout.Pane;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.scene.text.Text;
public class E06_GraphView extends Pane {
private E02_Graph<? extends E05_Displayable> graph;
public E06_GraphView(E02_Graph<? extends E05_Displayable> graph) {
this.graph = graph;
// Draw vertices
java.util.List<? extends E05_Displayable> vertices = graph.getVertices();
for (int i = 0; i < graph.getSize(); i++) {
int x = vertices.get(i).getX();
int y = vertices.get(i).getY();
String name = vertices.get(i).getName();
getChildren().add(new Circle(x, y, 16)); // Display a vertex
getChildren().add(new Text(x - 8, y - 18, name));
}
// Draw edges for pairs of vertices
for (int i = 0; i < graph.getSize(); i++) {
java.util.List<Integer> neighbors = graph.getNeighbors(i);
int x1 = graph.getVertex(i).getX();
int y1 = graph.getVertex(i).getY();
for (int v: neighbors) {
int x2 = graph.getVertex(v).getX();
int y2 = graph.getVertex(v).getY();
// Draw an edge for (i, v)
getChildren().add(new Line(x1, y1, x2, y2));
}
}
}
}
/***********************************************************************************/
End of E06_GraphView.java
/***********************************************************************************/
/***********************************************************************************/
E07_DisplayUSMap.java
/***********************************************************************************/
package chapter28;
import javafx.application.Application;
import javafx.scene.Scene;
import javafx.stage.Stage;
public class E07_DisplayUSMap extends Application {
@Override // Override the start method in the Application class
public void start(Stage primaryStage) {
City[] vertices = {new City("Seattle", 75, 50),
new City("San Francisco", 50, 210),
new City("Los Angeles", 75, 275), new City("Denver", 275, 175),
new City("Kansas City", 400, 245),
new City("Chicago", 450, 100), new City("Boston", 700, 80),
new City("New York", 675, 120), new City("Atlanta", 575, 295),
new City("Miami", 600, 400), new City("Dallas", 408, 325),
new City("Houston", 450, 360) };
// Edge array for graph in Figure 28.1
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}
};
E02_Graph<City> graph = new E04_UnweightedGraph<>(vertices, edges);
// Create a scene and place it in the stage
Scene scene = new Scene(new E06_GraphView(graph), 750, 450);
primaryStage.setTitle("DisplayUSMap"); // Set the stage title
primaryStage.setScene(scene); // Place the scene in the stage
primaryStage.show(); // Display the stage
}
static class City implements E05_Displayable {
private int x, y;
private String name;
City(String name, int x, int y) {
this.name = name;
this.x = x;
this.y = y;
}
@Override
public int getX() {
return x;
}
@Override
public int getY() {
return y;
}
@Override
public String getName() {
return name;
}
}
/**
* The main method is only needed for the IDE with limited
* JavaFX support. Not needed for running from the command line.
*/
public static void main(String[] args) {
launch(args);
}
}
/***********************************************************************************/
End of E07_DisplayUSMap.java
/***********************************************************************************/
/***********************************************************************************/
E09_TestDFS.java
/***********************************************************************************/
package chapter28;
public class E09_TestDFS {
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}
};
E02_Graph<String> graph = new E04_UnweightedGraph<>(vertices, edges);
E03_AbstractGraph<String>.Tree dfsTree =
graph.dfs(graph.getIndex("Chicago"));
java.util.List<Integer> searchOrders = dfsTree.getSearchOrder();
System.out.println(dfsTree.getNumberOfVerticesFound() +
" vertices are searched in this DFS order:");
for (int i = 0; i < searchOrders.size(); i++)
System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
System.out.println();
for (int i = 0; i < searchOrders.size(); i++)
if (dfsTree.getParent(i) != -1)
System.out.println("parent of " + graph.getVertex(i) +
" is " + graph.getVertex(dfsTree.getParent(i)));
}
}
/***********************************************************************************/
End of E09_TestDFS.java
/***********************************************************************************/
/***********************************************************************************/
E12_TestBFS.java
/***********************************************************************************/
package chapter28;
public class E12_TestBFS {
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}
};
E02_Graph<String> graph = new E04_UnweightedGraph<>(vertices, edges);
E03_AbstractGraph<String>.Tree bfsTree =
graph.bfs(graph.getIndex("Chicago"));
java.util.List<Integer> searchOrders = bfsTree.getSearchOrder();
System.out.println(bfsTree.getNumberOfVerticesFound() +
" vertices are searched in this order:");
for (int i = 0; i < searchOrders.size(); i++)
System.out.println(graph.getVertex(searchOrders.get(i)));
for (int i = 0; i < searchOrders.size(); i++)
if (bfsTree.getParent(i) != -1)
System.out.println("parent of " + graph.getVertex(i) +
" is " + graph.getVertex(bfsTree.getParent(i)));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.