Arbres

Visualiser un arbre

Le but du TP est d'afficher dans une image png l'arborescence d'un répertoire

Comme répertoire particulier on va prendre celui du logiciel filius

Voici une partie de l'arborescence des fichiers et sous-répertoires du répertoire filius

Pour réaliser cela on va utiliser un module de Python nommé graphviz dont voici l'API

Dans un premier temps on va découvrir ce module sur un exemple simple

A partir de la classe Noeud vue en cours pour construire les arbres binaires créer "à la main" l'arbre ci-dessus en complétant le code ci-dessous

    arbre = Noeud(1,Noeud(2,...),...)
    

On va ensuite parcourir en largeur l'arbre binaire arbre pour créer un objet Digraph (directed graph pour graphe orienté)ce qui nous permettra de visualiser l'arbre binaire

Pour parcourir en largeur l'arbre on va utiliser une file toute prête de Python provenant du module collections de Python

Lire et comprendre le passage concernant les files (deque pour double ended queue)

Ensuite entrer le code suivant (on parcourt en largeur l'arbre arbre et on crée en même temps l'objet Digraph en créant les noeuds et les arêtes

import graphviz
from collections import deque
import os
def cree_graphviz(arbre):
    """
     arbre est non vide
    """
    f = deque()
    g = graphviz.Digraph(format='png')
    f.appendleft(arbre)
    while len(f) > 0:
        x = f.pop()
        g.node(str(x.valeur))
        if x.gauche is not None:
            g.node(str(x.gauche.valeur))
            g.edge(str(x.valeur),str(x.gauche.valeur))
            f.appendleft(x.gauche)
        if x.droit is not None:
            g.node(str(x.droit.valeur))
            g.edge(str(x.valeur),str(x.droit.valeur))
            f.appendleft(x.droit)
    g.view()             

arbre = Noeud(1,Noeud(2,...),...)
cree_graphviz(arbre)

Vous devez ensuite obtenir cette image png

Qu'en pensez vous ?

Lister les fichiers d'un répertoire

On va utiliser du module os de Python (pour operating system), les méthodes suivantes

1. os.path.isdir(nom_fichier) qui retourne Vraie si le fichier nommé nom_fichier est un répertoire (directory), et Faux sinon

   Attention! img est un sous-répertoire du répertoire filius os.path.isdir('img') retourne Faux, il faut exécuter os.path.isdir(os.path.join('filius','img')) la fonction os.path.join(pere,enfant) relie le nom du repertoire pere au nom du fichier enfant

   
2. os.listdir(nom_repertoire) retourne une liste de chaînes de caractères les noms des fichiers et sous-répertoires

Se familiariser avec ces deux fonctions avec les fichiers et sous-répertoires du répertoire filius

Visualiser les fichiers du répertoire Filius

L'arborescence des fichiers n'est pas un arbre binaire car certains répertoires ont plus de deux successeurs, on va donc utiliser une nouvelle classe Noeud2,dont les attributs sont

• valeur de type str
• enfants de type list, contenant des objets de type Noeud2

class Noeud2:
    def __init__(self,v,e):
        """
        e est une liste de Noeuds2
        """
        self.valeur = v
        self.enfants = e

Compléter le code de la fonction récursive suivante pour créer l'arborescence du répertoire nommé filius

Cette fonction retournera un arbre de type Noeud2

def cree_arborescence(pere,f):
    
    if not os.path.isdir(os.path.join(pere,f)):
        return .... 
    else:
        liste = os.listdir(os.path.join(pere,f))
        enfants = []
        for elt in liste:
            noeud = ... 
            enfants.append(noeud)
            x = Noeud2(f,enfants)
        return x

Pour visualiser l'arborescence obtenue, s'inspirer de la fonction cree_graphviz(arbre) pour créer cree_graphviz2(arbre) car l'arbre n'est pas binaire

Finalement exécuter (ici le répertoire filius est contenu dans le répertoire Documents (adapter à votre situation)) et vous observerez l'arborescence de tous les fichiers et sous-répertoires du répertoire filius

arbre = cree_arborescence('Documents','filius')
cree_graphviz2(arbre)