Bibliothèque de graphes

Vous retrouverez dans graph.py le squelette de la classe Graph que vous avez implanté la séance dernière. Remplacez-le par votre implantation, puis vérifiez que tout fonctionne:

from graph import Graph, examples
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-1-ab1eaf72241e> in <module>
----> 1 from graph import Graph, examples

~/work/Enseignement/AlgoAvancee/ComputerLab/2-ParcoursDeGraphes/graph.py in <module>
     36 
     37 
---> 38 class Graph:
     39 
     40     # Déclaration des attributs

~/work/Enseignement/AlgoAvancee/ComputerLab/2-ParcoursDeGraphes/graph.py in Graph()
     46     # À vous de choisir la structure de donnée pour les arêtes (edges)
     47     # Remplacer la ligne suivante par le code adéquat
---> 48     raise NotImplementedError("code non implanté ligne 49");
     49 
     50     def __init__(

NotImplementedError: code non implanté ligne 49
G = Graph([1,2,3], edges=[(1,2,"12"),(2,3,"23")])
assert G.edges() == ((1, 2, '12'), (2, 1, '12'), (2, 3, '23'), (3, 2, '23'))
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-2-bf90ac6b9c4b> in <module>
----> 1 assert G.edges() == ((1, 2, '12'), (2, 1, '12'), (2, 3, '23'), (3, 2, '23'))

NameError: name 'G' is not defined
G.show()
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-3-3953782f1ed5> in <module>
----> 1 G.show()

NameError: name 'G' is not defined
G = examples.cours_1_G()
G.edges()
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-4-a474c2151191> in <module>
----> 1 G = examples.cours_1_G()
      2 G.edges()

NameError: name 'examples' is not defined
assert G.number_of_nodes() == 6

Maintenant, lancez tous les tests inclus dans la documentation des fonctions:

!pytest graph.py
============================= test session starts ==============================
platform linux -- Python 3.9.1, pytest-6.2.1, py-1.10.0, pluggy-0.13.1
rootdir: /home/nthiery/work/Enseignement/AlgoAvancee/ComputerLab/2-ParcoursDeGraphes, configfile: setup.cfg
plugins: anyio-2.0.2
collected 0 items / 2 errors                                                   

==================================== ERRORS ====================================
__________________________ ERROR collecting graph.py ___________________________
graph.py:38: in <module>
    class Graph:
graph.py:48: in Graph
    raise NotImplementedError("code non implanté ligne 49");
E   NotImplementedError: code non implanté ligne 49
__________________________ ERROR collecting graph.py ___________________________
graph.py:38: in <module>
    class Graph:
graph.py:48: in Graph
    raise NotImplementedError("code non implanté ligne 49");
E   NotImplementedError: code non implanté ligne 49
=========================== short test summary info ============================
ERROR graph.py - NotImplementedError: code non implanté ligne 49
ERROR graph.py - NotImplementedError: code non implanté ligne 49
!!!!!!!!!!!!!!!!!!! Interrupted: 2 errors during collection !!!!!!!!!!!!!!!!!!!!
============================== 2 errors in 1.22s ===============================

Évaluation de l’implantation des méthodes et de la complexité

from utils import show_source
show_source(Graph.successors)
show_source(Graph.predecessors)
show_source(Graph.capacity)
show_source(Graph.is_path)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-6-80052c5a8a02> in <module>
      1 from utils import show_source
----> 2 show_source(Graph.successors)
      3 show_source(Graph.predecessors)
      4 show_source(Graph.capacity)
      5 show_source(Graph.is_path)

NameError: name 'Graph' is not defined