Activités pratiques : Types de données récursives

Pour exécuter les tests, vous devez cliquer sur l’icône à gauche de l’éditeur, puis cliquer sur la double flèche en haut de la vue Tests pour exécuter tous les tests.

À ce stade, vous devriez voir un test échouer, car les classes Person et FamilyTree ne sont pas encore implémentées. Vous allez donc devoir compléter les classes Person et FamilyTree.

1 - Structure récursive

Un arbre généalogique est une structure de données récursive, car chaque personne peut avoir des enfants, qui sont eux-mêmes des personnes. Avant de vous lancer dans la programmation, vous devez réfléchir à la manière dont vous pourriez modéliser un arbre généalogique et les relations qui en découlent en utilisant une structure récursive. Vous devrez considérer le cas récursif ainsi que le(s) cas de base. Cette structure devra permettre d’ajouter, de supprimer et de rechercher des personnes dans l’arbre.

2 - Personne

Vous allez tout d’abord compléter la classe Person qui représentera une personne dans l’arbre généalogique. Cette classe devra contenir les informations suivantes :

• Le nom de la personne, sous la forme d’une chaîne de caractères, nommée name,
• La liste de ses enfants (qui seront également des instances de la classe Person), nommée children,
• Ses deux parents, nommés parent1 et parent2.

Si un parent n’est pas connu, alors il sera défini à None.

class Person:
    """
    Represents a person in the family tree.
    A person has a name, a list of children, and two parents.
    The absence of an ascendant is represented by None.
    """

    def __init__(self, name: str, parent1: 'Person' = None, parent2: 'Person' = None):
        """
        Initializes a new person with the given name and parents.

        :param name: The name of the person.
        :param parent1: The first parent of the person (can be None).
        :param parent2: The second parent of the person (can be None).
        :raises ValueError: If the name is empty.

        Implementation details:
        If parents are provided, the person is added to their children lists.
        """
        if not name:
            raise ValueError("Name cannot be empty.")
        self.name = name

        self.children = []
        self.parent1 = parent1
        self.parent2 = parent2
        # Add this person to the children of the parents
        if parent1 != None: 
            parent1.children.append(self)
        if parent2 != None:
            parent2.children.append(self)
    
    def __repr__(self):
        """
        Returns a string representation of the person.
        """
        return f"Person(name={self.name})"
    
    def __str__(self):
        """
        Returns the name of the person.
        """
        return self.name

3 - Arbre généalogique

Vous allez ensuite ouvrir la classe FamilyTree déclarée dans le fichier genealogy/familytree.py. Elle représente l’arbre généalogique lui-même. Cette classe déclare un constructeur qui initialise les éléments suivants :

• Une instance de Person qui sera la racine de l’arbre, nommée __root,

Vous devez consulter le fichier indiqué et prendre connaissance des méthodes déjà déclarées dans la classe FamilyTree. Vous n’avez pas le droit de changer la signature des méthodes existantes, ceci afin de garantir que les tests fonctionneront correctement. Par contre, vous allez devoir compléter les méthodes existantes, et si besoin, en ajouter de nouvelles. Ceci sera précisé dans les étapes suivantes.

3.1 - Trouver une personne

1. Vous allez maintenant implémenter une méthode find_person(self, name) dans la classe FamilyTree. Cette méthode devra parcourir l’arbre à partir de la racine et retourner l’instance de Person correspondante au nom recherché, ou None si la personne n’est pas trouvée. Cette méthode devra utiliser une approche récursive pour parcourir l’arbre.

def find_person(self, name: str) -> Person:
    """
    Finds a person by name in the family tree.
    Returns the person if found, otherwise None.

    :param name: The name of the person to find.
    :return: The person object if found, otherwise None.
    """
    # Helper function to perform a recursive search
    def _find_person(current: Person, name: str) -> Person:
        """
        Recursively searches for a person by name in the family tree.
        Returns the person if found, otherwise None.

        :param current: The current person being checked.
        :param name: The name of the person to find.
        :return: The person object if found, otherwise None.
        """
        if current.name == name:
            return current
        for child in current.children:
            found = _find_person(child, name)
            if found:
                return found
        return None

    return _find_person(self.__root, name)

2. Vous ajouterez également une méthode contains(self, name) dans la classe FamilyTree qui renverra True si la personne existe dans l’arbre, et False sinon. Cette méthode utilisera la méthode find_person.

def contains(self, name: str) -> bool:
    """
    Checks if a person with the given name exists in the family tree.
    Returns True if found, otherwise False.
    :param name: The name of the person to check.
    :return: True if the person exists, otherwise False.
    """
    return self.find_person(name) != None

3.2 - Ajout de personnes

