#+BEGIN_activite

1. 1. Compléter la définition suivante pour que la fonction mat_adj_vers_dict_succ pour qu'elle retourne un dictionnaire des successeurs représentant le graphe de matrice d'adjacence donnée en arguments

      import numpy as np
      
      def mat_adj_vers_dict_succ(A):
         n, p = A.shape
         assert n == ??
         d = ??
         for i in range(n):
            d[i] = ??
            for j in range(n):
               if A[i,j] == ??:
                  d[??].append(??)
         return ??
      
      def teste_mat_adj_vers_dict_succ():
         A = np.array([[0,1,0], [1,0,0], [0,1,0]])
         d = mat_adj_vers_dict_succ(A)
         assert d[0] == ??
         assert d[1] == ??
         assert d[2] == ??
         A = np.array([[1,1,0], [1,0,1], [0,1,1]])
         d = mat_adj_vers_dict_succ(A)
         assert sorted(d[0])==??
         assert sorted(d[1])==??
         assert sorted(d[2])==??
      
      teste_mat_adj_vers_dict_succ()
      

      import numpy as np
      
      def mat_adj_vers_dict_succ(A):
         n, p = A.shape
         assert n==p
         d = {}
         for i in range(n):
            d[i] = []
            for j in range(n):
               if A[i,j] == 1: # ou A[i,j] != 0
                  d[i].append(j)
         return d
      
      def teste_mat_adj_vers_dict_succ():
         A = np.array([[0,1,0], [1,0,0], [0,1,0]])
         d = mat_adj_vers_dict_succ(A)
         assert d[0] == [1]
         assert d[1] == [0]
         assert d[2] == [1]
         A = np.array([[1,1,0], [1,0,1], [0,1,1]])
         d = mat_adj_vers_dict_succ(A)
         assert sorted(d[0])==[0,1]
         assert sorted(d[1])==[0,2]
         assert sorted(d[2])==[1,2]
      
      teste_mat_adj_vers_dict_succ()
      

   2. Écrire une fonction mat_adj_vers_dict_pred pour qu'elle retourne un dictionnaire des prédecesseurs représentant le graphe de matrice d'adjacence donnée en argument.

      import numpy as np
      
      def mat_adj_vers_dict_pred(A):
         n, p = A.shape
         assert n==p
         d = {}
         for i in range(n):
            d[i] = []
            for j in range(n):
               if A[j,i] == 1: # ou A[j,i] != 0
                  d[i].append(j)
         return d
      
      def teste_mat_adj_vers_dict_pred():
         A = np.array([[0,1,0],
                       [1,0,0],
                       [0,1,0]])
         d = mat_adj_vers_dict_pred(A)
         assert d[0] == [1]
         assert sorted(d[1]) == [0,2]
         assert d[2] == []
         A = np.array([[1,1,0],
                       [1,0,1],
                       [0,1,1]])
         d = mat_adj_vers_dict_pred(A)
         assert sorted(d[0]) == [0,1]
         assert sorted(d[1]) == [0,2]
         assert sorted(d[2]) == [1,2]
      
      teste_mat_adj_vers_dict_pred()
      

2. Vérifier que le code ci-dessous affiche l'image qui lui suit

   import networkx as nx
   import numpy as np
   import matplotlib.pyplot as plt
   from networkx.drawing.nx_pydot import graphviz_layout
   
   def draw_weighted_digraph_dict_of_dict(graph, layout="spring_layout", root=None):
       graph_for_nx = {
           n: {
               succ: {"weight": weight} for succ, weight in d.items()
           } for n, d in graph.items()
       }
       G = nx.DiGraph(graph_for_nx)
       if layout == "spring_layout":
           pos = nx.spring_layout(G, seed=5) # seed for reproducible plots...
       else:
           pos = graphviz_layout(G, prog=layout, root=root)
       nx.draw(G, pos, with_labels=True, font_weight='bold')
       edge_labels = nx.get_edge_attributes(G,"weight")
       nx.draw_networkx_edge_labels(G, pos,
                                    edge_labels = edge_labels,
                                    font_weight='bold')
   
   graph = {
       'A' : {'B': 5, 'C': 2},
       'B' : {'C': 1},
       'C' : {'A': 3, 'B': 8}
   }
   draw_weighted_digraph_dict_of_dict(graph)
   plt.show()
   

   

