In this lab you will add additional methods to theUnweightedGraph class from lecture. This graph is directed andunweighted.
In order to create an UnweightedGraph object, write a methodthat reads in Integer graph data from a file and sets thisUnweightedGraph instance according to the data in the file. Themethod signature must be
public static UnweightedGraph<Integer>graphFromFile(String fileName)
throws FileNotFoundException
Here are examples of two files for their correspondinggraphs:
To the UnweightedGraph class, implement the followingmethods:
Files you will need:
//////Edge.java
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) {return originVertex == ((Edge)o).originVertex &&destinationVertex == ((Edge)o).destinationVertex;}
//Graph.java
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. If a graph isundirected, you should invoke addEdge(u, v) andaddEdge(v, u) to add an edge between u and v. */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 */public default boolean remove(V v) {return true; // Implementation left as an exercise}/** Remove an edge (u, v) from the graph */public default boolean remove(int u, int v) {return true; // Implementation left as an exercise}/** Obtain a depth-first search tree */public UnweightedGraph<V>.SearchTreegetDepthFirstSearchTree(int v);/** Obtain a breadth-first search tree */public UnweightedGraph<V>.SearchTreegetBreadthFirstSearchTree(int v);}
/////UnweightedGraph.java
- Graph Implementation In This Lab You Will Add Additional Methods To The Unweightedgraph Class From Lecture This Graph I 1 (55.98 KiB) Viewed 17 times
60 1 2 31 0 32 0 33 0 1 24 55 4
import java.io.FileNotFoundException; import java.util.*; public class UnweightedGraph<V> implements Graph<V> { private List<V> vertices = new ArrayList<>(); // Store vertices private List<List<Edge>> neighbors = new ArrayList<>(); // Adjacency lists /** Construct an empty graph */ public UnweightedGraph() { } /** 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); 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 */ public UnweightedGraph (List<Edge> edges, int numberOfVertices) { for (int i = 0; i < numberOfVertices; i++) addVertex ((V) (Integer.valueOf(i))); // vertices are {0, 1, ...} createAdjacencyLists (edges, numberOfVertices);
/** Construct a graph from integer vertices 0, 1, and edge array */ public UnweightedGraph(int[][] edges, int numberOfVertices) { for (int i = 0; i < numberOfVertices; i++) } /** Create adjacency lists for each vertex */ private void createAdjacencyLists ( } createAdjacencyLists (edges, numberOfVertices); addVertex ((V) (Integer.valueOf(i))); // vertices are {0, 1, ...} } int[][] edges, int numberOfVertices) { for (int i = 0; i < edges.length; i++) { addEdge (edges[0], edges [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 vertices in the graph */ public List<V> getVertices() { return vertices; } @Override /** Return the object for the specified vertex */ public V getVertex(int 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 vertices.get(index); } List<Integer> result = new ArrayList<>(); for (Edge e: neighbors.get(index)) @Override /** Return the degree for a specified vertex */ public int getDegree(int v) { } } result.add(e.getDestinationVertex()); return result; @Override /** Print the edges */ public void printEdges() { return neighbors.get(v).size(); 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); } } else { } } @Override /** Add an edge to the graph */ public boolean addEdge (Edge e) { neighbors.add(new ArrayList<Edge>()); return true; return false; if (e.getOriginVertex() < 0 || e.getOriginVertex() › getSize() - 1) } else { if (e.getDestinationVertex() < 0 || e.getDestinationVertex() > getSize() - 1) } throw new IllegalArgumentException("No such index: " + e.getOriginVertex()); if (!neighbors.get(e.getOriginVertex()). contains(e)) { neighbors.get(e.getOriginVertex()) .add(e); throw new IllegalArgumentException("No such index: " + e.getDestinationVertex()); return true; 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 Search Tree getDepthFirstSearchTree(int startingVertex) { List<Integer> searchOrder = new ArrayList<>(); int[] parent = new int[vertices.size()]; for (int i = 0; i < parent.length; i++) parent = -1; // Initialize parent to -1 // Mark visited vertices boolean[] isVisited = new boolean [vertices.size()]; // Recursively search dfs (startingVertex, parent, searchOrder, isVisited);
} /** 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 } // Return a search tree return new Search Tree (startingVertex, parent, searchOrder); } 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 getBreadthFirstSearchTree(int vertex) { List<Integer> searchOrder = new ArrayList<>(); int[] parent = new int[vertices.size()]; for (int i = 0; i < parent.length; i++) parent = -1; // Initialize parent to -1 // list used as a queue java.util.LinkedList<Integer> queue = new java.util.LinkedList<>(); boolean[] isVisited = new boolean [vertices.size()]; queue.offer (vertex); // Enqueue vertex isVisited [vertex] = true; // Mark it visited while (!queue.isEmpty()) { int u = queue.poll(); searchOrder.add(u); for (Edge e: neighbors.get(u)) { // Note that e.u is u if (!isVisited[e.getDestinationVertex()]) { } // Dequeue to u } // u searched queue.offer (e.getDestinationVertex()); parent [e.getDestinationVertex()] u; isVisited[e.getDestinationVertex()] = true; // Mark w visited } return new Search Tree (vertex, parent, searchOrder); // Enqueue w // The parent of w is u
/** Search Tree inner class inside the UnweightedGraph class */ public class Search 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 Search 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 getNumberOfVertices Found() { 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) + ": "); } /** Print the whole tree */ public void printTree() { for (int i = path.size() - 1; i >= 0; i--) System.out.print(path.get(i) + " "); * @return System.out.println("Root is: " + vertices.get(root)); System.out.print("Edges: "); for (int i = 0; i < parent.length; i++) { if (parent != -1) { } } System.out.println(); // Display an edge End implementation of inner SearchTree class */ /* Lab methods to be implemented */ System.out.print("(" + vertices.get(parent) + vertices.get(i) + ") "); /** * Reads the input file to extract the graph data * @param filename The String name of the file * @return UnweightedGraph of data from the File * @throws FileNotFoundException, Number FormatException */ public static UnweightedGraph<Integer> graphFromFile(String fileName) throws FileNotFoundException { return null; public boolean isComplete() { return true; true if this graph is complete } /** * @param origin the origin vertex A------- Jud.
public static UnweightedGraph<Integer> graphFromFile(String fileName) throws FileNotFoundException { return null; } /** * @return */ public boolean isComplete() { return true; } /** * @return } **/ public boolean areAdjacent(int origin, int destination) { return true; @param origin the origin vertex @param destination } true if this graph is complete **/ * @return */ public boolean isConnected() { return true; the destination vertex true if the destination vertex is adjacent to the origin vertex; false otherwise * @return true if this graph is connected true if this graph has a cycle public boolean hasCycle() { return true; * @param origin the origin vertex * @param destination * @return the destination vertex A List containing the shortest path from the origin vertex to the destination vertex public List<V> getShortestPath(int origin, int destination) { return null; }