Sujet Précédent Sujet Suivant

Petit problème d'algorithme

Fermé
selver057 Messages postés 25 Date d'inscription mardi 13 septembre 2011 Statut Membre Dernière intervention 17 avril 2017 - 1 nov. 2011 à 19:50
selver057 Messages postés 25 Date d'inscription mardi 13 septembre 2011 Statut Membre Dernière intervention 17 avril 2017 - 19 nov. 2011 à 21:11
Bonjour,

J'ai écrit ce petit programme en python qui me permet de modéliser un graphe orienté simple : 

 class Graphe(object):
        def __init__(self):
                self.sommet = []
                self.succ = []            
        def ajouterSommet(self):
                nouv_som = str(input("Entrez un nom de sommet : "))
                if nouv_som in self.sommet:
                        print("Attention! Ce nom de sommet est deja dans la liste.")
                        nouv_som = str(input("Entrez un nouveau nom : "))
                        while nouv_som in self.sommet:
                                if nouv_som in self.sommet:
                                        print("Attention! Ce nom de sommet est deja dans la liste.")
                                        nouv_som = str(input("Entrez un nouveau nom : "))
                        self.sommet.append(nouv_som)
                        self.succ.append([])
                else:
                        self.sommet.append(nouv_som)
                        self.succ.append([])                                   
        def ajouterArc(self):
                ext_ini = str(input("Entrez le nom de l'extremite initiale : "))
                ext_fin = str(input("Entrez le nom de l'extremite finale : "))
                a = 0
                b = 0
                if ext_ini in self.sommet and ext_fin in self.sommet:                   
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                elif not ext_ini in self.sommet and ext_fin in self.sommet:
                        self.sommet.append(ext_ini)
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                elif ext_ini in self.sommet and not ext_fin in self.sommet:
                        self.sommet.append(ext_fin)
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                else:
                        self.sommet.append(ext_ini)
                        self.sommet.append(ext_fin)
                        self.succ.append([])
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                if b in self.succ[a]:
                        print("Attention! Cette relation existe deja. Le doublon va etre enleve.")
                        self.succ[a].remove(b)
                self.succ[a].append(b)
         def affichageGraphe(self):
                print("Le(s) sommet(s) est\sont : " + str(self.sommet))
                print("Le(s) successeur(s) est\sont : " + str(self.succ))


Le programme marche bien et je souhaite maintenant faire une fonction qui me permet de stocker le(s) graphe(s) dans un fichier au format csv de la façon suivante :
- chaque ligne contient la description d'un sommet ou d'un arc sur deux colonnes
- une ligne qui décrit un sommet contient en première colonne le nom du graphe et en deuxième colonne un tiret ("-")
- une ligne qui décrit un arc contient en première colonne le nom de l'extrémité initiale et en deuxième colonne le nom de l'extrémité finale de l'arc
Exemple :
A ; -
B ; -
C ; -
A ; A
A ; B
B ; C
C ; A

Pouvez-vous, s'il vous plaît, me proposer une/des fonctions me permettant de réaliser ce que je viens de détailler plus haut? D'avance je vous remercie.

8 réponses

Réponse 1 / 8
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
2 nov. 2011 à 14:58
Salut,

J'ai légèrement réécrit ton code de façon à faire des essais d'exécution sans avoir à entrer à la main des données. 


