T – 4 – Implémenter les graphes | Cercles informatiques

Exercices

1. Implémenter un graphe simple

Nous allons utiliser cette première implémentation pour modéliser un graphe orienté simple.

Exercice de code : implémentation des graphes avec un dictionnaire

En utilisant l'implémentation de l'exemple précédant, créez le dictionnaire G correspondant au graphe ci-dessous. Votre code doit afficher le dictionnaire correspondant à ce graphe. (pour plus de lisibilté, certaines primitives de l'exemple précédent -non requise pour cet exercice- ont été omises)

def  creerGrapheVide() -> dict:
     return {}
def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int
    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'
    G[s]=[]
def ajouterArc(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int
    assert sd in G ,'le graphe ne contient pas le sommet de départ'
    assert sa in G ,'le graphe ne contient pas le sommet d arrivée'
    G[sd].append(sa)
def supprimerSommet(G : dict , s ) -> dict : #s peut être str ou int
    assert s in G,'le graphe ne contient pas le sommet '
    del G[s]
    for sommet in G.keys() :
        if s in G[sommet] :
            G[sommet].remove(s)
def supprimerArc(G : dict ,sd , sa ) -> dict: #sd et sa peuvent être str ou int
    assert sd in G,'le graphe ne contient pas le sommet de départ'
    assert sa in G,'le graphe ne contient pas le sommet d arrivée'
    assert sa in G[sd] , 'l arc  n existe pas.'
    G[sd].remove(sa)
def existeSommet(G : dict , s ) -> bool:
    return s in G
def existeArc(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int
    return sd in G and sa in G and sa in G[sd]

G=creerGrapheVide()
# complétez ici
# les lignes de code ci-dessous sont requises pour la validation :
for cle in G.keys() :
       G[cle] = sorted(G[cle])
print(str(G))

2.1 Modifier l'implémentation pour modéliser un graphe non orienté (primitives d'ajout)

Vous allez modifier notre première implémentation pour modéliser un graphe non orienté.

Dans la version d'implémentation fournie ci-dessous, on a remplacé la primitives ajouterArc par ajouterArete, mais on a pas modifié le code de cette primitive. Vous devez le faire vous même : dans le cas d'un graphe non orienté, ajouter une arrête SD-SA revient à ajouter SD dans la liste d'ajacence de SA, et SA dans la liste d'adjacence de SD. Le code doit donc faire le travail correctement.
Dans cet exercice nous n'incluerons que les primitives d'ajout de sommets et d'arêtes, les primitives pour retirer seront traitées dans un second temps

Exercice de code : Adapter l'implémentation pour un graphe non orienté

En modifiant l implémentation de l exemple précédant, créez le dictionnaire G correspondant au graphe ci-dessous.Les instructions données en fin de code devraient afficher le dictionnaire correct, si vos primitives ont été modifiées comme attendu.

def  creerGrapheVide() -> dict:
     return {}
def estVideGraphe(G : dict) -> bool :
    return G=={}
def ajouterSommet(G : dict ,s) -> dict: # s peut être str ou int
    G[s]=[]
def ajouterArete(G : dict,sd,sa) -> dict : # sd et sa peuvent être str ou int
    G[sd].append(sa)
def existeSommet(G : dict,s) -> bool: # s peut être str ou int
    return s in G
def existeArete(G : dict,sd,sa) -> bool : # sd et sa peuvent être str ou int
    return sd in G and sa in G[sd]
G=creerGrapheVide()
# complétez ici

# les lignes de code ci-dessous sont requises pour la validation :
for cle in G.keys() :
       G[cle] = sorted(G[cle])
print(str(G))

2.2 Modifier l'implémentation pour modéliser un graphe non orienté (primitives de suppression)

Vous allez compléter l'implémentation pour modéliser un graphe non orienté.

Comme dans l'exercice 2.1, dans la version d'implémentation fournie ci-dessous, on a remplacé la primitive supprimerArc par supprimerArete, mais on a pas modifié le code de cette primitive. Vous devez le faire vous même : dans le cas d'un graphe non orienté, supprimer une arrête SD-SA revient à modifier les listes d'adjacence des deux sommets SD et SA. Le code doit donc faire le travail correctement.
Dans cet exercice nous n'incluerons que les primitives de suppression, nous allons générer pour vous un objet graphe qui sera utilisé pour tester votre code. Vous devez coder supprimerSommet et supprimerArete et utiliser ces 2 primitives pour supprimer le sommet 'A' et l’arête 'B-C' du graphe généré par le système.

Exercice de code : Adapter l'implémentation pour un graphe non orienté (partie 2)

Modifiez les primitives supprimerSommet et supprimerArete. Puis utilisez les pour supprimer le sommet A et l'arrête B-C du graphe suivant :
G={'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B','D'], 'D': ['B','C']}
Vous n'avez pas à créer ce dictionnaire G qui sera généré automatiquement en amont de votre code.

def existeSommet(G : dict,s) -> bool: # s peut être str ou int
    return s in G

def existeArete(G : dict ,sd,sa) -> bool : # sd et sa peuvent être str ou int
    return sd in G and sa in G[sd]

def supprimerSommet(G : dict,s) -> dict : # s peut être str ou int
    pass # remplacez cette ligne par votre implémentation (pensez aux assert)

def supprimerArete(G : dict,sd,sa) -> dict : # sd et sa peuvent être str ou int
    pass # remplacez cette ligne par votre implémentation (pensez aux assert)

# insérez ici les instructions pour supprimer A puis supprimer B-D


print(str(G))

3. Modifier de nouveau l'implémentation pour modéliser un graphe pondéré non orienté

Vous allez modifier de nouveau l'implémentation pour modéliser un graphe pondéré et non orienté.

Exercice de code : Graphe pondéré

En modifiant de nouveau l implémentation du graphe, créez le dictionnaire G correspondant au graphe pondéré non orienté ci-dessous.
Attention, ici vous devez modifier les primitives mais aussi les instructions pour créer le graphe attendu.
Les clé resteront les sommets. Pour les listes d’adjacence, au lieu d'une liste de sommets, vous devrez implémenter avec un dictionnaires dont les éléments sont : sommet : poids).
Il faut donc modifier ajouterSommet (la valeur de la clé s doit être un dictionnaire) puis ajouterArete (pour ajouter un dictionnaire, et non plus une liste). supprimerArete devra aussi être modifiée pour tenir comte de la structure différente.

def  creerGrapheVide() -> dict:
     return {}
def estVideGraphe(G: dict) -> bool:
    return G=={}
def ajouterSommet(G : dict,s) : # s est str ou int
    G[s]=[]
def ajouterArete(G : dict , sd , sa) -> dict :  # sd et sa sont str ou int
    G[sd].append(sa)
def supprimerSommet(G : dict , s ) : # s est str ou int
    assert s in G.keys(),'impossible de supprimer un sommet non existant'
    del G[s]
    for sommet in G.keys() :
        if s in G[sommet] :
            G[sommet].remove(s)
def supprimerArete(G : dict , sd , sa) -> dict :  # sd et sa sont str ou int 
    G[sd].remove(sa)
def existeSommet(G : dict , s ) -> bool:  # s est str ou int
    return s in G
def existeArete(G : dict , sd , sa ) -> bool :  # sd et sa sont str ou int
    return sd in G and sa in G[sd]
# Completez également les instructions ci-dessous :
G=creerGrapheVide()
ajouterSommet(G,1)
ajouterSommet(G,2)

# les lignes de code ci-dessous sont requises pour la validation :
if G==G1 :
   print(G1)

Pages : 1 2 3 4