3. Vérifier que le code ci-dessous affiche l'image qui lui suit

   import networkx as nx
   import numpy as np
   import matplotlib.pyplot as plt
   from networkx.drawing.nx_pydot import graphviz_layout
   
   def draw_digraph_dict_of_list(graph, layout="spring_layout", root=None):
       G = nx.DiGraph(graph)
       if layout == "spring_layout":
           pos = nx.spring_layout(G, seed=5) # seed for reproducible plots...
       else:
           pos = graphviz_layout(G, prog=layout, root=root)
       nx.draw(G, pos, with_labels=True, font_weight='bold')
       nx.draw(G, pos, with_labels=True, font_weight='bold')
   
   graph = {
       'A' : ['B', 'C'],
       'B' : ['C'],
       'C' : ['A', 'B'],
   }
   draw_digraph_dict_of_list(graph)
   plt.show()
   

   

4. Compléter la fonction create_path_using_parent_dict ci-dessous pour qu'étant donné un tableau de prédécesseurs (la valeur particulière None signifiant que le somemt n'a pas de prédécesseur) et un sommet elle retourne le chemin terminant en ce sommet dont la relation sommet à prédesseur est déterminée par le tableau. On s'arrêtera au premier sommet sans prédecesseur.

   def create_path_using_parent_dict(parent_dict, goal):
       path, s = ??, goal
       while ?? is not None:
           ??.append(??)
           s = parent_dict[s]
           assert ?? not in ?? # no loop
       return list(reversed(path))
   
   def teste_create_path_using_parent_dict():
       # A -> C -> B -> E ; D
       parent_dict = {
           "A": None,
           "B": "C",
           "C": "A",
           "D": None,
           "E": "B"
       }
       goal = "E"
       path = create_path_using_parent_dict(parent_dict, goal)
       assert path == [??, ??, ??, "E"]
   
   teste_create_path_using_parent_dict()
   

   def create_path_using_parent_dict(parent_dict, goal):
       path, s = [], goal
       while s is not None:
           path.append(s)
           s = parent_dict[s]
           assert s not in path # no loop
       return list(reversed(path))
   
   def teste_create_path_using_parent_dict():
       # A -> C -> B -> E ; D
       parent_dict = {
           "A": None,
           "B": "C",
           "C": "A",
           "D": None,
           "E": "B"
       }
       goal = "E"
       path = create_path_using_parent_dict(parent_dict, goal)
       assert path == ["A", "C", "B", "E"]
   
   teste_create_path_using_parent_dict()
   

Dans cette section on ne s'intéresse qu'aux graphes non orienté #+BEGIN_activite

1. 1. Compléter la définition suivante pour que la fonction mat_adj_vers_dict_succ pour qu'elle retourne un dictionnaire des successeurs représentant le graphe de matrice d'adjacence donnée en arguments

      import numpy as np
      
      def mat_adj_vers_dict_succ(A):
         n, p = A.shape
         assert n == ??
         d = ??
         for i in range(n):
            d[i] = ??
            for j in range(n):
               if A[i,j] == ??:
                  d[??].append(??)
         return ??
      
      def teste_mat_adj_vers_dict_succ():
         A = np.array([[0,1,0], [1,0,0], [0,1,0]])
         d = mat_adj_vers_dict_succ(A)
         assert d[0] == ??
         assert d[1] == ??
         assert d[2] == ??
         A = np.array([[1,1,0], [1,0,1], [0,1,1]])
         d = mat_adj_vers_dict_succ(A)
         assert sorted(d[0])==??
         assert sorted(d[1])==??
         assert sorted(d[2])==??
      
      teste_mat_adj_vers_dict_succ()
      

      import numpy as np
      
      def mat_adj_vers_dict_succ(A):
         n, p = A.shape
         assert n==p
         d = {}
         for i in range(n):
            d[i] = []
            for j in range(n):
               if A[i,j] == 1: # ou A[i,j] != 0
                  d[i].append(j)
         return d
      
      def teste_mat_adj_vers_dict_succ():
         A = np.array([[0,1,0], [1,0,0], [0,1,0]])
         d = mat_adj_vers_dict_succ(A)
         assert d[0] == [1]
         assert d[1] == [0]
         assert d[2] == [1]
         A = np.array([[1,1,0], [1,0,1], [0,1,1]])
         d = mat_adj_vers_dict_succ(A)
         assert sorted(d[0])==[0,1]
         assert sorted(d[1])==[0,2]
         assert sorted(d[2])==[1,2]
      
      teste_mat_adj_vers_dict_succ()
      

   2. Écrire une fonction mat_adj_vers_dict_pred pour qu'elle retourne un dictionnaire des prédecesseurs représentant le graphe de matrice d'adjacence donnée en argument.

      import numpy as np
      
      def mat_adj_vers_dict_pred(A):
         n, p = A.shape
         assert n==p
         d = {}
         for i in range(n):
            d[i] = []
            for j in range(n):
               if A[j,i] == 1: # ou A[j,i] != 0
                  d[i].append(j)
         return d
      
      def teste_mat_adj_vers_dict_pred():
         A = np.array([[0,1,0],
                       [1,0,0],
                       [0,1,0]])
         d = mat_adj_vers_dict_pred(A)
         assert d[0] == [1]
         assert sorted(d[1]) == [0,2]
         assert d[2] == []
         A = np.array([[1,1,0],
                       [1,0,1],
                       [0,1,1]])
         d = mat_adj_vers_dict_pred(A)
         assert sorted(d[0]) == [0,1]
         assert sorted(d[1]) == [0,2]
         assert sorted(d[2]) == [1,2]
      
      teste_mat_adj_vers_dict_pred()
      