class Graphe(object):
    import csv
    from itertools import izip
    
    def __init__(self):
        self.sommet = []
        self.succ = []

    def ajouterSommet(self,x = None):
        if not x:
            nouv_som = str(raw_input("Entrez un nom de sommet : "))
        else:
            nouv_som = x
        if nouv_som in self.sommet:
            print("Attention! Ce nom de sommet est deja dans la liste.")
            nouv_som = str(raw_input("Entrez un nouveau nom : "))
            while nouv_som in self.sommet:
                    if nouv_som in self.sommet:
                            print("Attention! Ce nom de sommet est deja dans la liste.")
                            nouv_som = str(raw_input("Entrez un nouveau nom : "))
            self.sommet.append(nouv_som)
            self.succ.append([])
        else:
            self.sommet.append(nouv_som)
            self.succ.append([])                                   
    def ajouterArc(self,x=None,y = None):
        if not x:
            ext_ini = str(raw_input("Entrez le nom de l'extremite initiale : "))
        else:
            ext_ini = x
        if not y:
            ext_fin = str(raw_input("Entrez le nom de l'extremite finale : "))
        else:
            ext_fin = y
        a = 0
        b = 0
        if ext_ini in self.sommet and ext_fin in self.sommet:
            print x,' IN     ',y,' IN'
            a = self.sommet.index(ext_ini)
            b = self.sommet.index(ext_fin)
        elif not ext_ini in self.sommet and ext_fin in self.sommet:
            print x,' OUT     ',y,' IN'
            self.sommet.append(ext_ini)
            self.succ.append([])
            a = self.sommet.index(ext_ini)
            b = self.sommet.index(ext_fin)
        elif ext_ini in self.sommet and not ext_fin in self.sommet:
            print x,' IN     ',y,' OUT'
            self.sommet.append(ext_fin)
            self.succ.append([])
            a = self.sommet.index(ext_ini)
            b = self.sommet.index(ext_fin)
        else:
            print x,' OUT     ',y,' OUT'
            self.sommet.append(ext_ini)
            self.sommet.append(ext_fin)
            self.succ.append([])
            self.succ.append([])
            a = self.sommet.index(ext_ini)
            b = self.sommet.index(ext_fin)
        if b in self.succ[a]:
            print("Attention! Cette relation existe deja. Le doublon va etre enleve.")
            self.succ[a].remove(b)
        self.succ[a].append(b)
    def affichageGraphe(self):
        print("Le(s) sommet(s) est\sont : " + str(self.sommet))
        print("Le(s) successeur(s) est\sont : " + str(self.succ))
    def enregistrerGraphe(self,filepath):
        f = open(filepath+'.txt','wb')
        wrt = Graphe.csv.writer(f,delimiter=';')
        wrt.writerows([som,'-'] for som in self.sommet)
        wrt.writerows([som,self.sommet[one_succ]]
                      for som,successeurs_de_som in Graphe.izip(self.sommet,self.succ)
                      for one_succ in successeurs_de_som)
        f.close()
        

g = Graphe()

g.ajouterSommet('A')
g.affichageGraphe()
g.ajouterSommet('D')
g.affichageGraphe()
g.ajouterSommet('R')
g.affichageGraphe()
print
g.ajouterArc('Q','E')
g.affichageGraphe()
print
g.ajouterSommet('sooz')
g.affichageGraphe()
g.ajouterSommet('Z')
g.affichageGraphe()
print
g.ajouterArc('Z','A')
g.affichageGraphe()
print
g.ajouterSommet('UU')
g.affichageGraphe()
print
g.ajouterArc('Z','Z')
g.affichageGraphe()
g.ajouterArc('Z','UU')
g.affichageGraphe()

print
print g.sommet
print g.succ

g.enregistrerGraphe('objo')


Pour le moment, j'ai répondu à ta question au plus près. Mais il y a un certain nombre de choses à améliorer. Je posterai mes remarques plus tard, dans la mesure où j'aurai le temps.
0
Réponse 2 / 8
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
2 nov. 2011 à 15:51
Cette partie de ton code: 

        else:
            self.sommet.append(ext_ini)
            self.sommet.append(ext_fin)
            self.succ.append([])
            self.succ.append([])
            a = self.sommet.index(ext_ini)
            b = self.sommet.index(ext_fin)


présente un danger.
Dans le cas où la relation dans un graphe peut être réflexive, c'est à dire qu'il peut exister la relation d'un sommet vers lui-même, il peut arriver qu'on définisse par exemple 
g.ajouterArc('Q','Q')

alors que le sommet 'Q' n'existe pas dans le graphe.
Dans ce cas, ton code crée DEUX sommets 'Q' et un seul voit la liste de ses successeurs être remplie par l'index de sa propre position, le second sommet garde une list de successeurs vide.
0
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
2 nov. 2011 à 16:30
Ceci est préférable: 

    def ajouterArc(self,x=None,y = None,what = ('nouveau','deja present')):
        if x:  ext_ini = x
        else:  ext_ini = str(raw_input("Entrez le nom de l'extremite initiale : "))
        if ext_ini not in self.sommet:
            self.sommet.append(ext_ini) ; self.succ.append([])
        a = self.sommet.index(ext_ini)
            
        if y:  ext_fin = y
        else:  ext_fin = str(raw_input("Entrez le nom de l'extremite finale : "))
        if ext_fin not in self.sommet:
            self.sommet.append(ext_fin) ; self.succ.append([])
        b = self.sommet.index(ext_fin)
        
        if b in self.succ[a]:
            print("Attention! Cette relation existe deja. Creation non effectuee.")
        else:
            print '* ajout de relation  %s  %s  vers   %s  %s' % (ext_ini,what[ext_ini in self.sommet],ext_fin,what[ext_fin in self.sommet])
            self.succ[a].append(b)
