Please write a complete working code in Java: Submission: Please show work for 1
ID: 3709326 • Letter: P
Question
Please write a complete working code in Java:
Submission: Please show work for 1, 2 and 3 for this Project: please draw the graph with 10 or more vertices for # 2 of project.
Sample Code and edge graph:
Project 8 Word:
Sample Code For Project:
import java.io.*;
import java.util.*;
class Node{
private int data;
private Node nextNodePtr;
public Node(){}
public void setData(int d){
data = d;
}
public int getData(){
return data;
}
public void setNextNodePtr(Node nodePtr){
nextNodePtr = nodePtr;
}
public Node getNextNodePtr(){
return nextNodePtr;
}
}
class List{
private Node headPtr;
public List(){
headPtr = new Node();
headPtr.setNextNodePtr(null);
}
public Node getHeadPtr(){
return headPtr;
}
public boolean isEmpty(){
if (headPtr.getNextNodePtr() == null)
return true;
return false;
}
public void insert(int data){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
while (currentNodePtr != null){
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
}
Node newNodePtr = new Node();
newNodePtr.setData(data);
newNodePtr.setNextNodePtr(null);
prevNodePtr.setNextNodePtr(newNodePtr);
}
public void insertAtIndex(int insertIndex, int data){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == insertIndex)
break;
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
Node newNodePtr = new Node();
newNodePtr.setData(data);
newNodePtr.setNextNodePtr(currentNodePtr);
prevNodePtr.setNextNodePtr(newNodePtr);
}
public int read(int readIndex){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == readIndex)
return currentNodePtr.getData();
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
return -1; // an invalid value indicating
// index is out of range
}
public void modifyElement(int modifyIndex, int data){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == modifyIndex){
currentNodePtr.setData(data);
return;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
}
public void deleteElementAtIndex(int deleteIndex){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
Node nextNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == deleteIndex){
nextNodePtr = currentNodePtr.getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
prevNodePtr.setNextNodePtr(nextNodePtr);
}
public void deleteElement(int deleteData){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
Node nextNodePtr = headPtr;
while (currentNodePtr != null){
if (currentNodePtr.getData() == deleteData){
nextNodePtr = currentNodePtr.getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
}
prevNodePtr.setNextNodePtr(nextNodePtr);
}
public void IterativePrint(){
Node currentNodePtr = headPtr.getNextNodePtr();
while (currentNodePtr != null){
System.out.print(currentNodePtr.getData()+" ");
currentNodePtr = currentNodePtr.getNextNodePtr();
}
System.out.println();
}
public int countList(){
Node currentNodePtr = headPtr.getNextNodePtr();
int countElements = 0;
while (currentNodePtr != null){
//System.out.print(currentNodePtr.getData()+" ");
countElements++;
currentNodePtr = currentNodePtr.getNextNodePtr();
}
return countElements;
}
}
class Queue{
private int array[];
private int maxSize; // useful to decide if resizing (doubling the array size) is needed
private int endOfQueue; // same as endOfArray
public Queue(int size){
array = new int[size];
maxSize = size;
endOfQueue = -1;
}
public boolean isEmpty(){
if (endOfQueue == -1)
return true;
return false;
}
public void resize(int s){
int tempArray[] = array;
array = new int[s];
for (int index = 0; index < Math.min(s, endOfQueue+1); index++){
array[index] = tempArray[index];
}
maxSize = s;
}
public void enqueue(int data){ // same as insert 'at the end'
if (endOfQueue == maxSize-1)
resize(2*maxSize);
array[++endOfQueue] = data;
}
public int peek(){
if (endOfQueue >= 0)
return array[0];
else
return -1000000;// an invalid value indicating
// queue is empty
}
public int dequeue(){
if (endOfQueue >= 0){
int returnVal = array[0];
for (int index = 0; index < endOfQueue; index++)
array[index] = array[index+1];
endOfQueue--;
// the endOfQueue is decreased by one
return returnVal;
}
else
return -1000000; // an invalid value indicating
// queue is empty
}
}
class Graph{
private int numNodes;
private List[] adjacencyList;
private int[] levelNumbers;
private int[] predecessorList;
Graph(int n){
numNodes = n;
adjacencyList = new List[numNodes];
levelNumbers = new int[numNodes];
predecessorList = new int[numNodes];
for (int id = 0; id < numNodes; id++)
adjacencyList[id] = new List();
}
public void addEdge(int u, int v){
adjacencyList[u].insert(v);
adjacencyList[v].insert(u);
}
public List getNeighborList(int id){
return adjacencyList[id];
}
public int getLevelNumber(int id){
return levelNumbers[id];
}
public int getPredecessor(int id){
return predecessorList[id];
}
public void RunBFS(int startNodeID){
boolean[] visitedNodes = new boolean[numNodes];
for (int id = 0; id < numNodes; id++){
levelNumbers[id] = -1;
visitedNodes[id] = false;
predecessorList[id] = -1;
}
levelNumbers[startNodeID] = 0;
visitedNodes[startNodeID] = true;
Queue FIFOQueue = new Queue(1);
FIFOQueue.enqueue(startNodeID);
while (!FIFOQueue.isEmpty()){
int firstNodeID = FIFOQueue.dequeue();
int neighborListSize = adjacencyList[firstNodeID].countList();
for (int index = 0; index < neighborListSize; index++){
int neighborID = adjacencyList[firstNodeID].read(index);
if (!visitedNodes[neighborID]){
visitedNodes[neighborID] = true;
FIFOQueue.enqueue(neighborID);
levelNumbers[neighborID] = levelNumbers[firstNodeID] + 1;
predecessorList[neighborID] = firstNodeID;
}
}
}
}
}
class Graph_BFS_ShortestPaths_Solution{
public static void main(String[] args){
try{
Scanner input = new Scanner(System.in);
String graphEdgesFilename;
System.out.print("Enter the file name for the edges of the graph: ");
graphEdgesFilename = input.next();
int numNodes;
System.out.print("Enter number of nodes: ");
numNodes = input.nextInt();
Graph graph = new Graph(numNodes);
FileReader fr = new FileReader(graphEdgesFilename);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ( (line = br.readLine() ) != null){
StringTokenizer stk = new StringTokenizer(line);
int uNodeID = Integer.parseInt(stk.nextToken());
int vNodeID = Integer.parseInt(stk.nextToken());
graph.addEdge(uNodeID, vNodeID);
}
graph.RunBFS(0);
// *******Add code here*******
}
catch(Exception e){e.printStackTrace();}
}
}
Sample Edge Graph for Project:
0 1
0 7
1 2
1 3
2 4
2 7
3 4
3 5
4 6
5 6
Explanation / Answer
Just add function in graph :
public void printShortestPath(int node, List path) {
if (node == -1) {
return;
}
path.insertAtIndex(0, node);
int predecessor = getPredecessor(node);
printShortestPath(predecessor, path);
}
and add code in Add Code section:
// *******Add code here*******
System.out.println("Shortest Path from vertex 0 to each one is ");
for(int i=1;i<numNodes;i++){
//System.out.println(graph.getPredecessor(i));
List shortestpath = new List();
graph.printShortestPath(i,shortestpath);
shortestpath.IterativePrint();
}
Full working code is:
import java.io.*;
import java.util.*;
class Node{
private int data;
private Node nextNodePtr;
public Node(){}
public void setData(int d){
data = d;
}
public int getData(){
return data;
}
public void setNextNodePtr(Node nodePtr){
nextNodePtr = nodePtr;
}
public Node getNextNodePtr(){
return nextNodePtr;
}
}
class List{
private Node headPtr;
public List(){
headPtr = new Node();
headPtr.setNextNodePtr(null);
}
public Node getHeadPtr(){
return headPtr;
}
public boolean isEmpty(){
if (headPtr.getNextNodePtr() == null)
return true;
return false;
}
public void insert(int data){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
while (currentNodePtr != null){
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
}
Node newNodePtr = new Node();
newNodePtr.setData(data);
newNodePtr.setNextNodePtr(null);
prevNodePtr.setNextNodePtr(newNodePtr);
}
public void insertAtIndex(int insertIndex, int data){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == insertIndex)
break;
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
Node newNodePtr = new Node();
newNodePtr.setData(data);
newNodePtr.setNextNodePtr(currentNodePtr);
prevNodePtr.setNextNodePtr(newNodePtr);
}
public int read(int readIndex){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == readIndex)
return currentNodePtr.getData();
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
return -1; // an invalid value indicating
// index is out of range
}
public void modifyElement(int modifyIndex, int data){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == modifyIndex){
currentNodePtr.setData(data);
return;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
}
public void deleteElementAtIndex(int deleteIndex){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
Node nextNodePtr = headPtr;
int index = 0;
while (currentNodePtr != null){
if (index == deleteIndex){
nextNodePtr = currentNodePtr.getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
index++;
}
prevNodePtr.setNextNodePtr(nextNodePtr);
}
public void deleteElement(int deleteData){
Node currentNodePtr = headPtr.getNextNodePtr();
Node prevNodePtr = headPtr;
Node nextNodePtr = headPtr;
while (currentNodePtr != null){
if (currentNodePtr.getData() == deleteData){
nextNodePtr = currentNodePtr.getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr.getNextNodePtr();
}
prevNodePtr.setNextNodePtr(nextNodePtr);
}
public void IterativePrint(){
Node currentNodePtr = headPtr.getNextNodePtr();
while (currentNodePtr != null){
System.out.print(currentNodePtr.getData()+" ");
currentNodePtr = currentNodePtr.getNextNodePtr();
}
System.out.println();
}
public int countList(){
Node currentNodePtr = headPtr.getNextNodePtr();
int countElements = 0;
while (currentNodePtr != null){
//System.out.print(currentNodePtr.getData()+" ");
countElements++;
currentNodePtr = currentNodePtr.getNextNodePtr();
}
return countElements;
}
}
class Queue{
private int array[];
private int maxSize; // useful to decide if resizing (doubling the array size) is needed
private int endOfQueue; // same as endOfArray
public Queue(int size){
array = new int[size];
maxSize = size;
endOfQueue = -1;
}
public boolean isEmpty(){
if (endOfQueue == -1)
return true;
return false;
}
public void resize(int s){
int tempArray[] = array;
array = new int[s];
for (int index = 0; index < Math.min(s, endOfQueue+1); index++){
array[index] = tempArray[index];
}
maxSize = s;
}
public void enqueue(int data){ // same as insert 'at the end'
if (endOfQueue == maxSize-1)
resize(2*maxSize);
array[++endOfQueue] = data;
}
public int peek(){
if (endOfQueue >= 0)
return array[0];
else
return -1000000;// an invalid value indicating
// queue is empty
}
public int dequeue(){
if (endOfQueue >= 0){
int returnVal = array[0];
for (int index = 0; index < endOfQueue; index++)
array[index] = array[index+1];
endOfQueue--;
// the endOfQueue is decreased by one
return returnVal;
}
else
return -1000000; // an invalid value indicating
// queue is empty
}
}
class Graph{
private int numNodes;
private List[] adjacencyList;
private int[] levelNumbers;
private int[] predecessorList;
Graph(int n){
numNodes = n;
adjacencyList = new List[numNodes];
levelNumbers = new int[numNodes];
predecessorList = new int[numNodes];
for (int id = 0; id < numNodes; id++)
adjacencyList[id] = new List();
}
public void addEdge(int u, int v){
adjacencyList[u].insert(v);
adjacencyList[v].insert(u);
}
public List getNeighborList(int id){
return adjacencyList[id];
}
public int getLevelNumber(int id){
return levelNumbers[id];
}
public int getPredecessor(int id){
return predecessorList[id];
}
public void printShortestPath(int node, List path) {
if (node == -1) {
return;
}
path.insertAtIndex(0, node);
int predecessor = getPredecessor(node);
printShortestPath(predecessor, path);
}
public void RunBFS(int startNodeID){
boolean[] visitedNodes = new boolean[numNodes];
for (int id = 0; id < numNodes; id++){
levelNumbers[id] = -1;
visitedNodes[id] = false;
predecessorList[id] = -1;
}
levelNumbers[startNodeID] = 0;
visitedNodes[startNodeID] = true;
Queue FIFOQueue = new Queue(1);
FIFOQueue.enqueue(startNodeID);
while (!FIFOQueue.isEmpty()){
int firstNodeID = FIFOQueue.dequeue();
int neighborListSize = adjacencyList[firstNodeID].countList();
for (int index = 0; index < neighborListSize; index++){
int neighborID = adjacencyList[firstNodeID].read(index);
if (!visitedNodes[neighborID]){
visitedNodes[neighborID] = true;
FIFOQueue.enqueue(neighborID);
levelNumbers[neighborID] = levelNumbers[firstNodeID] + 1;
predecessorList[neighborID] = firstNodeID;
}
}
}
}
}
class bfs{
public static void main(String[] args){
try{
Scanner input = new Scanner(System.in);
String graphEdgesFilename;
System.out.print("Enter the file name for the edges of the graph: ");
graphEdgesFilename = input.next();
int numNodes;
System.out.print("Enter number of nodes: ");
numNodes = input.nextInt();
Graph graph = new Graph(numNodes);
FileReader fr = new FileReader(graphEdgesFilename);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ( (line = br.readLine() ) != null){
StringTokenizer stk = new StringTokenizer(line);
int uNodeID = Integer.parseInt(stk.nextToken());
int vNodeID = Integer.parseInt(stk.nextToken());
//System.out.println(uNodeID, vNodeID);
graph.addEdge(uNodeID, vNodeID);
}
graph.RunBFS(0);
// *******Add code here*******
System.out.println("Shortest Path from vertex 0 to each one is ");
for(int i=1;i<numNodes;i++){
//System.out.println(graph.getPredecessor(i));
List shortestpath = new List();
graph.printShortestPath(i,shortestpath);
shortestpath.IterativePrint();
}
}
catch(Exception e){e.printStackTrace();}
}
}