# Implement concurrent and distributed algorithm for computing various statistics on large graphs with colored nodes.

erlang exercise and need the explanation and answer to help me learn.

Hey, please provide the solution exactly in the format as asked in the question. Use Erlang language and do remember that the solution should work for various different test cases. Thanks.

Requirements:

Programming Languages Programming Assignment #2Graph StatisticsYou are to implement a concurrent algorithm for computing various statistics on potentially large graphs with colored nodes.Graphs are a relational data-structure where we dene a set of nodes and edges, representing some objects and a relationship between them. These graphs can be used to model any number of problems, from the power grid to social networks.Computing statistics on large graphs becomes more computationally expensive as the number of nodes and edges increase. For applications that run on graphs with the scale of the Internet, it becomes intractable to process the entire graph on a single machine. One solution to this problem of increasing graph sizes is to distribute the computation across multiple processing nodes, dividing the massive graph problem into manageable chunks and combining results from local computations.For this assignment, you will be given an undirected graph G that contains varying amounts of colored nodes. This graph will be provided to you already split into P partitions, each of which will be handled by its own actor Ap. Each partition consists of a set of unique nodes from G and all edges connected to those nodes. With these partitions the assignment is broken into two parts:a)YouwillcountthetotalnumberofnodesofeachcolorinG,aswellasgetthesumofthedegreeofallnodesofeachcolor.b)Youwillnd,foreachpartition,themostin

uentialnode(thenodewiththehighestdegree)thatiseitherinthepartition,ordirectlyconnectedtothepartition.AnexampleinputgraphisshowninFigure1.Thisgraphof12nodesisdividedequallybetween3actorsA0;A1;A2.Eachactorhasitsownlocalpartitioncontainingfourinternalnodesaswellasalltheedgesconnectedtothoseinternalnodes.Eachactormayhaveedgesthatcontainnodesthatarenotwithintheirinternalnodelist.Theseexternalnodes,whicharegreyinFigure1,arenecessarytocomputethedegreeinparta)andthemostin

uentialnodeinpartb),buttheactorisnotdirectlyresponsibleforcomputingthecolorstatisticsoftheseexternalnodes.A.ColorCountandDegreeTherstpartoftheassignmentwillhaveyoucomputetwostatisticsontheinputgraphG.Youwillrstcomputethetotalnumberofnodesthereareofeachcolorinthegraph.Thenyouwillndthedegreeofeachcolorinthegraph,wherethedegreeofacolorisequaltothesumofthedegreesofallnodesofthatcolor.Thedegreeofanodeisdenedasthetotalnumberofedgesitbelongsto.Forexample,youwillbeprovidedsomegraphGthathasbeensplitintoPpartitionsfg0;g1;:::;gPg.Eachofthesepartitionswillbehandledbyanactor,Ap,whichwillberesponsibleforcomputingthecountanddegreeofeachcolorinitslocalpartitiongp.ThisactorApwillalsoberesponsibleforreturningtheselocalcount/degreestatisticstoarequestingactor.TheresultsfromallactorscanbeaggregatedintothefullresultsforgraphG.Tosummarizethetasksofparta),eachactorisresponsibleforthreetasksinthisprogram:Countthenumberofnodesofeachcolorinthelocalpartitiongp.Foreachcolorcinthelocalpartition,sumthedegreeofthenodesofthatcolor(wherethedegreeofanodeisequaltothenumberofedgesitbelongsto).Returnthenodecountanddegreeofeachcolorinthelocalpartition.1

Figure1:Graphdividedamongstactors.blue,4,14green,4,14red,4,14Figure2:PartAoutputle.Thecoloroutputleliststhecountandtotaldegreeofthenodesforeachcolorinthegraph.Foreachcolorwewilloutputoneline,commaseparated,thatshowsthecolor,thenumberofnodesofthecolorandthedegreeofthecolor.TheexpectedoutputforFigure1’sgraphisshownhere.Theexpectedoutputofparta)willbeonele,thenamedenedasaninputparameter,containingthecombinedresultsofeachactor.Theseresultswillshowthecolorcountsandcolordegreesforeachcolorinthegraph.TheformatofthisleisshowninFigure2.Theseresultscanappearinanyorder.B.MostIn

uentialNodeThesecondpartofyourassignmentistondthemostin

uentialnodesconnectedtoeachpartitiongp.Themostin

uentialnodeforanactorApisthenodewiththehighestdegreethatiseitherinpartitiongpordirectlyconnectedtopartitiongp.EachactorApwillberesponsiblefordoingthefollowing:GetthedegreeofeachinternalnodeofAp.FindthelistofexternalnodesconnectedtoAp.(AnynodeintheedgelistthatisnotinthenodelistisanexternalnodeofAp)Foreachexternalnoden,messageallotheractorsrequestingthedegreeofnoden.(Anactorshouldreturn0ifnodendoesnotexistintheirlocalpartition).Findthelargestdegreenode(s)fromamongtheinternalandexternalnodesofactorAp.Iftherearemultiplenodesofthesamemaxdegree,returnallsuchnodes.Theoutputforpartb)shouldbeatextlecontainingonelineperactor,plusonefortheglobalgraphG.Eachlinewillprintthepartitionnumberandthelistofmostin