0
Réponse 3 / 8
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
2 nov. 2011 à 16:47
Voici comment je préfère écrire ton code: 


class Graphe(object):
    import csv
    from itertools import izip
    
    def __init__(self):
        self.sommet = []
        self.succ = []

    def ajouterSommet(self,x = None,com = ''):
        if x is None:
            while True:
                nouv_som = str(raw_input(com + "Entrez un nouveau nom : "))
                if nouv_som not in self.sommet:
                    print '- ajout de sommet  %s' % nouv_som
                    self.sommet.append(nouv_som) ; self.succ.append([])
                    break
                else:
                    com = "Attention! Ce nom de sommet est deja dans la liste.\n"
        elif x not in self.sommet:
            print '- ajout de sommet  %s' % x
            self.sommet.append(x) ; self.succ.append([])
        else:
            while True:
                raw_input('Rediger le code avec un autre sommet, '+x+' est deja present')

    def ajouterArc(self,x=None,y = None,what = ('nouveau','deja present')):
        if x:  ext_ini = x
        else:  ext_ini = str(raw_input("Entrez le nom de l'extremite initiale : "))
        if ext_ini not in self.sommet:
            self.sommet.append(ext_ini) ; self.succ.append([])
        a = self.sommet.index(ext_ini)
            
        if y:  ext_fin = y
        else:  ext_fin = str(raw_input("Entrez le nom de l'extremite finale : "))
        if ext_fin not in self.sommet:
            self.sommet.append(ext_fin) ; self.succ.append([])
        b = self.sommet.index(ext_fin)
        
        if b in self.succ[a]:
            print("Attention! Cette relation existe deja. Creation non effectuee.")
        else:
            print '* ajout de relation  %s  %s  vers   %s  %s'\
                  % (ext_ini,what[ext_ini in self.sommet],ext_fin,what[ext_fin in self.sommet])
            self.succ[a].append(b)
            
    def affichageGraphe(self):
        print("Le(s) sommet(s) est\sont : %s\n"
              "Le(s) successeur(s) est\sont : %s") %(self.sommet,self.succ)
        
    def enregistrerGraphe(self,filepath):
        f = open(filepath+'.txt','wb')
        wrt = Graphe.csv.writer(f,delimiter=';')
        wrt.writerows([som,'-'] for som in self.sommet)
        wrt.writerows([som,self.sommet[one_succ]]
                      for som,successeurs_de_som in Graphe.izip(self.sommet,self.succ)
                      for one_succ in successeurs_de_som)
        f.close()
        

g = Graphe()

g.ajouterSommet('A')
g.affichageGraphe()
g.ajouterSommet('B')
g.affichageGraphe()
g.ajouterSommet('R')
g.affichageGraphe()
print
g.ajouterArc('Q','Q')
g.affichageGraphe()
print
g.ajouterSommet('sooz')
g.affichageGraphe()
g.ajouterSommet('Z')
g.affichageGraphe()
print
g.ajouterArc('Z','Q')
g.affichageGraphe()
print
g.ajouterSommet('UU')
g.affichageGraphe()
print
g.ajouterArc('Z','Z')
g.affichageGraphe()
g.ajouterArc('Z','UU')
g.affichageGraphe()

print
print g.sommet
print g.succ

g.enregistrerGraphe('objo')




Ceci dit, il y a encore des défauts dans ce code.

