Graphes non-orientés

Commenter

Contenu du snippet

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 noeuds 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...

Source / Exemple : 


#! /usr/local/bin/python
#-*- coding: utf_8 -*-

#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,
		print
		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',
			print

	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
	print
	graph.toMatrice()
	print
	graph.toListe()
	print
	print graph.toXML()
	#print dijkstra.shortestPath(graph.graphe, 'A', 'B')

Conclusion :


Il est aussi 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).

Voilà la représentation sous forme de matrice ( toMatrice() ):

A B C D E F
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

et de liste d'adjacence ( toListe() ):

A --> ['C', 'F']
B --> ['C', 'D']
C --> ['A', 'B', 'D']
D --> ['C', 'B']
E --> []
F --> ['A']

Après avoir fait quelques tests il semble que cette implémentation de Dijkstra (http://code.activestate.com/recipes/119466/) fonctionne avec la classe.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (KimbleMandel)