Please note!! This is only one question, I explained the question in the detailed formated with instructions and example, you only have to edit the given code to get the similar output in the example. Please answer it in step by step format. Thank you!!

Finding a cycle in a directed graph using depth-first search. A directed graph is a graph where edges are directional; that is, edges (p,q) and (q,p) are distinct. An important class of directed graphs are directed acyclic graphs (DAGs), which have broad applications in programming languages and compilers. A DAG is any directed graph with no cycles. For example, this is a directed graph:

The above graph is not a DAG because it contains cycles. The cycles are:

1 2 4 7 4 5 7 

By extension, these rotated versions are also valid cycles of the above graph (and they are all such possible rotations):

2 1 7 4 5 7 4 7 4 5 

In this final part of the assignment, you will bring together ideas you have used throughout this assignment to find and print a cycle in a directed graph. If no cycles are found, your program will report that the graph is a DAG. You can use any algorithm for this task; either the DFS or the BFS approaches you have used in this assignment so far can be useful.

Input

Your program should take a single command line argument specifying the path to an input file. Test cases for your program are in the tests/ directory. In each test case, the first line records the number of nodes N in the graph. Then, the adjacency matrix is recorded in the subsequent N rows of the file. This time, the adjacency matrix represents a directed graph.

Output

You should print a single line of nodes (separated by spaces) that forms a cycle in the input directed graph. For example, for the example directed graph above you can print any one of the seven cycles listed above. This time, the ordering of the nodes does matter as this is a directed graph. If no cycles were found, your program should print "DAG", meaning the graph is acyclic. The known cycles for each test case are in the answers/ directory. You can print out rotated versions of the known cycles; the autograder will see that rotated cycles are equivalent.

graphutils.h code:

#include

#include

#include

#include

#include

#include

typedefsize_tgraphNode_t;

typedefstructAdjacencyListNode AdjacencyListNode;

structAdjacencyListNode {

graphNode_t graphNode; //the destination graph node

doubleweight; //a weight, if weighted graph, otherwise will be 1.0

AdjacencyListNode* next; //pointer to next linked list node

};

boolalmostEqual(doublea, doubleb)

{

returnfabs(a - b)

}

//READ INPUT FILE TO CREATE GRAPH ADJACENCY LIST

//Reads adjacency matrices for both undirected and directed graphs.

//Reads adjacency matrices for both unweighted and weighted graphs.

//Returns the number of nodes in the graph; returns 0 if reading failed.

size_tadjMatrixToList(

constchar* filename, //path to input file containing adjacency matrix

AdjacencyListNode** adjacencyList

) {

FILE* fp = fopen(filename, "r");

if(!fp) {

perror("fopen failed");

return0;

}

//first, read the graphNodeCount

size_tgraphNodeCount;

fscanf(fp, "%ld", &graphNodeCount);

/ext, allocate the linked list heads

*adjacencyList = calloc( graphNodeCount, sizeof(AdjacencyListNode) );

//finally, read the adjacency matrix and allocate linked list nodes

for(size_tadjMatrixRow=0; adjMatrixRow

(*adjacencyList)[adjMatrixRow].graphNode= adjMatrixRow; //A note indicating source graph node

(*adjacencyList)[adjMatrixRow].next= NULL;

for(size_tadjMatrixCol=0; adjMatrixCol

doubleweight;

fscanf(fp, "%lf", &weight);

if( !almostEqual(weight,0.0) ) { //if not almost zero, indicating an edge exists

AdjacencyListNode* newTop = calloc(1,sizeof(AdjacencyListNode));

newTop->graphNode= adjMatrixCol;

newTop->weight= weight;

newTop->next= (*adjacencyList)[adjMatrixRow].next;

(*adjacencyList)[adjMatrixRow].next= newTop;

}

}

}

fclose(fp);

returngraphNodeCount;

}

//TRAVERSE AND FREE THE LINKED LISTS, AND FREE THE ADJACENCY LIST

voidfreeAdjList(

size_tgraphNodeCount,

AdjacencyListNode* adjacencyList

) {

//example of how to traverse the graph adjacency list

for(size_tsource=0; source

AdjacencyListNode* dest = adjacencyList[source].next;

//list iterator

while(dest) {

AdjacencyListNode* temp = dest;

dest = dest->next; //iterator moves to next

free(temp);

}

}

free(adjacencyList);

}

Edit the given code below:

#include "../graphutils.h"

// A program to find a cycle in a directed graph

// You may use DFS or BFS as needed

/* ... */

int main ( int argc, char* argv[] ) {

// READ INPUT FILE TO CREATE GRAPH ADJACENCY LIST

AdjacencyListNode* adjacencyList;

/* ... */

bool isCyclic = false;

for (unsigned source=0; source

/* ... */

}

if (!isCyclic) { printf("DAG "); }

freeAdjList ( graphNodeCount, adjacencyList );

return EXIT_SUCCESS;

}