Suite au prochain numéro...
0
Réponse 4 / 8
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
3 nov. 2011 à 09:10
A moins que tu ne comptes utiliser les instances de la classe Graphe dans des applications pour lesquelles le modèle de données que tu as choisi (une liste sommet accompagnée d'une liste succ) est meilleur, je pense que représenter un graphe par un dictionnaire serait meilleur.

Voici ce que ca donne.
Je me suis amusé à fignoler les affichages en surchargeant __setitem__ et en affichant des messages différents selon les actions. 


class Graphe(dict):
    import csv

    def __setitem__(self,key,val):
        print '- ajout de sommet  %s' % key
        super(Graphe,self).__setitem__(key,val)
    
    def ajouterSommet(self,x = None,com = ''):
        if x is None:
            while True:
                nouv_som = str(raw_input(com + "Entrez un nouveau nom : "))
                if nouv_som not in self:
                    print '- ajout de sommet  %s' % nouv_som
                    self[nouv_som] = []
                    break
                else:
                    com = "Attention! Ce nom de sommet est deja dans le dictionnaire.\n"
        elif x not in self:
            self[x] = []
        else:
            while True:
                raw_input('Rediger le code avec un autre sommet, '+x+' est deja present')

    def ajouterArc(self,x=None,y = None):
        ext_ini = x if x else str(raw_input("Entrez le nom de l'extremite initiale : "))
        ext_fin = y if y else str(raw_input("Entrez le nom de l'extremite finale : "))

        if ext_ini in self and ext_fin in self[ext_ini]:
                print("\n# Tentative de creation de la relation  %s  vers  %s :\n"
                      "Attention! Cette relation existe deja. Creation non effectuee.")\
                      % (ext_ini,ext_fin)
        else:
            zz = ', necessite ajout de sommet ' if (ext_ini not in self or ext_fin not in self) else ''
            print '# ajout de relation  %s  vers  %s %s:' % (ext_ini,ext_fin,zz)                                             
            if ext_ini not in self:  self[ext_ini] = []
            if ext_fin not in self:  self[ext_fin] = []
            self[ext_ini].append(ext_fin)
            
    def affichageGraphe(self,displ=False):
        if displ:
            print'\n'.join('%s : %s' % (k,self[k]) for k in self)
        else:
            print self
        
    def enregistrerGraphe(self,filepath):
        f = open(filepath+'.txt','wb')
        wrt = Graphe.csv.writer(f,delimiter=';')
        wrt.writerows([som,'-'] for som in self)
        wrt.writerows([som,one_succ] for som in self for one_succ in self[som])
        f.close()
        

g = Graphe()

g.ajouterSommet('A')
g.affichageGraphe()
g.ajouterSommet('B')
g.affichageGraphe()
g.ajouterSommet('R')
g.affichageGraphe()
print
g.ajouterArc('K','K')
g.affichageGraphe()
print
g.ajouterSommet('muun')
g.affichageGraphe()
g.ajouterSommet('Z')
g.affichageGraphe()
print
g.ajouterArc('Z','Q')
g.affichageGraphe()
print
g.ajouterSommet('UU')
g.affichageGraphe()
print
g.ajouterArc('Z','Z')
g.affichageGraphe()
g.ajouterArc('Z','Q')
g.affichageGraphe()
g.ajouterArc('Z','UU')
g.affichageGraphe()

print
g.affichageGraphe(1)

g.enregistrerGraphe('objo')
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 8
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
3 nov. 2011 à 09:37
Remarque importante:
la doc de csv.writer dit:
" All other non-string data are stringified with str() before being written.
"

Or, aussi bien ton code que le mien acceptent des valeurs numériques comme symboles des sommets, ce qui entraine deux problèmes potentiels:
1/ lors de l'enregistrement d'un graphe dans un fichier CSV , ces valeurs numériques vont être enregistrées dans le fichier sous forme de chaînes, et lors de la re-création d'un graphe à partir d'un fichier CSV , ces valeurs numériques ne seront pas reconstituées
2/ si on crée un sommet nommé par l'entier 12, puis un sommet nommé par la chaîne "12", il y aura deux sommets distincts 12 et "12" dans le graphe. Ca c'est OK, mais le problème c'est que lors de l'enregistrement du graphe dans un fichier CSV il y aura deux lignes identiques 12;- qui seront créées


C'est pourquoi il vaudrait mieux que tu enregistres un graphe dans un fichier en utilisant la sérialisation qu'un fichier CSV. C'est tout simple à faire: au lieu d'importer memodule csv dans Graphe et de définir enregistrerGraphe(self,filepath) , on import le module cPickle et on définit 

    def picklingGraphe(self,filepath):
        output = open(filepath+'.pkl', 'wb')
        Graphe.cPickle.dump(self,output)
        output.close()
0
Réponse 6 / 8
selver057 Messages postés 25 Date d'inscription mardi 13 septembre 2011 Statut Membre Dernière intervention 17 avril 2017
6 nov. 2011 à 11:41
Merci beaucoup pour toutes tes réponses et tous tes conseils et suggestions pour améliorer le programme. Ton code pour représenter le graphe au moyen d'un dictionnaire est vraiment très intéressant et je le garde sous le coude pour étude et éventuelle utilisation. Mais pour l'heure je préfère continuer à avancer avec mon propre code, et y apporter les améliorations que je peux. Et pour cela, tous tes posts vont m'être vraiment utiles. Je suis loin d'être un expert de la programmation. Il s'agit juste d'un petit passe-temps depuis que j'ai découvert la programmation avec python. Merci encore pour le coup de main ;)
0
Réponse 7 / 8
selver057 Messages postés 25 Date d'inscription mardi 13 septembre 2011 Statut Membre Dernière intervention 17 avril 2017
6 nov. 2011 à 15:46
Afin de pouvoir mieux comprendre ton code pourrait tu me donner des précisions sur les lignes qui suivent, stp?

1. 
 x = None

Est-ce que cela signifie bien que x est une variable qui n'a aucune valeur? 
 com = ''

Si je suis le même principe, j'imagine que la variable com équivaut à une chaîne de caractère vide.
2. 
print '- ajout de sommet  %s' % nouv_som

Est-ce que c'est la même chose que : 
 print("Ajout de sommet")
 nouv_som = (raw_input("Entrez un nouveau sommet : "))

Par ailleurs, lorsque je teste ton code, par rapport à cette ligne, python me signale qu'il y a une erreur de syntaxe (j'utilise la version 3.2 de Python) - erreur sur la deuxième apostrophe. 
 print '- ajout de sommet  %s' % x

