Please help with this assignment!
CSE 101 Introduction to Data Structures and Algorithms Programming Assignment 3 In this assignment you will build a Graph module in C that implements the Depth First Search (DFS) algorithm. You will use your Graph module to find the strongly connected components of a digraph. Read the handout on graph algorithms, and sections 22.3-22.5 of the text. Also see the pseudo-code posted on the class webpage at Examples/Pseudo-Code/GraphAlgorithms. A digraph ? = (?, ?) is said to be strongly connected iff for every pair of vertices ?, ? ∈ ?, vertex u is reachable from v, and vertex v is reachable from u. Most directed graphs are not strongly connected. In general, we say a subset ? ⊆ ? is strongly connected iff every vertex in X is reachable from every other vertex in X. A strongly connected subset that is maximal with respect to this property is called a strongly connected component of G. In other words, ? ⊆ ? is a strongly connected component of G, if and only if (i) ? is strongly connected, and (ii) the addition of one more vertex to ? would create a subset that is not strongly connected. Example ? We can see that this digraph contains 4 strongly connected components: ?1 = {1, 2, 5}, ?2 = {3, 4}, ?3 = {6, 7}, and ?4 = {8}. To find the strong components of a digraph G call DFS(?). As vertices are finished, place them onto a stack. When DFS is complete the stack will store the vertices ordered by decreasing finish times. Next, compute the transpose ?? of ?. (The digraph ?? is obtained by reversing directions on all edges of ?.) Finally run DFS(??), but in the main loop (lines 5-7) of DFS, process vertices in order of decreasing finish times from the first call to DFS. This is accomplished by popping vertices off the stack. When the whole process is complete, the trees in the resulting DFS forest span the strong components of G. Note the strongly connected components of G are identical to the strong components of ??. See the algorithm Strongly- Connected-Components in section 22.5 (p.617) of the text. Your graph module will again use the adjacency list representation. It will, among other things, provide the capability of running DFS, and computing the transpose of a directed graph. DFS requires that vertices possess attributes for color (white, black, grey), discover time, finish time, and parent. Below is a catalog of required functions and prototypes, constituting the majority of Graph.h. // Constructors-Destructors Graph newGraph(int n); void freeGraph(Graph* pG); // Access functions int getOrder(Graph G); int getSize(Graph G); int getParent(Graph G, int u); /* Pre: 1<><=n=getorder(g) */="" int="" getdiscover(graph="" g,="" int="" u);="" *="" pre:=""><><=n=getorder(g) */="" int="" getfinish(graph="" g,="" int="" u);="" *="" pre:=""><><=n=getorder(g) */="" manipulation="" procedures="" void="" addarc(graph="" g,="" int="" u,="" int="" v);="" *="" pre:=""><><=n,><><=n */="" void="" addedge(graph="" g,="" int="" u,="" int="" v);="" *="" pre:=""><><=n,><><=n */="" void="" dfs(graph="" g,="" list="" s);="" *="" pre:="" length(s)="=getOrder(G)" */="" other="" functions="" graph="" transpose(graph="" g);="" graph="" copygraph(graph="" g);="" void="" printgraph(file*="" out="" ,="" graph="" g);="" function="" newgraph()="" will="" return="" a="" reference="" to="" a="" new="" graph="" object="" containing="" n="" vertices="" and="" no="" edges.="" freegraph()="" frees="" all="" heap="" memory="" associated="" with="" a="" graph="" and="" sets="" its="" graph="" argument="" to="" null.="" function="" getorder()="" returns="" the="" number="" of="" vertices="" in="" ,="" while="" functions="" getparent(),="" getdiscover(),="" and="" getfinish()="" return="" the="" appropriate="" field="" values="" for="" the="" given="" vertex.="" note="" that="" the="" parent="" of="" a="" vertex="" may="" be="" nil.="" the="" discover="" and="" finish="" times="" of="" vertices="" will="" be="" undefined="" before="" dfs="" is="" called.="" you="" must="" #define="" constant="" macros="" for="" nil="" and="" undef="" representing="" those="" values="" and="" place="" the="" definitions="" in="" the="" graph.h.="" the="" descriptions="" of="" functions="" addedge()="" and="" addarc()="" are="" exactly="" as="" they="" were="" in="" pa2.="" note="" that,="" as="" in="" pa2,="" it="" is="" required="" that="" adjacency="" lists="" are="" always="" processed="" in="" increasing="" order="" by="" vertex="" label.="" it="" is="" the="" responsibility="" of="" functions="" addedge()="" and="" addarc()="" to="" maintain="" adjacency="" lists="" in="" sorted="" order.="" function="" dfs()="" will="" perform="" the="" depth="" first="" search="" algorithm="" on="" .="" the="" list="" argument="" has="" two="" purposes="" in="" this="" function.="" first="" it="" defines="" the="" order="" in="" which="" vertices="" are="" to="" be="" processed="" in="" the="" main="" loop="" (5-7)="" of="" dfs.="" second,="" when="" dfs="" is="" complete,="" it="" will="" store="" the="" vertices="" by="" decreasing="" finish="" times="" (hence="" is="" considered="" to="" be="" a="" stack).="" thus="" can="" be="" classified="" as="" both="" an="" input="" and="" output="" parameter="" to="" function="" dfs().="" you="" should="" utilize="" the="" list="" module="" from="" pa1="" to="" implement="" and="" the="" adjacency="" lists="" representing="" g.="" dfs()="" has="" two="" preconditions:="" (i)="" length(?)="=" ,="" and="" (ii)="" s="" contains="" some="" permutation="" of="" the="" integers="" {1,="" 2,="" …="" ,="" }="" where="" =="" getorder(?).="" you="" are="" required="" to="" check="" the="" first="" precondition="" but="" not="" the="" second.="" recall="" dfs()="" calls="" the="" recursive="" algorithm="" visit()="" (referred="" to="" as="" dfs-visit()="" in="" the="" text),="" and="" uses="" a="" variable="" called="" time="" that="" is="" static="" over="" all="" recursive="" calls="" to="" visit().="" observe="" that="" this="" function="" is="" not="" mentioned="" in="" the="" above="" catalog="" (graph.h)="" and="" therefore="" is="" to="" be="" considered="" a="" private="" helper="" function="" in="" graph.c.="" there="" are="" at="" least="" three="" possible="" approaches="" to="" implementing="" visit().="" you="" can="" define="" visit()="" as="" a="" top-level="" function="" in="" graph.c="" and="" let="" time="" be="" a="" global="" variable="" whose="" scope="" is="" the="" entire="" file.="" this="" option="" has="" the="" drawback="" that="" other="" functions="" in="" graph.c="" have="" access="" to="" time="" and="" would="" be="" able="" to="" alter="" its="" value.="" for="" this="" reason,="" global="" variables="" are="" generally="" considered="" to="" be="" a="" poor="" programming="" practice.="" the="" second="" approach="" is="" to="" let="" time="" be="" a="" local="" variable="" in="" dfs(),="" then="" pass="" the="" address="" of="" time="" to="" visit(),="" making="" it="" an="" input-output="" variable="" to="" visit().="" this="" is="" perhaps="" the="" simplest="" option,="" and="" is="" recommended.="" the="" third="" approach="" is="" to="" again="" let="" time="" be="" a="" local="" variable="" in="" dfs(),="" then="" nest="" the="" definition="" of="" visit()="" within="" the="" definition="" of="" dfs().="" since="" time="" is="" local="" to="" dfs(),="" its="" scope="" includes="" the="" defining="" block="" for="" visit()="" and="" is="" therefore="" static="" throughout="" all="" recursive="" calls="" to="" visit().="" this="" may="" be="" tricky="" if="" you’re="" not="" used="" to="" nesting="" function="" definitions="" since="" there="" are="" issues="" of="" scope="" to="" deal="" with.="" if="" you="" pick="" this="" option,="" first="" experiment="" with="" a="" few="" examples="" to="" make="" sure="" you="" know="" how="" it="" works.="" note="" that="" although="" nesting="" function="" definitions="" is="" not="" a="" feature="" of="" standard="" c,="" and="" is="" not="" supported="" by="" many="" compilers,="" it="" is="" supported="" by="" the="" gnu="" gcc="" compiler="" (see="" https://gcc.gnu.org/onlinedocs/gcc/nested-functions.html.)="" there's="" actually="" a="" fourth="" option="" for="" implementing="" time="" that="" may="" be="" the="" easiest="" of="" all.="" just="" give="" visit()="" its="" own="" local="" copy="" of="" time,="" then="" let="" it="" take="" the="" current="" value="" of="" time="" as="" input,="" and="" return="" the="" new="" value="" of="" time="" when="" it's="" done.="" no="" global="" variable,="" no="" passing="" by="" reference="" and="" no="" nested="" function="" definitions.="" these="" design="" decisions="" are="" left="" to="" you,="" and="" are="" the="" type="" of="" thing="" that="" should="" be="" stated="" in="" your="" readme="" file.="" https://gcc.gnu.org/onlinedocs/gcc/nested-functions.html="" function="" transpose()="" returns="" a="" reference="" to="" a="" new="" graph="" object="" representing="" the="" transpose="" of="" g,="" and="" copygraph()="" returns="" a="" reference="" to="" a="" new="" graph="" that="" is="" a="" copy="" of="" g.="" both="" transpose()="" and="" copygraph()="" may="" be="" considered="" constructors="" since="" they="" create="" new="" graph="" objects.="" function="" printgraph()="" prints="" the="" adjacency="" list="" representation="" of="" g="" to="" the="" file="" pointed="" to="" by="" out.="" obviously,="" there="" is="" much="" in="" common="" between="" the="" graph="" module="" in="" this="" project="" and="" the="" one="" in="" pa2.="" if="" you="" wish,="" you="" may="" simply="" add="" functionality="" necessary="" for="" this="" project="" to="" the="" previous="" one,="" although="" it="" is="" not="" required="" that="" you="" do="" so.="" you="" should="" make="" note="" of="" choices="" such="" as="" this="" in="" your="" readme="" file.="" the="" client="" of="" your="" graph="" module="" will="" be="" called="" findcomponents.="" it="" will="" take="" two="" command="" line="" arguments="" giving="" the="" names="" of="" the="" input="" and="" output="" files="" respectively:="" $="" findcomponents="" infile="" outfile="" findcomponents.c="" will="" do="" the="" following:="" •="" read="" the="" input="" file.="" •="" assemble="" a="" graph="" object="" using="" newgraph()="" and="" addarc().="" •="" print="" the="" adjacency="" list="" representation="" of="" g="" to="" the="" output="" file.="" •="" run="" dfs="" on="" and="" ,="" processing="" the="" vertices="" in="" the="" second="" call="" by="" decreasing="" finish="" times="" from="" the="" first="" call.="" •="" determine="" the="" strong="" components="" of="" .="" •="" print="" the="" strong="" components="" of="" to="" the="" output="" file="" in="" topologically="" sorted="" order.="" after="" the="" second="" call="" to="" dfs(),="" the="" list="" parameter="" s="" can="" be="" used="" to="" determine="" the="" strong="" components="" of="" g,="" and="" to="" determine="" a="" topological="" sort="" of="" those="" components.="" you="" should="" trace="" the="" algorithm="" strongly-="" connected-components="" (p.617)="" on="" several="" small="" examples,="" keeping="" track="" of="" the="" list="" s="" to="" see="" how="" this="" can="" be="" done.="" input="" and="" output="" file="" formats="" are="" illustrated="" in="" the="" following="" example,="" which="" corresponds="" to="" the="" directed="" graph="" on="" the="" first="" page="" of="" this="" handout:="" input:="" 8="" 1="" 2="" 2="" 3="" 2="" 5="" 2="" 6="" 3="" 4="" 3="" 7="" 4="" 3="" 4="" 8="" 5="" 1="" 5="" 6="" 6="" 7="" 7="" 6="" 7="" 8="" 8="" 8="" 0="" 0="" output:="" adjacency="" list="" representation="" of="" g:="" 1:="" 2="" 2:="" 3="" 5="" 6="" 3:="" 4="" 7="" 4:="" 3="" 8="" 5:="" 1="" 6="" 6:="" 7="" 7:="" 6="" 8="" 8:="" 8="" g="" contains="" 4="" strongly="" connected="" components:="" component="" 1:="" 1="" 5="" 2="" component="" 2:="" 3="" 4="" component="" 3:="" 7="" 6="" component="" 4:="" 8="" observe="" that="" the="" input="" file="" format="" is="" very="" similar="" to="" that="" of="" pa2.="" the="" first="" line="" gives="" the="" number="" of="" vertices="" in="" the="" graph,="" subsequent="" lines="" specify="" directed="" edges,="" and="" input="" is="" terminated="" by="" the="" ‘dummy’="" line="" 0="" 0.="" you="" are="" required="" to="" submit="" the="" following="" eight="" files:="" readme="" makefile="" list.h="" list.c="" graph.h="" graph.c="" graphtest.c="" findcomponents.c="" as="" usual="" readme="" contains="" a="" catalog="" of="" submitted="" files="" and="" any="" special="" notes="" to="" the="" grader.="" makefile="" should="" be="" capable="" of="" making="" the="" executables="" graphtest="" and="" findcomponents="" and="" should="" contain="" a="" clean="" utility="" that="" removes="" all="" binary="" files.="" graph.c="" and="" graph.h="" are="" the="" implementation="" and="" interface="" files="" respectively="" for="" your="" graph="" module.="" graphtest.c="" will="" contain="" your="" own="" tests="" of="" your="" graph="" module.="" findcomponents.c="" implements="" the="" top-level="" client="" and="" main="" program="" for="" this="" project.="" to="" get="" full="" credit,="" your="" project="" must="" implement="" all="" required="" files="" and="" functions,="" compile="" without="" errors="" or="" warnings,="" produce="" correct="" output="" on="" our="" unit="" tests,="" and="" produce="" no="" memory="" leaks="" under="" valgrind.="" by="" now="" everyone="" knows="" that="" points="" are="" deducted="" both="" for="" neglecting="" to="" include="" required="" files,="" for="" misspelling="" any="" filenames="" and="" for="" submitting="" additional="" unwanted="" files="" but="" let="" me="" say="" it="" anyway:="" do="" not="" submit="" binary="" files="" of="" any="" kind.="" note="" that="" findcomponents.c="" needs="" to="" pass="" a="" list="" to="" the="" function="" dfs(),="" so="" findcomponents.c="" is="" also="" a="" client="" of="" the="" list="" module.="" in="" fact,="" any="" client="" of="" graph="" is="" also="" a="" client="" of="" list="" just="" by="" the="" presence="" of="" the="" list="" parameter="" to="" dfs().="" therefore="" graph.h="" should="" itself="" #include="" the="" file="" list.h.="" (see="" the="" handout="" entitled="" c="" header="" file="" guidelines="" for="" more="" on="" this="" topic.)="" a="" makefile="" for="" this="" project="" will="" be="" posted="" on="" the="" course="" webpage="" which="" you="" may="" alter="" as="" you="" see="" fit.="" as="" usual="" start="" early="" and="" ask="" questions="" if="" anything="" is="" not="" completely="" clear.="" 2023/2/2="" 13:59="" https://people.ucsc.edu/~ptantalo/cse101/winter23/examples/pa3/graphclient.c="" https://people.ucsc.edu/~ptantalo/cse101/winter23/examples/pa3/graphclient.c="" 1/2="" -----------------------------------------------------------------------------="" graphclient.c="" test="" client="" for="" the="" graph="" adt="" -----------------------------------------------------------------------------="">
#include #include"List.h" #include"Graph.h" int main(int argc, char* argv[]){ int i, n=8; List S = newList(); Graph G = newGraph(n); Graph T=NULL, C=NULL; for(i=1; i<=n; i++) append(s, i); addarc(g, 1,2); addarc(g, 1,5); addarc(g, 2,5); addarc(g, 2,6); addarc(g, 3,2); addarc(g, 3,4); addarc(g, 3,6); addarc(g, 3,7); addarc(g, 3,8); addarc(g, 6,5); addarc(g, 6,7); addarc(g, 8,4); addarc(g, 8,7); printgraph(stdout, g); dfs(g, s); fprintf(stdout, "\n"); i++)="" append(s,="" i);="" addarc(g,="" 1,2);="" addarc(g,="" 1,5);="" addarc(g,="" 2,5);="" addarc(g,="" 2,6);="" addarc(g,="" 3,2);="" addarc(g,="" 3,4);="" addarc(g,="" 3,6);="" addarc(g,="" 3,7);="" addarc(g,="" 3,8);="" addarc(g,="" 6,5);="" addarc(g,="" 6,7);="" addarc(g,="" 8,4);="" addarc(g,="" 8,7);="" printgraph(stdout,="" g);="" dfs(g,="" s);="" fprintf(stdout,="">