Vous allez maintenant implémenter une méthode add_person(self, name, parent1=None, parent2=None) dans la classe FamilyTree. Cette méthode devra permettre d’ajouter une nouvelle personne à l’arbre généalogique. Avant toute chose, vous devez vérifier si la personne existe déjà dans l’arbre. Si c’est le cas, vous ne devez pas l’ajouter à nouveau. Si la personne n’existe pas, vous devez l’ajouter à l’arbre. Si des parents sont fournis, la personne sera ajoutée à leurs listes d’enfants. Si aucun parent n’est spécifié, la personne sera ajoutée comme enfant de ROOT, un parent fictif qui n’est pas visible par l’utilisateur de l’arbre généalogique.

Pour alimenter votre arbre généalogique, nous avons fourni un exemple d’arbre généalogique de la famille Simpson. Le code se trouve à la fin du fichier genealogy/familytree.py.

Arbre généalogique de la famille Simpson (src: modelegenealogique.fr)

def add_person(self, name: str, parent1: Person = None, parent2: Person = None) -> Person:
    """
    Adds a person to the family tree.

    :param name: The name of the person to be added.
    :param parent1: The first parent of the person (can be None).
    :param parent2: The second parent of the person (can be None).
    :return: The added person object.
    
    Implementation details:
    If the person already exists, it returns the existing person.
    If no parents are provided, the root stores the person in her children list.
    """
    # Check if the person already exists in the tree
    existing_person = self.find_person(name)
    if existing_person != None:
        return existing_person
    person = Person(name, parent1, parent2)
    if parent1 == None and parent2 == None:
        self.__root.children.append(person)
    return person

3.3 - Grands-parents, frères et sœurs

Vous allez maintenant implémenter deux méthodes supplémentaires:

• get_grandparents(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste des grands-parents de la personne dont le nom est donné en paramètre. Si la personne n’existe pas ou n’a pas de grands-parents, la méthode devra retourner une liste vide.
• get_siblings(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste des frères et sœurs de la personne dont le nom est donné en paramètre. Sont considérés comme frères et sœurs les personnes qui ont au moins un parent en commun avec la personne recherchée. Si la personne n’existe pas ou n’a pas de frères et sœurs, la méthode devra retourner une liste vide.

def get_grandparents(self, name: str) -> list:
    """
    Returns a list of grandparents for the person with the given name.
    If the person does not exist or has no parents, returns an empty list.
    :param name: The name of the person to find grandparents for.
    :return: A list of names of the grandparents.

    Implementation details:
    This method retrieves the grandparents of a person by checking their parents.
    It returns a list of names of the grandparents.
    If the person does not exist or has no parents, it returns an empty list.
    """
    person = self.find_person(name)
    if not person or not person.parent1 and not person.parent2:
        return []
    grandparents = []
    for parent in person.parent1, person.parent2:
        if parent:
            grandparents.extend([parent.parent1, parent.parent2])
    return [grandparent.name for grandparent in grandparents if grandparent]

def get_siblings(self, name: str) -> list[str]:
    """
    Returns a list of siblings for the given person name.
    If the person does not exist, returns an empty list.
    :param name: The name of the person to find siblings for.
    :return: A list of names of the siblings.
    
    Implementation details:
    This method retrieves the siblings of a person by checking their parents.
    It returns a list of names of the siblings.
    If the person does not exist or has no parents, it returns an empty list.
    """
    person = self.find_person(name)
    if not person:
        return []

    siblings = []
    for parent in person.parent1, person.parent2:
        if parent:
            for sibling in parent.children:
                if sibling != person and sibling.name not in siblings:
                    siblings.append(sibling.name)
    return siblings

Pour aller plus loin

Vous pouvez aller plus loin en implémentant les fonctionnalités suivantes :

• Ajouter une méthode get_ancestors(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste de tous les ancêtres de la personne dont le nom est donné en paramètre, en remontant jusqu’à la racine de l’arbre.
• Ajouter une méthode get_descendants(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste de tous les descendants de la personne dont le nom est donné en paramètre, en descendant jusqu’aux feuilles de l’arbre.
• Ajouter une méthode get_family_tree(self, name) dans la classe FamilyTree. Cette méthode devra retourner une représentation textuelle de l’arbre généalogique de la personne dont le nom est donné en paramètre, en incluant tous les ancêtres et descendants de cette personne.
• Ajouter une méthode get_relationship(self, name1, name2) dans la classe FamilyTree. Cette méthode devra retourner le type de relation entre les deux personnes dont les noms sont donnés en paramètres (par exemple, “parent”, “enfant”, “frère/sœur”, “grand-parent”, etc.). Si les deux personnes ne sont pas liées, la méthode devra retourner None.
• etc