Je rencontre le même problème avec cette ligne. Python me signale une erreur de syntaxe. Y-a-t-il une façon différente de la réécrire?
3.
  print '* ajout de relation  %s  %s  vers   %s  %s'\
                  % (ext_ini,what[ext_ini in self.sommet],ext_fin,what[ext_fin in self.sommet])

Même problème avec cette ligne (syntaxe invalide), je pense qu'il vaudrait mieux la décomposer plutôt que de tout condenser dans une seule ligne.
0
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
6 nov. 2011 à 16:54
1. Si tu veux acquérir une bonne compréhension de Python, je te propose de t'habituer à voir les instructions selon ce qu'il en est réellement des mécanismes sous-jacents, je veux dire ce qui concerne le data model et l'execution model de Python, sur lesquels tu tireras grand profit de lire les sections suivante de la doc:

la partie 3.1 de
https://docs.python.org/3/reference/datamodel.html#objects-values-and-types

la partie 4.1 de
https://docs.python.org/3/reference/executionmodel.html#naming-and-binding


Ca n'a rien de compliqué:

quand on écrit une instruction x = 12 , on appelle cette instruction un assignement.

Lors d'un assignement il se passe ceci:


- un objet destiné à représenter le concept entier 12 est créé dans la mémoire (la RAM) . Je noterai cet objet 12 tandis que sa valeur sera 12.

Cet objet est une zône mémoire qui tient le registre du type de l'objet (ici un entier) et de la valeur qu'il représente (ici 12).
Cette zône mémoire est située à une localisation donnée dans la mémoire dont on peut obtenir l'adresse par l'expression id(x) où id() est une fonction


- une variable est créée pour contenir cette adresse de l'objet.

J'emploie ici le mot variable dans le sens précis de "morceau de mémoire, c'est à dire succession de bits, dont la valeur peut changer". La valeur dans une variable signifie "la succession des valeurs 0 ou 1 des bits qui constituent la variable"
Cette variable n'est rien d'autre que ce qui dans d'autres langages comme C++ est appelé "pointeur". En Python, on l'appelle plutôt une référence


- une liaison (binding en anglais) est effectué pour relier le symbole x à la référence qui pointe vers l'objet 12

