In this project, you'll begin with starter code for a Graph interface, an Edge class, and a class that represents an unweighted graph, UnweightedGraph.java.
You will extend the UnweightedGraph class by implementing a class called MyCustomGraph. You must override all of the constructors in the UnweightedGraph class and implement the following methods:
1. Write a method that reads in graph data from a file and sets this MyCustomGraph instance according to the data in the file. The method signature must be public MyCustomGraph< V > readFile(String fileName)
Here are examples of two files for their corresponding graphs: see image.
2. Add the method public boolean isComplete() that returns true if this graph is complete
3. Add the method public boolean areAdjacent(V v1, V v2) that returns true if v1 is adjacent to v2
4. Add a method called isConnected that returns true if this graph is connected and false otherwise. The header for this method is public boolean isConnected(). Hint: Call the printEdges() to display all edges, and then call dfs() to obtain an instance tree of UnweightedGraph.SearchTree. If tree.getNumberOfVerticesFound() is the same as the number of vertices in the graph, the graph is connected.
5.Add a method called getShortestPath for finding the shortest path between two vertices using a breadth-first search with the following header: public List< V > getShortestPath(V begin, V end)
6. Add a method called hasCycle() for determining whether there is a cycle in the graph with the following header: public boolean hasCycle()
Edge.java
package cmsc256;
public class Edge {
private int originVertex;
private int destinationVertex;
public Edge(int origin, int destination) {
this.originVertex = origin;
this.destinationVertex = destination;
}
public int getOriginVertex() {
return originVertex;
}
public void setOriginVertex(int originVertex) {
this.originVertex = originVertex;
}
public int getDestinationVertex() {
return destinationVertex;
}
public void setDestinationVertex(int destinationVertex) {
this.destinationVertex = destinationVertex;
}
public boolean equals(Object o) {
if(o == null || !(o instanceof Edge))
return false;
return originVertex == ((Edge)o).getOriginVertex()
&& destinationVertex == ((Edge)o).getDestinationVertex();
}
}
Graph.java
package cmsc256;
public 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 the graph */
public void clear();
/** Add a vertex to the graph */
public boolean addVertex(V vertex);
/** Add an edge (u, v) to the graph */
public boolean addEdge(int u, int v);
/** Add an edge to the graph */
public boolean addEdge(Edge e);
/** Remove a vertex v from the graph, return true if successful */
public boolean remove(V v);
/** Remove an edge (u, v) from the graph */
public boolean remove(int u, int v);
/** Obtain a depth-first search tree */
public UnweightedGraph< V >.SearchTree dfs(int v);
/** Obtain a breadth-first search tree */
public UnweightedGraph< V >.SearchTree bfs(int v);
}
test2.txt
6
0 1 2
1 0 3
2 0 3 4
3 1 2 4 5
4 2 3 5
5 3 4
test3.txt
6
0 1 2 3
1 0 3
2 0 3
3 0 1 2
4 5
5 4
UnweightedGraph.java
package cmsc256;
import java.util.*;
public class UnweightedGraph< V > implements Graph< V > {
protected List< V > vertices = new ArrayList< >(); // Store vertices
protected List< List< Edge > > neighbors = new ArrayList< >(); // Adjacency lists
/** Construct an empty graph */
public UnweightedGraph() {
super();
}
/** Construct a graph from vertices and edges stored in arrays */
public UnweightedGraph(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 */
public UnweightedGraph(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 */
@SuppressWarnings("unchecked")
public UnweightedGraph(List< Edge > edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(Integer.valueOf(i))); // vertices is {0, 1, ...}
createAdjacencyLists(edges, numberOfVertices);
}
/** Construct a graph from integer vertices 0, 1, and edge array */
@SuppressWarnings("unchecked")
public UnweightedGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(Integer.valueOf(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.getOriginVertex(), edge.getDestinationVertex());
}
}
@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.getDestinationVertex());
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.getOriginVertex()) + ", " +
getVertex(e.getDestinationVertex()) + ") ");
}
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;
}
}
@Override /** Add an edge to the graph */
public boolean addEdge(Edge e) {
if (e.getOriginVertex() < 0 || e.getOriginVertex() > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.getOriginVertex());
if (e.getDestinationVertex() < 0 || e.getDestinationVertex() > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.getDestinationVertex());
if (!neighbors.get(e.getOriginVertex()).contains(e)) {
neighbors.get(e.getOriginVertex()).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));
}
@Override /** Obtain a DFS tree starting from vertex v */
public SearchTree 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 SearchTree(v, parent, searchOrder);
}
/** Recursive method for DFS search */
private void dfs(int v, int[] parent, List< Integer > searchOrder,
boolean[] isVisited) {
// Store the visited vertex
searchOrder.add(v);
isVisited[v] = true; // Vertex v visited
for (Edge e : neighbors.get(v)) { // Note that e.u is v
if (!isVisited[e.getDestinationVertex()]) { // e.v is w in Listing 28.8
parent[e.getDestinationVertex()] = v; // The parent of w is v
dfs(e.getDestinationVertex(), parent, searchOrder, isVisited); // Recursive search
}
}
}
@Override /** Starting bfs search from vertex v */
public SearchTree 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)) { // Note that e.u is u
if (!isVisited[e.getDestinationVertex()]) { // e.v is w in Listing 28.11
queue.offer(e.getDestinationVertex()); // Enqueue w
parent[e.getDestinationVertex()] = u; // The parent of w is u
isVisited[e.getDestinationVertex()] = true; // Mark w visited
}
}
}
return new SearchTree(v, parent, searchOrder);
}
/** Tree inner class inside the AbstractGraph class */
public class SearchTree {
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 SearchTree(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();
}
}
@Override /** Remove vertex v and return true if successful */
public boolean remove(V v) {
throw new java.lang.UnsupportedOperationException();
}
@Override /** Remove edge (u, v) and return true if successful */
public boolean remove(int u, int v) {
throw new java.lang.UnsupportedOperationException();
}
}