2. Vérifier que le code ci-dessous affiche l'image qui lui suit

   import networkx as nx
   import numpy as np
   import matplotlib.pyplot as plt
   from networkx.drawing.nx_pydot import graphviz_layout
   
   def draw_weighted_digraph_dict_of_dict(graph, layout="spring_layout", root=None):
       graph_for_nx = {
           n: {
               succ: {"weight": weight} for succ, weight in d.items()
           } for n, d in graph.items()
       }
       G = nx.DiGraph(graph_for_nx)
       if layout == "spring_layout":
           pos = nx.spring_layout(G, seed=5) # seed for reproducible plots...
       else:
           pos = graphviz_layout(G, prog=layout, root=root)
       nx.draw(G, pos, with_labels=True, font_weight='bold')
       edge_labels = nx.get_edge_attributes(G,"weight")
       nx.draw_networkx_edge_labels(G, pos,
                                    edge_labels = edge_labels,
                                    font_weight='bold')
   
   graph = {
       'A' : {'B': 5, 'C': 2},
       'B' : {'C': 1},
       'C' : {'A': 3, 'B': 8}
   }
   draw_weighted_digraph_dict_of_dict(graph)
   plt.show()
   

   

3. Vérifier que le code ci-dessous affiche l'image qui lui suit

   import networkx as nx
   import numpy as np
   import matplotlib.pyplot as plt
   from networkx.drawing.nx_pydot import graphviz_layout
   
   def draw_digraph_dict_of_list(graph, layout="spring_layout", root=None):
       G = nx.DiGraph(graph)
       if layout == "spring_layout":
           pos = nx.spring_layout(G, seed=5) # seed for reproducible plots...
       else:
           pos = graphviz_layout(G, prog=layout, root=root)
       nx.draw(G, pos, with_labels=True, font_weight='bold')
       nx.draw(G, pos, with_labels=True, font_weight='bold')
   
   graph = {
       'A' : ['B', 'C'],
       'B' : ['C'],
       'C' : ['A', 'B'],
   }
   draw_digraph_dict_of_list(graph)
   plt.show()
   

   

4. Compléter la fonction create_path_using_parent_dict ci-dessous pour qu'étant donné un tableau de prédécesseurs (la valeur particulière None signifiant que le somemt n'a pas de prédécesseur) et un sommet elle retourne le chemin terminant en ce sommet dont la relation sommet à prédesseur est déterminée par le tableau. On s'arrêtera au premier sommet sans prédecesseur.

   def create_path_using_parent_dict(parent_dict, goal):
       path, s = ??, goal
       while ?? is not None:
           ??.append(??)
           s = parent_dict[s]
           assert ?? not in ?? # no loop
       return list(reversed(path))
   
   def teste_create_path_using_parent_dict():
       # A -> C -> B -> E ; D
       parent_dict = {
           "A": None,
           "B": "C",
           "C": "A",
           "D": None,
           "E": "B"
       }
       goal = "E"
       path = create_path_using_parent_dict(parent_dict, goal)
       assert path == [??, ??, ??, "E"]
   
   teste_create_path_using_parent_dict()
   

   def create_path_using_parent_dict(parent_dict, goal):
       path, s = [], goal
       while s is not None:
           path.append(s)
           s = parent_dict[s]
           assert s not in path # no loop
       return list(reversed(path))
   
   def teste_create_path_using_parent_dict():
       # A -> C -> B -> E ; D
       parent_dict = {
           "A": None,
           "B": "C",
           "C": "A",
           "D": None,
           "E": "B"
       }
       goal = "E"
       path = create_path_using_parent_dict(parent_dict, goal)
       assert path == ["A", "C", "B", "E"]
   
   teste_create_path_using_parent_dict()
   

Un parcours de graphe est dit en profondeur si pour chaque sommet

• il visite ce sommet;
• puis visite récursivement chaque sommet adjacent non déjà parcouru.

Ainsi

• c'est un parcours qui s'implément facilement de façon récursive;
• les sommets fils sont parcourus avant les frères (sauf pour les fils qui ont déjà été parcourus et ne se donc pas reparcourus).
• on peut vouloir effectuer une action en rentrant dans un sommet (donc avant de visiter les fils non encore visités) par exemple si on veut créer une hierarchie de dossiers/sous-dossiers non a partir de sa représentation sous forme de graphe;

