Data Structure : i want GraphTjava code which is work in the main class Driver5.
ID: 3681998 • Letter: D
Question
Data Structure : i want GraphTjava code which is work in the main class Driver5.java. I paste both class code GraphAL and Driver5.java as well.
The GraphAL.javale provides the GraphAL class, used to build and store a static undirected graph. It uses node indexing (from 0) and adjacency lists (built using an internal class GNode) as the underlying data structure, and also has an array of integers (one for each node) to be used to mark nodes. The two adjacency list entries for each edge are linked, and there is also a mark eld on each of them that can be used.
Its constructor sets up the array of adjacency lists and array of marks.
reset() takes an integer parameter and sets all marks to that integer. This method is to be used to initialize marks to the desired default value.
addEdge() takes a pair of indices (x and y ) as parameters, and inserts the edge (x; y)between them into the adjacency list representation.
toString()converts the adjacency lists (and current vertex marks) into a string, with one vertex+list per line.
You need to write a GraphTclass that extends GraphAL, to add the following methods:
1.components(void): count the number of components of the graph, and mark each vertex with its component number. This method needs to call a DFS traversal of the graph (written by you) to traverse and mark the vertices in each component. It should return the number of components.
2.diameter(void): the diameter of a graph is the maximum, over all pairs of vertices(x; y), of the length of the shortest path from x to y(measured as the number of edges it takes to get from x to y). Calculate and return this value. Your method should call a BFS-based method (written by you) for each vertex to nd the lengths of its shortest paths.
Your class will also need a constructor to pass on the size parameter to the GraphAL constructor, and should also have private methods and classes as appropriate. Your class should not have any additional variables declared globally for the class.
Ensure that your code works with the provided Driver5.java code, which will be used to test your submitted solution. Organize and comment your code appropriately
Driver5.java code :
//********************************
// Driver5.java
//********************************
import java.util.Scanner;
public class Driver5
{
public static void main(String[] args)
{
int n, m, x, y;
Scanner scan = new Scanner(System.in);
System.out.print("Number of vertices: ");
n = scan.nextInt();
System.out.print("Number of edges: ");
m = scan.nextInt();
GraphT Graph = new GraphT(n);
System.out.println("Enter edges (pairs of indices):");
for(int i=0;i<m;i++) {
x = scan.nextInt();
y = scan.nextInt();
Graph.addEdge(x,y);
}
System.out.println(Graph);
int parts = Graph.components();
String sp = "component";
if(parts!=1) sp+="s";
System.out.println("Graph has " + parts + " " + sp + ".");
System.out.println(Graph);
int diam = Graph.diameter();
System.out.println("Graph has diameter " + diam + ".");
}
}
GraphAL.java code :
//****************************************************
// GraphAL.java -- basic class for graphs
// uses adjacency lists
//****************************************************
public class GraphAL
{
protected int n;
protected GNode AdjList[];
protected int mark[];
public GraphAL(int size)
{
n = size;
AdjList = new GNode[n];
mark = new int[n];
for(int i=0;i<n;i++) {
AdjList[i] = null;
mark[i] = 0;
}
}
public void reset(int unmarked)
{
for(int i=0;i<n;i++) {
mark[i] = unmarked;
}
}
public void addEdge(int x, int y)
{
GNode entry, trail, forward, backward;
forward = new GNode(y);
backward = new GNode(x);
forward.partner = backward;
backward.partner = forward;
trail=null;
for(entry=AdjList[x];entry!=null;entry=entry.next) {
trail = entry;
}
if(trail!=null) {
trail.next = forward;
}
else {
AdjList[x] = forward;
}
trail=null;
for(entry=AdjList[y];entry!=null;entry=entry.next) {
trail = entry;
}
if(trail!=null) {
trail.next = backward;
}
else {
AdjList[y] = backward;
}
}
public String toString()
{
Integer iobj;
String result = "";
for(int i=0;i<n;i++) {
result += i + " (" + mark[i] + ") : ";
for(GNode list=AdjList[i];list!=null;list=list.next) {
result += " " + list.nbr;
}
result += " ";
}
return result;
}
protected class GNode
{
int nbr;
int mark;
GNode partner;
GNode next;
protected GNode(int index)
{
nbr = index;
mark = 0;
partner = null;
next = null;
}
public String toString()
{
Integer iobj = new Integer(nbr);
return iobj.toString();
}
}
}
Explanation / Answer
package com.he.capillary.chegg1;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
public class GraphTclass extends GraphT {
public GraphTclass(int size) {
super(size);
}
public int components() {
List<Integer> visitedVertexList = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
int componentCount = 0;
for (int i = 0; i < this.n; i++) {
if (!visitedVertexList.contains(i)) {
componentCount++;
stack.push(i);
while (!stack.isEmpty()) {
Integer poppedElement = stack.pop();
visitedVertexList.add(poppedElement);
GNode gNode = this.AdjList[poppedElement];
if (gNode != null) {
GNode temp = gNode;
while (temp != null) {
if (temp.nbr != poppedElement && !visitedVertexList.contains(temp.nbr)
&& !stack.contains(temp.nbr)) {
stack.add(temp.nbr);
}
temp = temp.next;
}
}
}
}
}
return componentCount;
}
public int diameter() {
List<Integer> visitedVertexList = new ArrayList<Integer>();
Queue<Integer> queue = new LinkedList<Integer>();
int maxDistance = 0;
int distance[] = new int[this.n];
for (int i = 0; i < this.n; i++) {
queue.clear();
visitedVertexList.clear();
for (int j = 0; j < this.n; j++) {
distance[j] = -1;
}
distance[i] = 0;
queue.add(i);
while (!queue.isEmpty()) {
Integer poppedElement = queue.poll();
visitedVertexList.add(poppedElement);
GNode gNode = this.AdjList[poppedElement];
if (gNode != null) {
GNode temp = gNode;
while (temp != null) {
if (temp.nbr != poppedElement && !visitedVertexList.contains(temp.nbr)
&& !queue.contains(temp.nbr)) {
queue.add(temp.nbr);
distance[temp.nbr] = distance[poppedElement] + 1;
}
temp = temp.next;
}
}
}
for (int j = 0; j < this.n; j++) {
if (maxDistance < distance[j]) {
maxDistance = distance[j];
}
}
}
return maxDistance;
}
}
==============================
Number of vertices: 6
Number of edges: 6
Enter edges (pairs of indices):
1
2
2
3
3
4
0
5
1
3
1
4
0 (0) : 5
1 (0) : 2 3 4
2 (0) : 1 3
3 (0) : 2 4 1
4 (0) : 3 1
5 (0) : 0
Graph has 2 components.
0 (0) : 5
1 (0) : 2 3 4
2 (0) : 1 3
3 (0) : 2 4 1
4 (0) : 3 1
5 (0) : 0
Graph has diameter 2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.