Commits

Cédric Bonhomme committed 87eb799

Renamed graphe.py to graph.py.

Comments (0)

Files changed (2)

+#! /usr/local/bin/python
+# -*- coding: utf-8 -*-
+
+__author__ = "Cedric Bonhomme"
+__date__ = "$Date: 2012/01/31 $"
+__license__ = "GPL v3"
+
+import dijkstra
+import shortest
+
+
+class Graph(object):
+	"""Classe représentant un graphe.
+
+	Un graphe est représenté par un dictionnaire.
+	http://www.python.org/doc/essays/graphs/
+	"""
+	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 relliant 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 fromXML(self, fichier = "./var/graphe-example1.xml"):
+		"""Crée un graphe à partir d'un fichier XML.
+		"""
+		from xml.dom.minidom import parse
+		doc = None
+		doc = parse(fichier)
+		for sommet in doc.getElementsByTagName("graphe").item(0).childNodes:
+			for voisin in sommet.childNodes:
+				self.ajouteSommet(sommet.childNodes.item(0))
+				self.ajouteArrete(sommet, voisin, voisin)
+
+	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 = Graph()
+	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()
+	#grapheXML = open('graphe.xml', 'w')
+	#grapheXML.write(graph.toXML())
+	#grapheXML.close()
+	#graph = Graph()
+	#graph.fromXML()
+	#print graph
+	print dijkstra.shortest_path(graph.graphe, 'A', 'B')
+	print shortest.find_shortest_path(graph.graphe, 'A', 'B')
+	print shortest.find_all_paths(graph.graphe, 'A', 'B')

graphe.py

-#! /usr/local/bin/python
-# -*- coding: utf-8 -*-
-
-__author__ = "Cedric Bonhomme"
-__date__ = "$Date: 2012/01/31 $"
-__license__ = "GPL v3"
-
-import dijkstra
-import shortest
-
-
-class Graph(object):
-	"""Classe représentant un graphe.
-
-	Un graphe est représenté par un dictionnaire.
-	http://www.python.org/doc/essays/graphs/
-	"""
-	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 relliant 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 fromXML(self, fichier = "./var/graphe-example1.xml"):
-		"""Crée un graphe à partir d'un fichier XML.
-		"""
-		from xml.dom.minidom import parse
-		doc = None
-		doc = parse(fichier)
-		for sommet in doc.getElementsByTagName("graphe").item(0).childNodes:
-			for voisin in sommet.childNodes:
-				self.ajouteSommet(sommet.childNodes.item(0))
-				self.ajouteArrete(sommet, voisin, voisin)
-
-	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 = Graph()
-	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()
-	#grapheXML = open('graphe.xml', 'w')
-	#grapheXML.write(graph.toXML())
-	#grapheXML.close()
-	#graph = Graph()
-	#graph.fromXML()
-	#print graph
-	print dijkstra.shortest_path(graph.graphe, 'A', 'B')
-	print shortest.find_shortest_path(graph.graphe, 'A', 'B')
-	print shortest.find_all_paths(graph.graphe, 'A', 'B')