Can someone please help me with this. Create a new project called Homework14. Th
ID: 664092 • Letter: C
Question
Can someone please help me with this.
Create a new project called Homework14.
The following code shows a simple Java implementation of a graph class (parts of the code is missing, you are to complete it). ======
Graph.java
/**
* class Graph
*
*/
public class Graph
{
protected HashMap adjacencyMap;
/**
* Initialize this Graph object to be empty.
*/
public Graph()
{
adjacencyMap = new HashMap();
}
/**
* Determines if this Graph contains no vertices.
*
* @return true - if this Graph contains no vertices.
*/
public boolean isEmpty()
{
return adjacencyMap.isEmpty();
}
/**
* Determines the number of vertices in this Graph.
*
* @return the number of vertices.
*/
public int size()
{
return adjacencyMap.size();
}
/**
* Returns the number of edges in this Graph object.
*
* @return the number of edges.
*/
public int getEdgeCount()
{
int count = 0;
for (int i=0;i<adjacencyMap.CAPACITY;i++)
{
if (adjacencyMap.keys[i] != null)
{
LinkedList edges = (LinkedList)
adjacencyMap.get(adjacencyMap.keys[i]);
count += edges.size();
}
}
return count;
}
/**
* Adds a specified object as a vertex
*
* @param vertex - the specified object
* @return true - if object was added by this call
*/
public boolean addVertex (Object vertex)
{
if (adjacencyMap.containsKey(vertex))
return false;
adjacencyMap.put (vertex, new LinkedList());
return true;
}
/**
* Adds an edge, and vertices if not already present
*
* @param v1 - the beginning vertex object of the edge
* @param v2 - the ending vertex object of the edge
* @return true - if the edge was added by this call
*/
public boolean addEdge (Object v1, Object v2)
{
======
======
}
}
Using an Graph
Controller Class: The following class GraphTester.java shows how to use a Graph to hold String objects. Calls to Graph operations are shown in bold.
GraphTester.java
public class GraphTester {
private Graph graph;
public GraphTester(Graph graph)
{
this.graph = graph;
}
/**
* adding edges
*/
public void addingEdge(String str1, String str2)
{
graph.addEdge(str1, str2);
System.out.println("Added new edge");
}
/**
* return the number of vertices
*/
public int returnNumberofVertices()
{
int count = graph.size();
System.out.println("Number of vertices is: " + count);
return (count);
}
/**
* return the number of edges
*/
public int returnNumberofEdges()
{
int count = graph.getEdgeCount();
System.out.println("Number of edges is: " + count);
return (count);
}
}
Looking at a Graph
Create a Driver.java class (it contains main).
2. Create a new instance of Graph called graph1.
3. Create a new instance of Controller Class called GraphTester called gt and select your Graph instance graph1 in the object bench as the parameter in the constructor. This means that you will be testing the Graph you created in the previous step.
4. Call the addingEdge method of GraphTester to add the following edges (this should construct a directed graph equivalent to the example used earlier):
addingEdge("Anchorage", "Billings");
addingEdge("Anchorage", "Corvallis");
addingEdge("Anchorage", "Edmonton");
addingEdge("Billings", "Denver");
addingEdge("Billings", "Edmonton");
addingEdge("Corvallis", "Denver");
addingEdge("Denver", "Edmonton");
addingEdge("Denver", "Flagstaff");
addingEdge("Flagstaff", "Denver");
addingEdge("Flagstaff", "Houston");
addingEdge("Grand Rapids", "Houston");
5. Call the returnNumberofVertices and returnNumberofEdges methods of GraphTester and inspect the adjacencyMap. Inspect the keys array. Check that “Anchorage” is included. Note its position.
6. Inspect the values array. You should see an array which includes some object references.
Explanation / Answer
Here is the code for the above problem:
Driver.java :
public class Driver {
public static void main(String[] args) {
Graph graph1 = new Graph();
GraphTester gt = new GraphTester(graph1);
gt.addingEdge("Anchorage", "Billings");
gt.addingEdge("Anchorage", "Corvallis");
gt.addingEdge("Anchorage", "Edmonton");
gt.addingEdge("Billings", "Denver");
gt.addingEdge("Billings", "Edmonton");
gt.addingEdge("Corvallis", "Denver");
gt.addingEdge("Denver", "Edmonton");
gt.addingEdge("Denver", "Flagstaff");
gt.addingEdge("Flagstaff", "Denver");
gt.addingEdge("Flagstaff", "Houston");
gt.addingEdge("Grand Rapids", "Houston");
System.out.println("No Of Edges: " + gt.returnNumberofEdges()
+ "No Of Vertices:" + gt.returnNumberofVertices());
}
}
Graph.java:
import java.util.HashMap;
import java.util.LinkedList;
/**
* class Graph
*
*/
public class Graph {
protected HashMap<String, LinkedList<String>> adjacencyMap;
/**
* Initialize this Graph object to be empty.
*/
public Graph() {
adjacencyMap = new HashMap<String, LinkedList<String>>();
}
/**
* Determines if this Graph contains no vertices.
*
* @return true - if this Graph contains no vertices.
*/
public boolean isEmpty() {
return adjacencyMap.isEmpty();
}
/**
* Determines the number of vertices in this Graph.
*
* @return the number of vertices.
*/
public int size() {
return adjacencyMap.size();
}
/**
* Returns the number of edges in this Graph object.
*
* @return the number of edges.
*/
public int getEdgeCount() {
int count = 0;
for (String key : adjacencyMap.keySet()) {
if (key != null) {
LinkedList<String> edges = (LinkedList<String>) adjacencyMap
.get(key);
count += edges.size();
}
}
return count;
}
/**
* Adds a specified object as a vertex
*
* @param vertex
* - the specified object
* @return true - if object was added by this call
*/
public boolean addVertex(String vertex) {
if (adjacencyMap.containsKey(vertex))
return false;
adjacencyMap.put(vertex, new LinkedList<String>());
return true;
}
/**
* Adds an edge, and vertices if not already present
*
* @param v1
* - the beginning vertex object of the edge
* @param v2
* - the ending vertex object of the edge
* @return true - if the edge was added by this call
*/
public boolean addEdge(String v1, String v2) {
try {
if (!adjacencyMap.containsKey(v1))
adjacencyMap.put(v1, new LinkedList<String>());
LinkedList<String> edges = (LinkedList<String>) adjacencyMap
.get(v1);
edges.add(v2);
return true;
} catch (Exception e) {
return false;
}
}
}
--> GraphTester.java:
public class GraphTester {
private Graph graph;
public GraphTester(Graph graph) {
this.graph = graph;
}
/**
* adding edges
*/
public void addingEdge(String str1, String str2) {
graph.addEdge(str1, str2);
System.out.println("Added new edge");
}
/**
* return the number of vertices
*/
public int returnNumberofVertices() {
int count = graph.size();
System.out.println("Number of vertices is: " + count);
return (count);
}
/**
* return the number of edges
*/
public int returnNumberofEdges() {
int count = graph.getEdgeCount();
System.out.println("Number of edges is: " + count);
return (count);
}
}