Cette liaison est effectuée dans ce qui est appelé "symbol table" en anglais. J'avoue que je serais incapable d'expliquer en quoi consiste physiquement dans l'ordinateur cette "symbol table". Mais il suffit de savoir qu'il y a une telle structure qui existe bel et bien qui assure ce travail de liaison, ça rend les choses moins ésotériques, et pourtant il en est peu souvent question.

Donc une liaison est établie entre la référence et le symbole écrit x. Par habitude de ce qu'on pratique en mathématique, le symbole écrit x est de façon très générale et néamoins très reprochable appelé "variable".
Mais il ne s'agit pas de la même acception du mot variable que plus haut ! Et je trouve cet emploi erroné très regrettable, ça apporte et entretient une confusion pas possible dans les esprits et dans certaines discussions.

Donc il vaut mieux appeler x comme ce doit l'être: un identifiant. C'est ce qui est très généralkement fait dans la doc, le mot "variable" y est très rarement trouvé dans ce sens . Cf
https://docs.python.org/3/reference/lexical_analysis.html#identifiers

On peut aussi l'appeler le "nom"


Voilà. Après, on raisonne majoritairement en utilisant les notions d'identifiant et d'objet. Faire constamment le travail intellectuel de considérer tout le temps la trilogie identifiant-référence-objet serait fatigant et ce n'est pas utile.
Mais il faut toujours garder l'idée que sous le capot il y a un jeu des références constant dans un programme Python, cette idée doit rester subconsciente pour y faire appel dès que nécessaire pour comprendre certains phénomènes qui ne se passent pas en Python comme dans d'autres langages. Tu saisiras plus tard ce que je veux dire, par exemple sur les listes qui sont mutables et qui dans certaines circonstances gardent des valeurs précédentes alors qu'on pouvait croire qu'elles ne les avaient plus.


Bref.
Maintenant je peux répondre à la question:
x = None ne signifie pas que x est une variable qui n'a aucune valeur.

Cela signifie que l'identifiant x pointe (directement sous le capot vers une référence mais ) indirectement vers un objet None
Cet objet dont le nom = l'identifiant est None est un objet comme tous les autres : il est représenté dans un endroit de la mémoire par une certaine collection de bits adjacents dont la succession de valeurs est conventionnellement fixée pour représenter quelque chose ayant certaines propriétés dans un programme Python.

En fait x = None est un peu différent d'un assignement comme x = 12 car None est en soi un identifiant, à la différence de 12 dont je ne sais pas trop comment l'interpréteur Python l'interprète quand il rencontre les caractères accolés 12 dans un script, mais je ne crois pas qu'on puisse considérer que 12 est un identifiant.

Donc bref, après x = None, l'objet None est référencé par deux identifiants: None et x !


De même, si on écrit x = 12 puis y = 12 , l'objet 12 aura deux identifiants le référençant.


n truc spécial concernant l'objet None, c'est que c'est un singleton, c'est à dire qu'il ne peut exister qu'une seule zône mémoire représentant cette notion dans un programme Python en exécution. Tandis que tout autre objet peut dans certaines circonstances ne pas être représenté en mémoire qu'à un seul endroit, bien qu'en général avant de faire une création d'objet dans le cadre d'un assignement, Python cherche d'abord si l'objet à référencé n'existe pas déjà quelque part dans la mémoire.

C'est un sacré bazar n'est ce pas ? Mais tu verras, quand on a compris ce qui se passe sous le capot , c'est un vrai ballet admirable d'identifiants , de pointeurs et d'objets.

Il faut aussi savoir que le fonctionnement de Python est basé sur la notion de dictionnaire pour tenir registre de tout ce ballet. Mais bon, je ne peux pas tout expliquer d'un coup.



Pour ce qui est de
com = ''
l'identifiant com référence après cette instruction un objet qui existe bel et bien, mais dont la valeur exprime une chaîne vide. Mais l'objet n'est pas vide: il comporte le type (chaîne) et l'information que la chaîne n'a pas de caractère.
0
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
Modifié par heyquem le 6/11/2011 à 17:22
2. Lorsque l'interpréteur Python rencontre une expression comme
'- ajout de sommet %s' % nouv_som
il crée une chaîne obtenue en remplaçant les deux caractères %s par la chaîne obtenue par application de la fonction str() sur l'objet nouv_som