uentialnodesinorconnectedtothepartition.Thenal2

linewillprintGandthenthelistofmostin

uentialnodesintheentirecombinedgraph.AsampleofthisoutputcanbeseeninFigure3.partition0:0,1,4,9partition1:1,4,5,8partition2:0,5,8,9G:0,1,4,5,8,9Figure3:PartBSampleOutput.TheoutputofpartBisalistofnodesperpartitionandonefortheentiregraphG.Thislistcontainsthemostin

uentialnodesineachpartitionofthegraph,aswellasthemostin

uentialnodesofthegraphasawhole.TheexpectedoutputforFigure1’sgraphisshownhere.SampleInputTheinputtoyourprogramwillbeatextledeningtheedgesbelongingtoeachpartitionaswellasalistofcolorspernode.Figure4showswhattheinputleforthegraphdenedinFigure1lookslike.partition00,1,2,3blue,green,blue,red0,10,20,31,21,32,30,91,4partition14,5,6,7green,red,green,green4,54,64,75,65,76,74,15,8partition28,9,10,11red,blue,blue,red8,98,10,8,119,109,1110,118,59,0Figure4:Inputle.Theinputleisbrokenintogroupsofnodesandedgesdeningeachpartition.Theleisgroupedintosetsof4lines,eachdeningalltheinformationneededbyapartitionactor.Line1thepartition/actornumber.Line2showsallthenodesintheactor’slocalgraphpartition.Line3showsthecolorassignedtoeachofthosenodes.Andline4givesaspaceseparatedlistofedgesfortheactor’slocalpartition.ThispatternrepeatsforallgraphpartitionsP.Thegraphprovidedtoyouwillbeanundirectedgraphwithnoselfedges.Youcanexpectallpartitionandnodenamestobeintegersandthattheinputleswillcontainnoerrors(likeduplicatenodes/edges,undirected/selfedges,ormismatchingnodelist/colorlistsize).RequirementsYoursubmissionwillconsistoftwomodules,oneforalocalconcurrentimplementationofthesolu-tion,andtheotherforadistributedsolution.Werecommendyouimplementtheconcurrentsolutionrstandthenmodifythatcodeintothedistributedsolution.Alloutputshouldbewrittenintothesamedirectoryasyourproject.Yourprogramshouldbeabletoworkforanynumberofactorsandvariousnumbersofactorswillbetested.3

NotesforErlangProgrammersTostartyourErlangimplementation,rstcreatenewdirectoriesandlesinthefollowingstructure.FeelfreetocreateadditionalErlanglestohelpwithyourimplementation..|–concurrent||–graph_stats.erl|–distributed||–graph_stats.erl|–input.txt|–README.mdBeginbyimplementingyourconcurrentprograminconcurrent/graphstats.erl.Onceyouhavenishedtheconcurrentversion,copyyourcodeandpasteitintothelelocatedatdistributed/graphstats.erl.Proceedtomodifyyourcodeintothedistributedsolution.Inboththeconcurrentanddistributedgraphstats.erlle,youmustincludeafunctioncalledstartthattakesthreeparameters,theinputlename,theParta)outputlename,andthePartb)outputlename.Runningthisfunctionwillwritetheresultsofyourcomputationtothetwooutputles.PleasealsoexportthestartfunctionsoitcanberunfromanotherErlangprogram.Hereisanexampleofthestartfunctiondeclaration.-export([start/3]).start(Input_file_path,Part_a_output_file_path,Part_b_output_file_path)->%YourcodestartshereRuningtheconcurrentimplementationTorunyourErlangconcurrentprogram,rstgototheconcurrentdirectory,theexecutethefollowing:/**LaunchtheErlangshell*/erl/**Intheerlangshell,compileallfiles,thenrunthestartfunctioningraph_stats.erl*/c(“graph_stats”),graph_stats:start(“../input.txt”,”a_output.txt”,”b_output.txt”).RuningthedistributedimplementationTorunthedistributedsolution,multiplenodesneedtobecreated.Eachgraphpartitionrequiresanewnode.Addi-tionally,anodeisrequiredfortheparent.Youshouldnameyournodesusingtheformatchild

Usingadictionarymightbehelpfulforstoringyourcomputedstatistics.InErlang,thenodename’stypeisanatom.Toconvertastringtoanatom,uselisttoatomfunction.Submission guidelinesGrading: This assignment will be graded mostly on the correctness of the output for each given graph. As always, code clarity / readability is important, and will be a factor in your nal grade.Submission Requirements: Please submit a zip le with your solutions in two separate directories, con-current and distributed, plus a README le at the top-level directory. README les must be in plain text; markdown is acceptable. Your zip le should be named with your LMS user name(s) and chosen language as the lename, eg, userid1 userid2 erlang.zip. In the README le, place the names of each group member (up to two). Your README le should also have a list of specic features / bugs in your solution.Do not include unnecessary les. Test your archive after uploading it. Name your source les appropriately: graph_stats.erl .6