Write a Java class definition for an abstract data type called Graph that models

Question

Write a Java class definition for an abstract data type called Graph that models an undirected graph. Some implementation details:

- Loops are allowed but multiple edges are not allowed.

- Vertices are labeled by number from 0 to n-1 where n is the number of vertices in the

graph.

Implement the following public member functions.

- A constructor that creates an empty graph.

- void load(char *filename): Creates the graph using the file passed into the function. The format of the file is described later. You may assume load is only called once for a graph. You may modify the argument type of this function if you use Java.

- void display(): Displays the graph's adjacency matrix to the screen.
- void displayDFS(int vertex): Displays the result of a depth first search starting at the provided vertex. When you have a choice between selecting two vertices, pick the vertex with the lower number.

- void displayBFS(int vertex): Displays the result of a breadth first search starting at the provided vertex. When you have a choice between selecting two vertices, pick the vertex with the lower number. You are permitted to add extra member functions you feel are helpful. DFS must be implemented using recursion. Other forms of using STL are not permitted.

Input File Format

The function load is responsible for reading in a file corresponding to a graph. The format is as follows:

- The first line contains a single integer indicating how many vertices are present in the
graph. You may make no assumptions on how many vertices in the graph

Explanation / Answer

import java.io.FileWriter; import java.io.IOException; import java.util.*; public class Graph { // from name to vertex, using HashMap private HashMap myVertices; // Adjacent list is a set of vertices represented by a search tree: TreeSet // from vertex to adjacent list, using HashMap private HashMap myAdjList; private int myNumVertices; private int myNumEdges; // EMPTY_SET is a constant: private static final TreeSet EMPTY_SET = new TreeSet(); public static final int INFINITY = Integer.MAX_VALUE; // Construct an empty Graph public Graph() { myAdjList = new HashMap(); myVertices = new HashMap(); myNumVertices = myNumEdges = 0; } // Add a new vertex name with no neighbors (if vertex does not yet exist) public Vertex addVertex(String name) { Vertex v; v = myVertices.get(name); if (v == null) { v = new Vertex(name); myVertices.put(name, v); myAdjList.put(v, new TreeSet()); myNumVertices += 1; } return v; } /** * Returns the Vertex matching v * @param name a String name of a Vertex that may be in * this Graph * @return the Vertex with a name that matches v or null * if no such Vertex exists in this Graph */ public Vertex getVertex(String name) { return myVertices.get(name); } /** * Returns true iff v is in this Graph, false otherwise * @param name a String name of a Vertex that may be in * this Graph * @return true iff v is in this Graph */ public boolean hasVertex(String name) { return myVertices.containsKey(name); } /** * Is from-to, an edge in this Graph. The graph is * undirected so the order of from and to does not * matter. * @param from the name of the first Vertex * @param to the name of the second Vertex * @return true iff from-to exists in this Graph */ public boolean hasEdge(String from, String to) { Vertex v1 = myVertices.get(from); Vertex v2 = myVertices.get(to); if (v1 == null || v2 == null) return false; return myAdjList.get(v1).contains(v2); } /** * Add to to from's set of neighbors, and add from to to's * set of neighbors. Does not add an edge if another edge * already exists * @param from the name of the first Vertex * @param to the name of the second Vertex */ public void addEdge(String from, String to) { Vertex v, w; if (hasEdge(from, to)) return; // no duplicate edges myNumEdges += 1; if ((v = getVertex(from)) == null) v = addVertex(from); if ((w = getVertex(to)) == null) w = addVertex(to); myAdjList.get(v).add(w); myAdjList.get(w).add(v); // undirected graph only } /** * Return an iterator over the neighbors of Vertex named v * @param name the String name of a Vertex * @return an Iterator over Vertices that are adjacent * to the Vertex named v, empty set if v is not in graph */ public Iterable adjacentTo(String name) { Vertex v = getVertex(name); if (v == null) return EMPTY_SET; return myAdjList.get(getVertex(name)); } /** * Return an iterator over the neighbors of Vertex v * @param v the Vertex * @return an Iterator over Vertices that are adjacent * to the Vertex v, empty set if v is not in graph */ public Iterable adjacentTo(Vertex v ) { if (!myAdjList.containsKey(v)) return EMPTY_SET; return myAdjList.get(v); } /** * Returns an Iterator over all Vertices in this Graph * @return an Iterator over all Vertices in this Graph */ public Iterable getVertices() { return myVertices.values(); } public int numVertices() { return myNumVertices; } public int numEdges(){ return myNumEdges; } /* * Returns adjacency-list representation of graph */ public String toString() { String s = ""; for (Vertex v : myVertices.values()) { s += v + ": "; for (Vertex w : myAdjList.get(v)) { s += w + " "; } s += " "; } return s; } private String escapedVersion(String s) { return "'"+s+"'"; } public void outputGDF(String fileName) { HashMap idToName = new HashMap(); try { FileWriter out = new FileWriter(fileName); int count = 0; out.write("nodedef> name,label,distance "); // write vertices for (Vertex v: myVertices.values()) { String id = "v"+ count++; idToName.put(v, id); out.write(id + ", " + escapedVersion(v.name)); out.write(", "+v.distance+" "); } out.write("edgedef> node1,node2,color "); // write edges for (Vertex v : myVertices.values()) for (Vertex w : myAdjList.get(v)) if (v.compareTo(w) < 0) { out.write(idToName.get(v)+", "+ idToName.get(w) + ", "); if (v.predecessor == w || w.predecessor == v) out.write("blue"); else out.write("gray"); out.write(" "); } out.close(); } catch (IOException e) { e.printStackTrace(); } } private void initSearch() { for (Vertex v : this.getVertices()) { v.processed = v.discovered = false; v.predecessor = null; v.distance = INFINITY; } } public void BFS(Vertex s) { this.initSearch(); s.distance = 0; s.discovered = true; Queue q = new LinkedList(); q.add(s); while (!q.isEmpty()) { Vertex v = q.remove(); System.out.println("visit " + v); for (Vertex w : this.adjacentTo(v)) if (!w.discovered) { w.distance = v.distance+1; w.discovered = true; w.predecessor = v; q.add(w); } v.processed = true; } } public void DFS(Vertex s) { this.initSearch(); s.distance = 0; s.discovered = true; recDFS(s); } public void recDFS(Vertex v) { System.out.println("visit " + v); for (Vertex w : this.adjacentTo(v)) if (!w.discovered) { w.distance = v.distance+1; w.discovered = true; w.predecessor = v; recDFS(w); } v.processed = true; } public void DFS2(Vertex s) { this.initSearch(); s.distance = 0; s.discovered = true; Stack q = new Stack(); q.push(s); while (!q.isEmpty()) { Vertex v = q.pop(); for (Vertex w : this.adjacentTo(v)) { if (!w.processed) { w.distance = v.distance+1; w.discovered = true; w.predecessor = v; q.add(w); } } v.processed = true; } } public static void main(String[] args) { Graph G = new Graph(); G.addEdge("A", "B"); G.addEdge("A", "C"); G.addEdge("B", "C"); G.addEdge("C", "D"); G.addEdge("D", "E"); G.addEdge("D", "G"); G.addEdge("E", "G"); G.addVertex("H"); // print out graph System.out.println(G); // G.BFS(G.getVertex("A")); G.DFS(G.getVertex("A")); // print out graph again by iterating over vertices and edges for (Vertex v : G.getVertices()) { System.out.print(v + ": "); for (Vertex w : G.adjacentTo(v.name)) { System.out.print(w + " "); } System.out.println(); } G.outputGDF("graph.txt"); } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.