ITI0140:Ülesanne 19

Sugulasfilter

Pühad on peagi tulemas ning Jaak otsustas see aasta kõiki oma sugulasi üllatada. Kahjuks ei tunne ta kõiki oma sugulasi ning seetõttu otsustas ta tõmmata sotsiaalvõrgustikest kõik oma tutvused alla, et nende hulgast välja filtreerida sugulased. Eelmisest aastast oli talle juba jäänud perekonna sugupuu graaf, kuid käsitsi oleks see töö tüütu, seega otsustas ta kirjutada algoritmi, mis leiaks, kas inimene on tema sugupuust.

Selleks otsis ta googlest märksõnu "graph search algorithm" ja leidis rekursiivse otsingualgoritmi, mis tundus sobivat. Imelikul kombel see töötas ja tagastas külastatud sõlmede arvu. Jaak oli kuskilt kuulnud, et kõike, mida saab rekursiivselt teha, saab ka iteratiivselt, seega kirjutas ta kiiresti ka iteratiivse variandi ja tegi suure hulga teste veendumaks algoritmi korrektsuses. Testide kirjutamise käigus avastas Jaak järsku, et ta on probleemist kõrvale kaldunud ja tal pole võimalik sellise algoritmiga tuvastada, kas X on tema sugulane, kui X on parempoolse haru kõige viimane element. Selleks, et testid päris ilmaasjata ei oleks, saatis ta need Sulle, et näha, kas Sa suudaksid ka need läbida.

Jaak oli koostanud testid nii, et need töötaks Pythoni NetworkX graafiku abiga.

def find_relative_iterative(graph, name):

    """

    Iterative implementation.

    Find how many nodes are visited during the depth first search.

    The algorithm must work with cycles and look through every node if 

    name doesn't exist in the graph.

    Example graph:

       Mary     <-- find(Tim)  == 5 

       /       \      <-- find(Mary) == 1

    Jane Dane   <-- find(Jane) == 2

     /           \     <-- find(John) == 3

   John   Mike  <-- find(Dane) == 4

                <-- find(Mike) == 5  

   (Assumed that left half is always preferred)

    Args: graph - family tree (networkx graph object)

          name  - searched relative (string)


    Return: number of nodes visited (int)

    """

    pass

def find_relative_recursive(graph, name):

    """

    Recursive implementation.

    Find how many nodes are visited during the depth first search.

    The algorithm must work with cycles and look through every node if 

    name doesn't exist in the graph.

    Example graph:

       Mary     <-- find(Tim)  == 5 

       /      \      <-- find(Mary) == 1

    Jane Dane   <-- find(Jane) == 2

     /          \     <-- find(John) == 3

   John   Mike  <-- find(Dane) == 4

                <-- find(Mike) == 5  

(Assumed that left half is always preferred)

    Args: graph - family tree (networkx graph object)

          name  - searched relative (string)


    Return: number of nodes visited (int)

    """

    pass

if __name__ == "__main__":

    example_graph = nx.Graph()

    example_graph.add_edge("Mari", "Juku")

    print(find_relative_recursive(example_graph, "Mari")) #1

    print(find_relative_iterative(example_graph, "Mari")) #1