Alors voilà je veux tout simplement déclarer un graphe orienté (et éventuellement cyclique). Mon but est de permettre de déclarer un grand nombre de nœuds, à la main, sans trop se prendre la tête...
Tout de suite s'est posé un problème de NameError, je me suis dis que je trouverais vite une solution (ça me semble être un problème courant), mais j'en suis au point de demander ici.
Donc voilà entrès gros ma première idée:
class Node:
def __init__(self,label,fathers):
self.label=label
self.fathers=fathers
self.sons=list()
for f in self.fathers:
f.sons.append(self)
Sauf que bien entendu si je veux faire un cycle :
a=Node('',[])
b=Node('',[a,d])
c=Node('',[a,b])
d=Node('',[c])
>>> NameError: name 'd' is not defined
Une solution toute donnée serait de déclarer des nœuds vides dans un premier temps :
class Node:
def __init__(self,label='',fathers=[]):
self.label=label
self.fathers=fathers
self.sons=list()
for f in self.fathers:
f.sons.append(self)
def set(self,label,fathers):
self.label=label
self.fathers=fathers
for f in self.fathers:
f.sons.append(self)
d=Node()
a=Node('',[])
b=Node('',[a,d])
c=Node('',[a,b])
d.set('',[c])
Mais je me demandais s'il n'existait pas un autre moyen, plus élégant, moins galère par ce que je voudrait faire un grand nombre de déclaration au clavier.
N'hésitez pas également à critiquer ce système d'instanciation père/fils ; je n'y ai pas vu d’inconvénients mais il y en a peut-être...
En fait, il faut se servir de votre classe, après les avoir créés....
Exemple:
class Node(object):
def __init__(self, label):
self.label = label
self.fathers = []
self.sons = []
def add_fathers(self, fathers):
self.fathers = fathers
for f in self.fathers:
f.sons.append(self)
a = Node(1)
b = Node(2)
c = Node(5)
d = Node(6)
b.add_fathers([a,d])
c.add_fathers([a,b])
d.add_fathers([c])
print('FATHER_A:', a.__dict__)
for son in a.sons:
print('SON_A:', son.__dict__)
Merci nolimitech ! mais cela ressemble à ma solution de départ. Mon problème étant que justement je voulais savoir (peut-être simplement par curiosité ) s'il n'y avait pas une solution propre pour diviser par deux le nombre de mes lignes d'instanciations.
Ou en faisant un schmilblick dans l'__init__, un truc comme ça :
except NameError as e:
name=e.__str__()[6:-16] # Si qqun sait comment récup le nom de la variable inconnue plus proprement...
globals()[name]=Node(label='node')
blablablabla
MrFoxtrot a écrit:
> Merci nolimitech ! mais cela ressemble à ma solution de départ. Mon problème étant que justement je voulais savoir (peut-être simplement par curiosité ^^) s'il n'y avait pas une solution propre pour diviser par deux le nombre de mes lignes d'instanciations.
Tu ne pourras en tout cas pas déclarer simultanément deux variables qui se référencent cycliquement.
Il y a deux solutions à ce problème :
La première, que tu connais, qui est de déclarer les nœuds vides et de les lier ensuite.
La seconde, de ne pas référencer les nœuds en eux-mêmes mais de leur assigner un nom (le label), d'utiliser ce nom pour les référencer et d'avoir un index de tous les nœuds.
Mais ton second problème, c'est aussi que des références inverses (des parents vers les enfants) se mettent aussi automatiquement en place. Ça, tu ne pourras pas le faire uniquement avec un nom, il faudra posséder les deux objets, donc ça bloquera.
Encore une fois, ce n'est pas sans solution, mais il faudra revoir la manière dont tu organises tes liaisons.
Ce que je te propose, c'est d'externaliser ça dans une classe qui gérerait le graphe plutôt que dans les nœuds.
Un exemple de ce que pourrait donner cette solution :
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = {}
self.links = defaultdict(list)
self.rev_links = defaultdict(list)
def node(self, label, parents_labels=[]):
node = self.nodes[label] = Node(self, label)
for plabel in parents_labels:
self.links[plabel].append(label)
self.rev_links[label].append(plabel)
return node
class Node:
def __init__(self, graph, label):
self.graph = graph
self.label = label
@property
def children(self):
g = self.graph
return [g.nodes[p] for p in g.links[self.label]]
@property
def parents(self):
g = self.graph
return [g.nodes[p] for p in g.rev_links[self.label]]
g = Graph()
a = g.node('a')
b = g.node('b', ['a', 'd'])
c = g.node('c', ['a', 'b'])
d = g.node('d', ['c'])
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = {}
self.links = defaultdict(list)
def __getitem__(self, index):
return self.nodes[index]
def node(self, name, label, sons_names=[]):
self.nodes[name] = Node(self, name, label)
for n in sons_names:
self.links[name].append(n)
class Node:
def __init__(self, graph, name, label):
self.graph = graph
self.label = label
self.name = name
@property
def sons(self):
g = self.graph
return [g.nodes[s] for s in g.links[self.name]]
def __repr__(self):
return self.name
g = Graph()
g.node('a','label')
g.node('b','label', ['a', 'd'])
g.node('c','label', ['a', 'b'])
g.node('d','label', ['c'])
Je rajoute un 'name' en plus du label car deux nœuds pourrais avoir une même valeur. Dans mon programme précisément je ne pense pas avoir besoin de sauver le liens inverse finalement. Donc je ne garde que les enfants. Cette solution est élégante et je suis ravi de découvrir collections.defaultdict
Si tu n'as finalement pas besoin des références inverses, tu peux te contenter de stocker les noms des fils dans le nœud plutôt que dans le graphe.
Ce qui empêchait de procéder ainsi dans mon exemple était que tu voulais aussi stocker des informations dans le fils (la référence inverse), et donc que ce dernier se devait d'exister.
(j'ai utilisé un tuple comme valeur par défaut du paramètre plutôt qu'une liste pour éviter les soucis de multiples références sur un même objet mutable)
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique