Graphe & Coverage
Document Actions
Je viens vous présenter deux choses. Une petite implémentation d'une classe permettant de représenter des graphes. Et un fabuleux module nommé Coverage dont l'utilité est de vérifier si vous avez bien testé votre code. En fait, c'est surtout ce module qui m'intéresse.
Graphe
Voilà une classe très simple permettant de représenter des graphes non-orientés avec des poids sur les arêtes.
Le graphe est représenté par un dictionnaire. Pour l'implémentation je me suis inspiré de cet essai :
http://www.python.org/doc/essays/graphs.html
Les clés sont les nœuds et les valeurs représentes les voisins ainsi que les poids de chaque arêtes.
Exemple :
{'A': {'C': 2, 'F': 7},\
'C': {'A': 2, 'B': 800, 'D': 7},\
'B': {'C': 800, 'D': 7},\
'E': {}, 'D': {'C': 7, 'B': 7},\
'F': {'A': 7}}Donc l'arête AC à un poids de 2, l'arête AF à un poids de 7. En effet, on observe un <<gâchis>> de mémoire car les arêtes sont stockées en double, en revanche certains traitements sont facilités. On pourrait aisément éviter cette duplication, mais il ne s'agit pas d'optimiser la mémoire ici.
Voilà la représentation sous forme de matrice :
A B C D E Fet de liste d'adjacence :
A 0 0 1 0 0 1
B 0 0 1 1 0 0
C 1 1 0 1 0 0
D 0 1 1 0 0 0
E 0 0 0 0 0 0
F 1 0 0 0 0 0
A --> ['C', 'F']
B --> ['C', 'D']
C --> ['A', 'B', 'D']
D --> ['C', 'B']
E --> []
F --> ['A']
Il est donc possible d'imprimer le graphe sous forme de liste d'adjacence, de matrice et de l'exporter au format XML (pas grand intérêt et expérimental ;-).
Pour calculer le plus court chemin entre deux nœuds, cette implémentation de Dijkstra fonctionne très bien avec la classe.
Coverage
J'en viens enfin au plus intéressant - ce dont je voulais surtout parler - le module Coverage que je viens de découvrir il y a quelques temps.
Il s'agit d'un module assez sympa permettant de vérifier si tout votre code est testé. Attention, il ne permet pas dire si le code est juste, il dit s'il ne reste pas de morceau de code non testé.
Coverage génère un fichier indiquant chaque ligne de code non testé, ce qui est très pratique.
Voilà comment tester ma classe graphe :
[cedric@localhost ~]$ python coverage.py -e
[cedric@localhost ~]$ python coverage.py -x testGraphe.py
[cedric@localhost ~]$ python coverage.py -r -m graphe.py
[cedric@localhost ~]$ python coverage.py -a -d . graphe.py
résultat :
[cedric@localhost graphe]$ ./test.shDonc seulement 30% de mon code est couvert :-( En fait les sorties sous forme de liste d'adjacence, de matrice et au format XML ne sont pas testés...
Teste l'ajout d'un sommet. ... ok
Teste l'ajout de voisins avec les poids. ... ok
Teste la suppression d'arrêtes. ... ok
Teste la suppression d'un sommet. ... ok
Teste avec un graphe vide. ... ok
----------------------------------------------------------------------
Ran 5 tests in 0.005s
OK
Name Stmts Exec Cover Missing
--------------------------------------
graphe 96 29 30% 29-30, 49-60, 65-67, 72-101, 106-112, 122, 127, 132-152
Coverage indique même les numéros des lignes non testés. De plus, un fichier graphe.py,cover a été généré pour montrer ces lignes dans le code.
Le fichier test.sh contient simplement les 4 lignes de commandes vues plus haut.
Les codes utilisés
La classe Graphe
#! /usr/local/bin/python
#-*- coding: utf_8 -*-
__author__ = "Cédric Bonhomme"
__date__ = "$Date: 2008/04/10 $"
__license__ = "Python"
#import dijkstra
class Graphe(object):
"""Classe représentant un graphe.
Un graphe est représenté par un dictionnaire.
"""
def __init__(self):
"""Initialise le graphe à vide.
"""
self.graphe = {}
def ajouteSommet(self, sommet):
"""Ajoute un sommet au graphe sans aucun voisin.
"""
if sommet not in self.graphe.keys():
self.graphe[sommet] = {}
def ajouteArrete(self, sommet, sommetVoisin, p):
"""Crée une arrête en reliant sommet avec sommetVoisin en associant le poids p.
"""
if sommet != sommetVoisin:
try:
self.graphe[sommetVoisin][sommet] = p
self.graphe[sommet][sommetVoisin] = p
except KeyError:
pass
def supprimeSommet(self, sommet):
"""Supprime un sommet du graphe.
"""
for sommetVoisin in self.graphe[sommet].keys():
del self.graphe[sommetVoisin][sommet]
del self.graphe[sommet]
def supprimeArrete(self, sommet, sommetVoisin):
"""Supprime une arrête.
"""
if sommet in self.graphe[sommetVoisin]:
self.supprimeSommet(sommet)
self.supprimeSommet(sommetVoisin)
def toMatrice(self):
"""Affichage matriciel du graphe.
"""
print " ",
for i in sorted(self.graphe.keys()):
print i,
for i in sorted(self.graphe.keys()):
print i,
for j in sorted(self.graphe.keys()):
if i in self.graphe[j].keys():
print '1',
else:
print '0',
def toListe(self):
"""Affiche le graphe sous forme de listes d'adjacences.
"""
for i in sorted(self.graphe.keys()):
print i, " --> ",
print self.graphe[i].keys()
def toXML(self):
"""Affiche le graphe sous une structure XML.
"""
from xml.dom.minidom import Document
try:
racine = doc.getElementsByName('graphe').item(0)
except:
doc = Document()
racine = doc.createElement("graphe")
doc.appendChild(racine)
for sommet in sorted(self.graphe.keys()):
try:
noeud = doc.getElementsByName(sommet)
except:
noeud = doc.createElement(sommet)
racine.appendChild(noeud)
if len(self.graphe[sommet].keys()) == 0:
element = doc.createTextNode("")
noeud.appendChild(element)
for voisin in sorted(self.graphe[sommet].keys()):
try:
element = doc.createElement("voisin")
element.setAttribute("nom", voisin)
element.setAttribute("poids",str(self.graphe[sommet][voisin]))
noeud.appendChild(element)
except:
pass
return doc.toprettyxml()
def __eq__(self, graphe1):
"""Compare deux graphes.
"""
return self.graphe == graphe1
def __str__(self):
"""Affichage du graphe.
"""
return repr(self.graphe)
def __repr__(self):
"""Représentation du graphe.
"""
return repr(self.graphe)
if __name__ == "__main__":
# Point d'entrée en exécution.
graph = Graphe()
graph.ajouteSommet('A')
graph.ajouteSommet('B')
graph.ajouteSommet('C')
graph.ajouteSommet('D')
graph.ajouteSommet('E')
graph.ajouteSommet('F')
graph.ajouteArrete('A', 'C', 2)
graph.ajouteArrete('D', 'B', 2)
graph.ajouteArrete('B', 'C', 800)
graph.ajouteArrete('B', 'D', 7)
graph.ajouteArrete('C', 'D', 7)
graph.ajouteArrete('F', 'A', 7)
print graph
graph.toMatrice()
graph.toListe()
print graph.toXML()
#print dijkstra.shortestPath(graph.graphe, 'A', 'B')
La classe de tests
#! /usr/local/bin/python
#-*- coding: utf_8 -*-
import unittest
import graphe
class TestGraph(unittest.TestCase):
def setUp(self): # appelé avant chaque test
self.graph = graphe.Graphe()
def testVide(self):
"""Teste avec un graphe vide.
"""
self.assertEqual(self.graph, {})
def testAjouteSommet(self):
"""Teste l'ajout d'un sommet.
"""
self.graph.ajouteSommet('A')
self.assertEqual(self.graph, {'A' : {}})
def testAjouteVoisin(self):
"""Teste l'ajout de voisins avec les poids.
"""
self.graph.ajouteSommet('A')
self.graph.ajouteSommet('B')
self.graph.ajouteSommet('C')
self.graph.ajouteSommet('D')
self.graph.ajouteSommet('E')
self.graph.ajouteSommet('F')
self.graph.ajouteArrete('A', 'B', 3)
self.assertEqual(self.graph, {\
'A' : {'B':3},\
'B' : {'A':3},\
'C' : {},\
'D' : {},\
'E' : {},\
'F' : {} })
def testSuppressionSommet(self):
"""Teste la suppression d'un sommet.
"""
self.graph.ajouteSommet('A')
self.graph.supprimeSommet('A')
self.assertEqual(self.graph, {})
def testSuppressionArrete(self):
"""Teste la suppression d'arrêtes.
"""
self.graph.ajouteSommet('A')
self.graph.ajouteSommet('B')
self.graph.ajouteSommet('C')
self.graph.ajouteSommet('D')
self.graph.ajouteSommet('E')
self.graph.ajouteSommet('F')
self.graph.ajouteArrete('A', 'B', 1)
self.graph.ajouteArrete('A', 'C', 7)
self.graph.ajouteArrete('B', 'F', 1984)
self.graph.supprimeArrete('A', 'B')
self.assertEqual(self.graph, {\
'C' : {},\
'D' : {},\
'E' : {},\
'F' : {} })
if __name__ == "__main__":
suite = unittest.TestSuite()
suite.addTest(unittest.makeSuite(TestGraph))
unittest.TextTestRunner(verbosity=2).run(suite)
Voilà, maintenant vous serez enfin rassuré quand vous ferez vos tests ! ;-)