• on peut vouloir effectuer une action en sortant d'un sommet (donc après avoir visité tous ses fils) par exemple si on veut détruire une hierarchie de dossiers/sous-dossiers et qu'on ne peut supprimer que des dossiers vides.

  1. En commençant votre script par le code ci-dessous

     import os
     import sys
     from collections import deque
     
     # Inutile de comprendre le fonctionnement de cette fonction: HP
     def print_green(*args, **kwargs):
         OKGREEN = '\x1b[32m'
         ENDC = '\x1b[0m'
         print(*[OKGREEN+txt+ENDC for txt in args], **kwargs)
     
     # Inutile de comprendre le fonctionnement de cette fonction: HP
     def print_cyan(*args, **kwargs):
         OKCYAN = '\x1b[36m'
         ENDC = '\x1b[0m'
         print(*[OKCYAN+txt+ENDC for txt in args], **kwargs)
     
     # Inutile de comprendre le fonctionnement de cette fonction: HP
     def print_black(*args, **kwargs):
         print(*args, **kwargs)
     
     def do_nothing(sommet):
         return
     
     def previsite_print_sommet(sommet):
         print_green("Avant visite du sommet", sommet)
     
     def postvisite_print_sommet(sommet):
         print_cyan("Après visite du sommet", sommet)
     

     compléter le script suivant afin qu'il effectue un parcours en profondeur du graphe passé en premier argument

     def parcours_profondeur_aux(G, sommet, previsite_fun, postvisite_fun, parent_dict):
         previsite_fun(sommet)
         for sommet_adj in ??:
             if ??: # sommet déjà visité?
                 parent_dict[??] = ??
                 parcours_profondeur_aux(??, ??, ??, ??, ??)
         postvisite_fun(sommet)
     
     def parcours_profondeur(G, start, previsite_fun, postvisite_fun):
         parent_dict = {??: None}
         parcours_profondeur_aux(??, ??, ??, ??, ??)
         return parent_dict
     

     Dans la suite on utilise le graphe ci-dessous

     G_dict_dict = {
         "Chaos": ["Nyx", "Erebe", "Tartare", "Eros", "Gaya"],#
         "Nyx": ["Eris", "Hemera"],#
         "Erebe": ["Eris", "Hemera"],#
         "Gaya": ["Nymphes", "Ourea", "Pontos", "Ouranos"],#
         "Nymphes": [],#
         "Ourea": [],#
         "Pontos": [],#
         "Ouranos": ["Chronos", "Rhea"],#
         "Chronos": ["Zeus"],#
         "Rhea": ["Zeus"],#
         "Hemera": [],#
         "Eris": [],#
         "Erebe": [],#
         "Tartare": [],#
         "Eros": [],#
         "Chronos": [],#
         "Rhea": [],#
     }     
     draw_digraph_dict_of_list(G_dict_dict, layout="dot")
     

     /tmp/ipykernel_41646/3099813051.py:11: DeprecationWarning: nx.nx_pydot.graphviz_layout depends on the pydot package, which has known issues and is not actively maintained. Consider using nx.nx_agraph.graphviz_layout instead.
     
     See https://github.com/networkx/networkx/issues/5723
       pos = graphviz_layout(G, prog=layout, root=root)
     

     

     Vérifier que les scripts suivants donnent les sorties données dans la console.

     1. print_black("Previsite (parcours en profondeur):")
        parcours_profondeur(G_dict_dict, "Chaos", previsite_print_sommet, do_nothing)
        

        : Previsite (parcours en profondeur):
        Avant visite du sommet Chaos
        Avant visite du sommet Nyx
        Avant visite du sommet Eris
        Avant visite du sommet Hemera
        Avant visite du sommet Erebe
        Avant visite du sommet Tartare
        Avant visite du sommet Eros
        Avant visite du sommet Gaya
        Avant visite du sommet Nymphes
        Avant visite du sommet Ourea
        Avant visite du sommet Pontos
        Avant visite du sommet Ouranos
        Avant visite du sommet Chronos
        Avant visite du sommet Rhea
        

  1. print_black("Postvisite (parcours en profondeur):")
     parcours_profondeur(G_dict_dict, "Chaos", do_nothing, postvisite_print_sommet)
     

     : Postvisite (parcours en profondeur):
     Après visite du sommet Eris
     Après visite du sommet Hemera
     Après visite du sommet Nyx
     Après visite du sommet Erebe
     Après visite du sommet Tartare
     Après visite du sommet Eros
     Après visite du sommet Nymphes
     Après visite du sommet Ourea
     Après visite du sommet Pontos
     Après visite du sommet Chronos
     Après visite du sommet Rhea
     Après visite du sommet Ouranos
     Après visite du sommet Gaya
     Après visite du sommet Chaos
     

  2. print_black("Previsite et postvisite  (parcours en profondeur):")
     parcours_profondeur(G_dict_dict, "Chaos", previsite_print_sommet, postvisite_print_sommet)     
     

     : Previsite et postvisite (parcours en profondeur):
     Avant visite du sommet Chaos
     Avant visite du sommet Nyx
     Avant visite du sommet Eris
     Après visite du sommet Eris
     Avant visite du sommet Hemera
     Après visite du sommet Hemera
     Après visite du sommet Nyx
     Avant visite du sommet Erebe
     Après visite du sommet Erebe
     Avant visite du sommet Tartare
     Après visite du sommet Tartare
     Avant visite du sommet Eros
     Après visite du sommet Eros
     Avant visite du sommet Gaya
     Avant visite du sommet Nymphes
     Après visite du sommet Nymphes
     Avant visite du sommet Ourea
     Après visite du sommet Ourea
     Avant visite du sommet Pontos
     Après visite du sommet Pontos
     Avant visite du sommet Ouranos
     Avant visite du sommet Chronos
     Après visite du sommet Chronos
     Avant visite du sommet Rhea
     Après visite du sommet Rhea
     Après visite du sommet Ouranos
     Après visite du sommet Gaya
     Après visite du sommet Chaos
     

Un parcours de graphe est dit en largeur si les frères d'un sommet (non encore parcourus) sont parcourus avant ses fils (remarquons que cette décision a par contré été prise par le sommet parent car un sommet n'a pas accès directement à ses frêres).

• un graphe non orienté est dite connexe si tout sommet peut être atteint à partir d'un autre.

• Le fait qu'un graphe non orienté possède un cycle peut être détecté lors d'un parcours, de préference lors d'un parcours en profondeur.

  1. Écrire une fonction graphe_est_connexe qui accepte une matrice d'adjacence en argument (représentée par une liste de liste d'entiers ou par un tableau numpy) et qui en effectuant un parcourt en profondeur retourne True si le graphe est connexe et False sinon.
  2. Écrire une fonction graphe_non_orienté_a_cycle qui accepte une matrice d'adjacence en argument (représentée par une liste de liste d'entiers ou par un tableau numpy) et qui en effectuant un parcourt en profondeur retourne True si le graphe possède un cycle et False sinon.