Complete sections labelled TODO based off of information given and partial code
ID: 3695633 • Letter: C
Question
Complete sections labelled TODO based off of information given and partial code given:
Class SpyGraph java.lang.Object SpyGraph All Implemented Interfaces: java.lang.Iterable GraphNode> public class SpyGraph extends java.lang.0bject implements java.lang. IterablecGraphNode> Stores all vertexes as a list of GraphNodes. Provides necessary graph operations as need by the SpyGame class Constructor Summary Constructors Constructor and Description SpyGraph () Initializes an empty list of GraphNode objects Method Summary All Methods Modifier and Type void Instance MethodsConcrete Methods Method and Description int cost) addEdge (java. lang.String vlname, java.lang.String v2name, Adds v2 as a neighbor of v1 and adds v1 as a neighbor of v2 void addGraphNode (java.lang.String name) Add a vertex with this label to the list of vertexes java.util.List BFS (java.lang.String start, java.lang.String end) Return Breadth First Search list of nodes on path from one Node to another java.util.List DFS (java.lang.String start, java.lang.String end) Return Depth First Search list of nodes on path from one Node to another java.util.ListExplanation / Answer
import java.util.*;
private HashSet<String> vertices;
/*
* For any vertex v, we usually think of the adjacency list as a
* list of vertices w that represents the edges (v,w) in the graph.
* In a weighted graph, we also need to store the weight of each edge.
* We can do so by using a map for the adjacency list, namely it is
* a map from vertices to weights. That is, rather than representing the
* adjacency list of v as a list, we represent it as a map
* {(w, weight(v,w)) : (v,w) in E}.
*/
private HashMap<String, HashMap<String,Double>> adjList;
// constructor
public Graph()
{
vertices = new HashSet<String>();
adjList = new HashMap<String, HashMap<String,Double>>();
}
Packdel pd=new SpyGraph();
Packdel pd=new addGraphNode(String name);
Packdel pd=new addEdge(String v1name, String v2name, int cost);
Packdel pd=new Bfs(String start, String end, Set<String> dict);
Packdel pd=new Dfs(String start, String end, Set<String> dict);
Packdel pd=new Dfs(String start, String end, Set<String> dict);
Packdel pd=new Dfs(GraphNode getRandomNode);
/**
* Stores all vertexes as a list of GraphNodes. Provides necessary graph operations as
* need by the SpyGame class.
*
* @author strominger
*
*/
public class SpyGraph implements Iterable<GraphNode> {
/** DO NOT EDIT -- USE THIS LIST TO STORE ALL GRAPHNODES */
private List<GraphNode> vlist;
/**
* Initializes an empty list of GraphNode objects
*/
public SpyGraph(){
// TODO initialize data member(s)
}
/**
* Add a vertex with this label to the list of vertexes.
* No duplicate vertex names are allowed.
* @param name The name of the new GraphNode to create and add to the list.
*/
public void addGraphNode(String name){
// TODO implement this method
}
/**
* Adds v2 as a neighbor of v1 and adds v1 as a neighbor of v2.
* Also sets the cost for each neighbor pair.
*
* @param v1name The name of the first vertex of this edge
* @param v2name The name of second vertex of this edge
* @param cost The cost of traveling to this edge
* @throws IllegalArgumentException if the names are the same
*/
public void addEdge(String v1name, String v2name, int cost) throws IllegalArgumentException{
public void addVertex(String v)
{
// If there's already a vertex there, then throw an exception.
if (vertices.contains(v))
throw new IllegalArgumentException("Trying to add vertex " + String.valueOf(v) + ", but its already there.");
vertices.add(v);
adjList.put(v, new HashMap<String,Double>());
}
/**
* Adds an edge to the adjacency list. Edge is (start,end, weight), so it adds end to adjacency list of start Vertex.
* @param start Vertex of the edge
* @param end Vertex of the edge
* @param double weight of the edge
*/
public void addEdge(String start, String end, double weight)
{
HashMap<String,Double> map = adjList.get(start);
map.put(end, new Double(weight));
}
public HashSet<String> getVertices()
{
return vertices;
}
/**
* @return get the adjacency list map (which is a map of maps)
*/
public HashMap<String, HashMap<String, Double>> getAdjList()
{
return adjList;
}
// make a string that can be used for printing the graph
public String toString()
{
String result="";
for(String label: vertices)
{
result += label + ' ';
Set<String> endVertices = adjList.get(label).keySet();
for (String w_label: endVertices){
result += " edge to " + w_label + " with weight " + adjList.get(label).get(w_label) + " ";
}
}
return(result);
}
// TODO implement this method
}
/**
* Return an iterator through all nodes in the SpyGraph
* @return iterator through all nodes in alphabetical order.
*/
public Iterator<GraphNode> iterator() {
return vlist.iterator();
}
/**
* Return Breadth First Search list of nodes on path
* from one Node to another.
* @param start First node in BFS traversal
* @param end Last node (match node) in BFS traversal
* @return The BFS traversal from start to end node.
*/
// TODO implement this method
// may need and create a companion method
return null;
}
/**
* @param name Name corresponding to node to be returned
* @return GraphNode associated with name, null if no such node exists
*/
public GraphNode getNodeFromName(String name){
for ( GraphNode n : vlist ) {
if (n.getNodeName().equalsIgnoreCase(name))
return n;
}
return null;
}
/**
* Return Depth First Search list of nodes on path
* from one Node to another.
* @param start First node in DFS traversal
* @param end Last node (match node) in DFS traversal
* @return The DFS traversal from start to end node.
*/
// TODO implement this method
// may need and create a companion method
return null;
}
/**
* OPTIONAL: Students are not required to implement Dijkstra's ALGORITHM
*
* Return Dijkstra's shortest path list of nodes on path
* from one Node to another.
* @param start First node in path
* @param end Last node (match node) in path
* @return The shortest cost path from start to end node.
*/
public List<Neighbor> Dijkstra(String start, String end){
// TODO: implement Dijkstra's shortest path algorithm
// may need and create a companion method
return null;
}
/**
* DO NOT EDIT THIS METHOD
* @return a random node from this graph
*/
public GraphNode getRandomNode() {
if (vlist.size() <= 0 ) {
System.out.println("Must have nodes in the graph before randomly choosing one.");
return null;
}
int randomNodeIndex = Game.RNG.nextInt(vlist.size());
return vlist.get(randomNodeIndex);
}
}
private HashSet<String> vertices;
/*
* For any vertex v, we usually think of the adjacency list as a
* list of vertices w that represents the edges (v,w) in the graph.
* In a weighted graph, we also need to store the weight of each edge.
* We can do so by using a map for the adjacency list, namely it is
* a map from vertices to weights. That is, rather than representing the
* adjacency list of v as a list, we represent it as a map
* {(w, weight(v,w)) : (v,w) in E}.
*/
private HashMap<String, HashMap<String,Double>> adjList;
// constructor
public Graph()
{
vertices = new HashSet<String>();
adjList = new HashMap<String, HashMap<String,Double>>();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.