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 de ne 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)Youwill nd,foreachpartition,themostin
uentialnode(thenodewiththehighestdegree)thatiseitherinthepartition,ordirectlyconnectedtothepartition.AnexampleinputgraphisshowninFigure1.Thisgraphof12nodesisdividedequallybetween3actorsA0;A1;A2.Eachactorhasitsownlocalpartitioncontainingfourinternalnodesaswellasalltheedgesconnectedtothoseinternalnodes.Eachactormayhaveedgesthatcontainnodesthatarenotwithintheirinternalnodelist.Theseexternalnodes,whicharegreyinFigure1,arenecessarytocomputethedegreeinparta)andthemostin
uentialnodeinpartb),buttheactorisnotdirectlyresponsibleforcomputingthecolorstatisticsoftheseexternalnodes.A.ColorCountandDegreeThe rstpartoftheassignmentwillhaveyoucomputetwostatisticsontheinputgraphG.Youwill rstcomputethetotalnumberofnodesthereareofeachcolorinthegraph.Thenyouwill ndthedegreeofeachcolorinthegraph,wherethedegreeofacolorisequaltothesumofthedegreesofallnodesofthatcolor.Thedegreeofanodeisde nedasthetotalnumberofedgesitbelongsto.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:PartAoutput le.Thecoloroutput leliststhecountandtotaldegreeofthenodesforeachcolorinthegraph.Foreachcolorwewilloutputoneline,commaseparated,thatshowsthecolor,thenumberofnodesofthecolorandthedegreeofthecolor.TheexpectedoutputforFigure1’sgraphisshownhere.Theexpectedoutputofparta)willbeone le,thenamede nedasaninputparameter,containingthecombinedresultsofeachactor.Theseresultswillshowthecolorcountsandcolordegreesforeachcolorinthegraph.Theformatofthis leisshowninFigure2.Theseresultscanappearinanyorder.B.MostIn
uentialNodeThesecondpartofyourassignmentisto ndthemostin
uentialnodesconnectedtoeachpartitiongp.Themostin
uentialnodeforanactorApisthenodewiththehighestdegreethatiseitherinpartitiongpordirectlyconnectedtopartitiongp.EachactorApwillberesponsiblefordoingthefollowing:GetthedegreeofeachinternalnodeofAp.FindthelistofexternalnodesconnectedtoAp.(AnynodeintheedgelistthatisnotinthenodelistisanexternalnodeofAp)Foreachexternalnoden,messageallotheractorsrequestingthedegreeofnoden.(Anactorshouldreturn0ifnodendoesnotexistintheirlocalpartition).Findthelargestdegreenode(s)fromamongtheinternalandexternalnodesofactorAp.Iftherearemultiplenodesofthesamemaxdegree,returnallsuchnodes.Theoutputforpartb)shouldbeatext lecontainingonelineperactor,plusonefortheglobalgraphG.Eachlinewillprintthepartitionnumberandthelistofmostin
uentialnodesinorconnectedtothepartition.The nal2
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.SampleInputTheinputtoyourprogramwillbeatext lede ningtheedgesbelongingtoeachpartitionaswellasalistofcolorspernode.Figure4showswhattheinput leforthegraphde nedinFigure1lookslike.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:Input le.Theinput leisbrokenintogroupsofnodesandedgesde ningeachpartition.The leisgroupedintosetsof4lines,eachde ningalltheinformationneededbyapartitionactor.Line1thepartition/actornumber.Line2showsallthenodesintheactor’slocalgraphpartition.Line3showsthecolorassignedtoeachofthosenodes.Andline4givesaspaceseparatedlistofedgesfortheactor’slocalpartition.ThispatternrepeatsforallgraphpartitionsP.Thegraphprovidedtoyouwillbeanundirectedgraphwithnoselfedges.Youcanexpectallpartitionandnodenamestobeintegersandthattheinput leswillcontainnoerrors(likeduplicatenodes/edges,undirected/selfedges,ormismatchingnodelist/colorlistsize).RequirementsYoursubmissionwillconsistoftwomodules,oneforalocalconcurrentimplementationofthesolu-tion,andtheotherforadistributedsolution.Werecommendyouimplementtheconcurrentsolution rstandthenmodifythatcodeintothedistributedsolution.Alloutputshouldbewrittenintothesamedirectoryasyourproject.Yourprogramshouldbeabletoworkforanynumberofactorsandvariousnumbersofactorswillbetested.3
NotesforErlangProgrammersTostartyourErlangimplementation, rstcreatenewdirectoriesand lesinthefollowingstructure.FeelfreetocreateadditionalErlang lestohelpwithyourimplementation..|–concurrent||–graph_stats.erl|–distributed||–graph_stats.erl|–input.txt|–README.mdBeginbyimplementingyourconcurrentprograminconcurrent/graphstats.erl.Onceyouhave nishedtheconcurrentversion,copyyourcodeandpasteitintothe lelocatedatdistributed/graphstats.erl.Proceedtomodifyyourcodeintothedistributedsolution.Inboththeconcurrentanddistributedgraphstats.erl le,youmustincludeafunctioncalledstartthattakesthreeparameters,theinput lename,theParta)output lename,andthePartb)output lename.Runningthisfunctionwillwritetheresultsofyourcomputationtothetwooutput les.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@127.0.0.1.Forexample,iftherearethreepartitionsintheinput le,thenodenameswouldbechild0@127.0.0.1,child1@127.0.0.1,andchild2@127.0.0.1.TorunyourErlangdistributedprogram, rstgotothedistributeddirectory,thengiventhenumberofnodesneededasn,opennnewterminalsessions.Foreachsession,execute/**Startanode,replacewiththeanumberrangingfrom0ton-1*/erl-namechild@127.0.0.1Thenopenanewterminalwindowfortheparentnode,execute/**Startaparentnode,erlangshellshouldopen*/erl-nameparent@127.0.0.1/**Intheerlangshell,compileandexecute*/c(“graph_stats”),graph_stats:start(“../input.txt”,”a_output.txt”,”b_output.txt”).ErlangTipsForreference,pleaseseetheErlangdocumentationonconcurrency.5
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 speci c 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

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *