Quick Guide to Graph Traversal Analysis | by Riccardo Di Sipio

Traversing a graph means exploring its structure by visiting the nodes according to some systematic rule. The most effective rule depends on the type of graph ... GetstartedOpeninappSigninGetstartedFollow612KFollowers·Editors'PicksFeaturesDeepDivesGrowContributeAboutGetstartedOpeninappQuickGuidetoGraphTraversalAnalysisAnalyzinggraphstofindoptimalpathsdoesn’thavetobehardRiccardoDiSipioMay11,2021·3minreadAgraphisadatastructurecomposedofasetofobjects(nodes)equippedwithconnections(edges)amongthem.Graphscanbedirectediftheconnectionsareorientedfromonenodetoanother(e.g.AliceowesmoneytoBob),orundirectediftheorientationisirrelevantandtheconnectionsjustrepresentrelationships(e.g.AliceandBobarefriends).Agraphissaidtobecompleteifallnodesareconnectedtoeachother.Adirectedgraphwithnoloopsissaidtobeacyclic.Atreeisanundirectedgraphinwhichanytwonodesareconnectedbyexactlyoneedge.Theinitialnodeinatreeiscalledroot,andterminalnodes(i.e.nodeswithnodownstream-connectednodes)arecalledleaves.Afewpracticalexamplesofgraphsarefriendshipnetworks(e.g.onsocialmedia),genealogical(family)trees,molecules,particlesproducedattheLargeHadronCollider,acompany’sorganizationalchart.Canyoutellwhichcategoryofgraphsdotheybelongto?MainGraphTraversalAlgorithmsTraversingagraphmeansexploringitsstructurebyvisitingthenodesaccordingtosomesystematicrule.Themosteffectiveruledependsonthetypeofgraphandtheproblemathandsoit’snotpossibletomaketrulygeneralstatements.Sincemanydatastructuresincomputersciencehaveanunderlyinggraphthatisatree,it’sworthspendingsomeefforttounderstandbetterthestrategiestoexploresuchagraphinordertofindpathsornodesthatsatisfytheconditionsoftheproblemathand.Inmanycases,theproblemcanbereducedtoastatementsuchas“findthepathbetweennodeAandBsuchthatacertainquantityisoptimized”.Thequantitymaybeforexamplethenumberofedges(i.e.thelengthofthepath),orthesumofacertainfeature(possiblybinary)associatedtoeachnode.TwomainapproachesarecalledDepth-FirstSearch(DFS)andBreadth-FirstSearch(BFS).IntheBFSapproach,nodesatthesamedepthlevelareexploredsequentially,untilthestoppingconditionisfulfilled.Itmakesuseofaqueuetofindtheshortestpathwithaniterativeapproach.BFSusuallytakesuplotsofmemorybecauseoneneedstomaintainanadditionaldatastructurecontainingthenodesyettoexplore,oftenintheformofa“alreadyvisited”booleanvariable.BFSisoftenthebestapproachwhenthedepthofthetreeisnotbalancedorifthesearchnodeisnottoofarfromtheroot(“shallowtree”).Atypicalexampleisasocialnetworkwherewewanttosearchforpeoplewhohavesimilarinterestsofaspecificperson.There’sagoodchancethatthetargetnodesaredirectfriendsorfriendsoffriends,i.e.therootnodecanhavemanybranchings,butthetargetsarejustafewedgesaway.TheDFSalgorithmexploresthegraphbygoingfromtheroottoaleaf,andrepeattheoperationuntiltheconditionissatisfied.Itmakesuseofastacktofindtheshortestpath.Ifagivenbranchdoesn’tfulfilltherequest,thealgorithm“backtracks”tothehigherlevelandthengoesdownanotherpath.Ifarecursiveapproachisused,lessmemoryisneededasonedoesn’thavetokeeptrackofthenodesthathavebeenalready“visited”.DFSisusuallyaneffectiveapproachincasethetreerepresentsaseriesofdecisionsand/orthetargetleafisfarfromtheroot.Atypicaluse-caseexampleisthesimulationofgamessuchaschess,inwhichateachiterationstherearefewpossibilitiesbuteachdecisiongoesfarintermsofnextmoves.CodeExamplesAfewlinesofcodeareoftenmoreexplicativethanlotsoftext.Inthefollowing,we’llexploreasimplegraphmadeof6nodesand5edges.ThestructureofthegraphusedintheexamplesbelowDepth-FirstSearchExpectedoutput:AA->BB->DB->EA->CC->FBreadth-FirstSearchExpectedoutput:ABCDEFRuleofThumbShortestpathonsimplegraph->BFSLowwidth,largedepth->BFSLargewidth,lowdepth->DFS(recursionstackwillnotoverflow)Scanallpossibleresults->DFSRiccardoDiSipioNLPMachineLearningengineeratCeridian.PreviouslysmashingprotonsattheCERNLHC.Viewsaremyown.Follow1111 11GraphAlgorithmsDataStructuresTreesComputerScienceMorefromTowardsDataScienceFollowYourhomefordatascience.AMediumpublicationsharingconcepts,ideasandcodes.ReadmorefromTowardsDataScienceMoreFromMediumMyFirstForayintoaDataScienceCompetitionPederNorrInterpretingtheOLSsummariesinPythonusingPandasandstatsmodelCelBroomheadWhatisDecisiontreeandhowitworks?AkashNHForecastingsoftwareproject’scompletiondatethroughMonteCarloSimulationLucasColucciinTowardsDataScienceDataScienceonWhyReadingtheNewsMightStressYouOutASamuelPottingerinTowardsDataScienceBestmetricforRegression ?RMSE,MSE,MAE,R2NicolasMaurer“Haberman’sCancerSurvival”ExploratoryDataAnalysis_PythonManjunathTOnBuildingaDataScienceTeam,PartIShayStrong