GRAPHES NON-ORIENTÉS

#! /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')