Using the Graph.java methods, and assuming the variable called graph has been as

Question

Using the Graph.java methods, and assuming the variable called graph has been assigned an instance of a Graph, write statements to add EDGES/vertices which represent the following graph (use 0 for the weight when adding). See GraphTester.java in the Graph Code Files folder in Catalyst for examples.

Graph.java:

import java.util.*;
import java.util.Map.Entry;
interface Visitor<T>
{
public void visit(T obj);
}

// --- assumes definition of simple class Pair<E, F>

// --- Vertex class ------------------------------------------------------
class Vertex<E>
{
public static final double INFINITY = Double.MAX_VALUE;
public HashMap<E, Pair<Vertex<E>, Double> > adjList
= new HashMap<E, Pair<Vertex<E>, Double> >();
public E data;
public double dist; // used for particular graph problems, NOT the graph itself
public Vertex<E> nextInPath; // used for particular graph problems, NOT the graph itself

public Vertex( E x )
{
data = x;
dist = INFINITY;
nextInPath = null;
}
public Vertex() { this(null); }

public void addToAdjList(Vertex<E> neighbor, double cost)
{
   if( adjList.get(neighbor.data) == null)
       adjList.put(neighbor.data, new Pair<Vertex<E>, Double> (neighbor, cost) );
   // Note: if you want to change the cost, you'll need to remove it and then add it back
}

public void addToAdjList(Vertex<E> neighbor, int cost)
{
addToAdjList( neighbor, (double)cost );
}

public boolean equals(Object rhs)
{
Vertex<E> other = (Vertex<E>)rhs;

return (data.equals(other.data));

}

public int hashCode()
{
return (data.hashCode());
}

public void showAdjList()
{
Iterator<Entry<E, Pair<Vertex<E>, Double>>> iter ;
Entry<E, Pair<Vertex<E>, Double>> entry;
Pair<Vertex<E>, Double> pair;

System.out.print( "Adj List for " + data + ": ");
iter = adjList.entrySet().iterator();
while( iter.hasNext() )
{
entry = iter.next();
pair = entry.getValue();
System.out.print( pair.first.data + "("
+ String.format("%3.1f", pair.second)
+ ") " );
}
System.out.println();
}

}

public class Graph<E>
{
// the graph data is all here --------------------------
protected HashMap<E, Vertex<E> > vertexSet;

// public graph methods --------------------------------
public Graph ()
{
vertexSet = new HashMap<E, Vertex<E> >();
}

public Graph( Edge<E>[] edges )
{
this();
int k, numEdges;
numEdges = edges.length;

for (k = 0; k < numEdges; k++)
addEdge( edges[k].source.data,
edges[k].dest.data, edges[k].cost);
}

public void addEdge(E source, E dest, double cost)
{
Vertex<E> src, dst;

// put both source and dest into vertex list(s) if not already there
src = addToVertexSet(source);
dst = addToVertexSet(dest);

// add dest to source's adjacency list
src.addToAdjList(dst, cost);
//dst.addToAdjList(src, cost); // ADD THIS IF UNDIRECTED GRAPH
}

public void addEdge(E source, E dest, int cost)
{
addEdge(source, dest, (double)cost);
}

// adds vertex with x in it, and always returns ref to it
public Vertex<E> addToVertexSet(E x)
{
Vertex<E> retVal=null;
Vertex<E> foundVertex;

// find if Vertex already in the list:
foundVertex = vertexSet.get(x);
  
if ( foundVertex != null ) // found it, so return it
{
return foundVertex;
}

// the vertex not there, so create one
retVal = new Vertex<E>(x);
vertexSet.put(x, retVal);

return retVal; // should never happen
}

public boolean remove(E start, E end)
{
   Vertex<E> startVertex = vertexSet.get(start);
   boolean removedOK = false;
     
   if( startVertex != null )
   {
       Pair<Vertex<E>, Double> endPair = startVertex.adjList.remove(end);
       removedOK = endPair!=null;
   }
   /*// Add if UNDIRECTED GRAPH:
       Vertex<E> endVertex = vertexSet.get(end);
       if( endVertex != null )
       {
           Pair<Vertex<E>, Double> startPair = endVertex.adjList.remove(start);
           removedOK = startPair!=null ;
       }
       */

   return removedOK;
}

public void showAdjTable()
{
Iterator<Entry<E, Vertex<E>>> iter;

System.out.println( "------------------------ ");
iter = vertexSet.entrySet().iterator();
while( iter.hasNext() )
{
(iter.next().getValue()).showAdjList();
}
System.out.println();
}

public void clear()
{
vertexSet.clear();
}

/** Breadth-first traversal from the parameter startElement*/
public void breadthFirstTraversal(E startElement, Visitor<E> visitor)
{
   Vertex<E> currVertex;
}

/** Postorder traversal from the parameter startElement */
public void depthFirstTraversal(E startElement, Visitor<E> visitor)
{
     
}

}

GraphTester.java:

import java.util.*;
import java.text.*;

//------------------------------------------------------
public class GraphTester
{
   // ------- main --------------
   public static void main(String[] args)
   {
   // build graph
   Graph<String> myGraph1 = new Graph<String>();
   myGraph1.addEdge("A", "B", 0); myGraph1.addEdge("A", "C", 0); myGraph1.addEdge("A", "D", 0);
   myGraph1.addEdge("B", "E", 0); myGraph1.addEdge("B", "F", 0);
   myGraph1.addEdge("C", "G", 0);
   myGraph1.addEdge("D", "H", 0); myGraph1.addEdge("D", "I", 0);
   myGraph1.addEdge("F", "J", 0);
   myGraph1.addEdge("G", "K", 0); myGraph1.addEdge("G", "L", 0);
   myGraph1.addEdge("H", "M", 0); myGraph1.addEdge("H", "N", 0);
   myGraph1.addEdge("I", "N", 0);

   myGraph1.showAdjTable();
  

   }

}

Explanation / Answer

Going through the description I can only assume that the question wants only the line of codes where we want to replicate creation of the Graph shown in the given diagram via the code given and add its respective edges.
-Many of the critical section of the given code is missing, but if we only want to do what was mentioned above then that can be done accordingly following the below mentioned steps:
-All the additions has to happen via a class having a Main method like below.

public class GraphTester
{
       // ------- main --------------
       public static void main(String[] args)
       {
          // build graph
      
       // Creating a new Graph Object called myGraph2
       Graph<Integer> myGraph2 = new Graph<Integer>();
      
       /*Below calling in the Graph class's inbuilt method called addEdge to add a edge for all edges originating from Source vertex 1 via above created Graph object called myGraph2
       /*
      
       myGraph2.addEdge(1, 2, 0);
       myGraph2.addEdge(1, 3, 0);
       myGraph2.addEdge(1, 4, 0);


       // adding all edges originating from Source vertex 2
      
       myGraph2.addEdge(2, 4, 0);
       myGraph2.addEdge(2, 5, 0);

// adding all edges originating from Source vertex 3
       myGraph2.addEdge(3, 6, 0);

// adding all edges originating from Source vertex 4
       myGraph2.addEdge(4, 3, 0);
       myGraph2.addEdge(4, 6, 0);
       myGraph2.addEdge(4, 7, 0);

// adding all edges originating from Source vertex 5
       myGraph2.addEdge(5, 4, 0);
       myGraph2.addEdge(5, 7, 0);
   // No edges originating from Source vertex 6
   // adding all edges originating from Source vertex 7
       myGraph2.addEdge(7, 6, 0);
  
  
   //calling in the inbuild method called showAdjTable()
       myGraph2.showAdjTable();
       }

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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