The objective of this project is to use the Depth First Search (DFS) algorithm to assign directions to the edges of an undirected graph so that the resulting directed graph is a directed acyclic graph (DAG). You are given the code to run the DFS on an undirected graph as well as all the auxiliary classes needed. The Graph class has member variables to assign the push order and pop order for the vertices as well as to keep track of the number of vertices that have been pushed and popped until then. Strategy: Run DFS on the given undirected graph and determine the pop order of the vertices. For any undirected edge u-v in the graph, assign the direction u -> v if the pop order of u is greater than the pop order of v, or assign the direction v -> u if the pop order of v is greater than the pop order of u. You are given the code for running the DFS algorithm (in a recursive fashion) on an undirected graph (whose edge information is input to the user).

Extend the DFS algorithm to determine/set the push and pop order of the vertices and extend the code in the main function to use the pop order of the vertices in the graph and assign the directions to the edges. Your code in the main function should output the push and pop order of the vertices as well as the directions assigned for the edges so that the resulting directed graph is a DAG. Include the entire code with all the extensions in your project report.

Justify why the above suggested strategy of assigning edges will indeed work. Give a clear explanation.

Draw an undirected graph of 10 or more vertices and use the above strategy to assign directions of the edges.

Prepare the edge text file based on the undirected graph of (3), pass it to your code of (1) and capture a screenshot of the output. Compare the directions of the edges assigned in (3) and (4): they are expected to be the same.

Java Code

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 Graph{

private int numNodes;

private List[] adjacencyList;

private int[] pushOrder;

private int[] popOrder;

private int lastPushNumber = 0;

private int lastPopNumber = 0;

Graph(int n){

numNodes = n;

adjacencyList = new List[numNodes];

pushOrder = new int[numNodes];

popOrder = 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 getDegree(int id){

return adjacencyList[id].countList();

}

public int getPushOrder(int id){

return pushOrder[id];

}

public int getPopOrder(int id){

return popOrder[id];

}

public void resetLastPopNumber(){

lastPopNumber = 0;

}

public void resetLastPushNumber(){

lastPushNumber = 0;

}

public void RunDFSRecur(int visitedNodeID, boolean[] visitedNodes){

visitedNodes[visitedNodeID] = true;

pushOrder[visitedNodeID] = ++lastPushNumber;

int neighborListSize = adjacencyList[visitedNodeID].countList();

for (int index = 0; index < neighborListSize; index++){

int neighbID = adjacencyList[visitedNodeID].read(index);

if (!visitedNodes[neighbID]){

RunDFSRecur(neighbID, visitedNodes);

}

}

popOrder[visitedNodeID] = ++lastPopNumber;

}

public void RunDFSRecursive(int rootNodeID){

boolean[] visitedNodes = new boolean[numNodes];

for (int id = 0; id < numNodes; id++){

visitedNodes[id] = false;

pushOrder[id] = -1;

popOrder[id] = -1;

}

RunDFSRecur(rootNodeID, visitedNodes);

resetLastPushNumber();

resetLastPopNumber();

}

}

class Graph_DFS_EdgeClassification{

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.RunDFSRecursive(0);

System.out.println();

// Add code to print the push and pop order of the vertices

// Add code to assign and print the directions to the edges such that the resulting directed graph is a DAG

}

catch(Exception e){e.printStackTrace();}

}

}

Text File (Graph Edges)

0 1

0 7

1 2

1 3

2 4

2 7

3 4

3 5

4 6

5 6