liste d 27adjacence simple code python

1#! /usr/local/bin/python
2#-*- coding: utf_8 -*-
3
4#import dijkstra
5
6class Graphe(object):
7	"""Classe représentant un graphe.
8
9	Un graphe est représenté par un dictionnaire.
10	"""
11	def __init__(self):
12		"""Initialise le graphe à vide.
13		"""
14		self.graphe = {}
15
16	def ajouteSommet(self, sommet):
17		"""Ajoute un sommet au graphe sans aucun voisin.
18		"""
19		if sommet not in self.graphe.keys():
20			self.graphe[sommet] = {}
21
22	def ajouteArrete(self, sommet, sommetVoisin, p):
23		"""Crée une arrête en reliant sommet avec sommetVoisin en associant le poids p.
24		"""
25		if sommet != sommetVoisin:
26			try:
27				self.graphe[sommetVoisin][sommet] = p
28				self.graphe[sommet][sommetVoisin] = p
29			except KeyError:
30				pass
31
32	def supprimeSommet(self, sommet):
33		"""Supprime un sommet du graphe.
34		"""
35		for sommetVoisin in self.graphe[sommet].keys():
36			del self.graphe[sommetVoisin][sommet]
37		del self.graphe[sommet]
38
39	def supprimeArrete(self, sommet, sommetVoisin):
40		"""Supprime une arrête.
41		"""
42		if sommet in self.graphe[sommetVoisin]:
43			self.supprimeSommet(sommet)
44			self.supprimeSommet(sommetVoisin)
45
46	def toMatrice(self):
47		"""Affichage matriciel du graphe.
48		"""
49		print " ",
50		for i in sorted(self.graphe.keys()):
51			print i,
52		print
53		for i in sorted(self.graphe.keys()):
54			print i,
55			for j in sorted(self.graphe.keys()):
56				if i in self.graphe[j].keys():
57					print '1',
58				else:
59					print '0',
60			print
61
62	def toListe(self):
63		"""Affiche le graphe sous forme de listes d'adjacences.
64		"""
65		for i in sorted(self.graphe.keys()):
66			print i, " --> ",
67			print self.graphe[i].keys()
68
69	def toXML(self):
70		"""Affiche le graphe sous une structure XML.
71		"""
72		from xml.dom.minidom import Document
73
74		try:
75			racine = doc.getElementsByName('graphe').item(0)
76		except:
77			doc = Document()
78			racine = doc.createElement("graphe")
79			doc.appendChild(racine)
80
81		for sommet in sorted(self.graphe.keys()):
82			try:
83				noeud = doc.getElementsByName(sommet)
84			except:
85				noeud = doc.createElement(sommet)
86				racine.appendChild(noeud)
87
88			if len(self.graphe[sommet].keys()) == 0:
89				element = doc.createTextNode("")
90				noeud.appendChild(element)
91
92			for voisin in sorted(self.graphe[sommet].keys()):
93				try:
94					element = doc.createElement("voisin")
95					element.setAttribute("nom", voisin)
96					element.setAttribute("poids",str(self.graphe[sommet][voisin]))
97					noeud.appendChild(element)
98				except:
99					pass
100
101		return doc.toprettyxml()
102
103	def __eq__(self, graphe1):
104		"""Compare deux graphes.
105		"""
106		return self.graphe == graphe1
107
108	def __str__(self):
109		"""Affichage du graphe.
110		"""
111		return repr(self.graphe)
112	
113	def __repr__(self):
114		"""Représentation du graphe.
115		"""
116		return repr(self.graphe)
117
118if __name__ == "__main__":
119	# Point d'entrée en exécution.
120	graph = Graphe()
121	graph.ajouteSommet('A')
122	graph.ajouteSommet('B')
123	graph.ajouteSommet('C')
124	graph.ajouteSommet('D')
125	graph.ajouteSommet('E')
126	graph.ajouteSommet('F')
127
128	graph.ajouteArrete('A', 'C', 2)
129	graph.ajouteArrete('D', 'B', 2)
130	graph.ajouteArrete('B', 'C', 800)
131	graph.ajouteArrete('B', 'D', 7)
132	graph.ajouteArrete('C', 'D', 7)
133	graph.ajouteArrete('F', 'A', 7)
134	print graph
135	print
136	graph.toMatrice()
137	print
138	graph.toListe()
139	print
140	print graph.toXML()
141	#print dijkstra.shortestPath(graph.graphe, 'A', 'B')
142