C'est à dire:

- si la valeur de nouv_som est une chaîne 'blabla' , la chaîne obtenue sera
'- ajout de sommet blabla'

Nota:
je devrais écrire : nouv_som est un objet de type chaîne dont la valeur est 'blabla',
ou: la valeur de la chaîne référencée par l'identifiant nouv_som est 'blabla'
pour rester cohérent avec ma précédente manière de désigner les choses.
Mais ce serait évidemment lourdingue et il faut comprendre:
la valeur de l'objet référencé indirectement (via un pointeur dont on se fiche) par l'identifiant nouv_som est la chaîne écrite 'blabla'

- si nouv_som est un nombre 135, la chaîne obtenue sera
'- ajout de sommet 135'


- si nouv_som est une liste [12,45,78] , la chaîne obtenue sera
'- ajout de sommet [12,45,78]'

etc


Il te faut regarder à : formatting dans l'index de la doc



Tu peux remplacer
'- ajout de sommet %s' % nouv_som

par
'- ajout de sommet ' + str(nouv_som)
0
heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 131
6 nov. 2011 à 17:19
2.

Avec Python 3.2, print() est une fonction dont les arguments doivent être placés entre parenthèses
0
Réponse 8 / 8
selver057 Messages postés 25 Date d'inscription mardi 13 septembre 2011 Statut Membre Dernière intervention 17 avril 2017
19 nov. 2011 à 21:11
Je me demande s'il est possible d'appliquer un algorithme de parcours en largeur (algorithme du plus court chemin) à ton programme (ou au mien qui est moins sophistiqué) ?

Je pense procéder de la façon suivante : 

def parcours(self, G, x, Gprim) :
             queue = []
             pour chaque successeur y de x faire :
                    enfiler (x,y) dans queue
             tant que queue n'est pas vide faire :
                    (i,f) = défiler(queue)
                     si f n'a pas encore été visité alors :
                           marquer f comme "visité"
                           ajouter f dans Gprim
                           ajouter l'arc (i,f) dans Gprim
                           pour chaque successeur de y de f faire :
                                    enfiler (x,y) dans queue


En plus de l'arbre couvrant calculé par l'algorithme, je souhaite :
1. calculer une table associant à chaque sommet y la distance en nombre d'arcs entre x et y,
2. on peut utiliser une liste pour représenter cette table. Si on note d cette liste et si l'indice du sommet y dans la liste de sommets du graphe est i, d[i] est alors la distance de x à y.
3. certains sommets peuvent ne pas être accessibles à partir de x. On choisit alors une valeur particulière pour noter quand cela arrive.

Pour gérer la file :
1. on peut exploiter la structure deque,
2. pour initaliser :
deque( liste ) retourne la file ; par exemple deque( [ ] ) retourne la liste vide
queue = deque( [ ] ) permet de la récupérer dans la variable queue
3. pour insérer : queue.append( valeur_a_inserer )
4. pour supprimer : valeur_a_recuperer = queue.popleft()

Si j'ai des graphes représentant des relations entre personnes, entreprises ou objets et résultant de sondages ou de relevés d'informations publiques. Ces graphes sont anonymes si bien qu'il n'est pas possible de connaître ce qu'ils représentent (ex : le graphe des envois de courrier interne entre employés au sein d'une entreprise ...).

En utilisant les résultats de l'algorithme du plus court chemin pour fournir des informations à partir du graphe :

1. Quelle peut être la longueur maximale d'un plus court chemin entre deux sommets de graphes ?
2. Existe t'il des communautés potentielles dans la population étudiée ? On peut peut être assimiler une communauté potentielle à une composante fortement connexe.

D'avance merci de m'éclairer de tes lumières.
0

Discussions similaires

comment écrire des petits chiffres ?
Elisa-x3 -
Luka_65 -

9 réponses
Générer toutes combinaisons possibles Euromillions dans Excel
pierremartins -
pierremartins -

12 réponses
Dimensions L x l x H : comment lire ces infos ?
Miss-Curieuse -
valou -

8 réponses
[Ecrire Exposant 12] 10² ou 10³ ok mais...
tessai -
rayous -

43 réponses
petit colis
tina -
Utilisateur anonyme -

6 réponses