tracer un arbre à partir d’une expression NPI
NPI : notation polonaise inversée
En particulier : on dispose d’une expression en NPI, du type :
L3 = [7,8,'-',6,'*',10,3,'+','*']
Et on veut créer et afficher le graphe correspondant :
On utilisera le script :
L3 = [7,8,'-',6,'*',10,3,'+','*']
D = makeTree(L3)
G = nx.Graph()
graphDict(D)
Dont l’instruction suivante va générer le dictionnaire à partir de l’expression NPI (fonction npiTree recursive):
D = makeTree(L3)
D
# affiche {'*': ({'*': ({'-': (7, 8)}, 6)}, {'+': (10, 3)})}
Ce dictionnaire peut être alors parcouru avec des elgorithmes recursifs, comme par exemple celui de la fonction createEdges qui est un parcours en profondeur.
Le script permet aussi de créer une structure intermédiaire sous forme de dictionnaire, et permet d’afficher le graphe à partir de tout dictionnaire D :
G = nx.Graph()
graphDict(D)
Le graphe est dans le format networkx. On pourra consulter la notice à l’adresse suivante :
def hierarchy_pos(G, root=None, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5):
'''
From Joel's answer at https://stackoverflow.com/a/29597209/2966723.
Licensed under Creative Commons Attribution-Share Alike
If the graph is a tree this will return the positions to plot this in a
hierarchical layout.
G: the graph (must be a tree)
root: the root node of current branch
- if the tree is directed and this is not given,
the root will be found and used
- if the tree is directed and this is given, then
the positions will be just for the descendants of this node.
- if the tree is undirected and not given,
then a random choice will be used.
width: horizontal space allocated for this branch - avoids overlap with other branches
vert_gap: gap between levels of hierarchy
vert_loc: vertical location of root
xcenter: horizontal location of root
'''
if not nx.is_tree(G):
raise TypeError('cannot use hierarchy_pos on a graph that is not a tree')
if root is None:
if isinstance(G, nx.DiGraph):
root = next(iter(nx.topological_sort(G))) #allows back compatibility with nx version 1.11
else:
root = random.choice(list(G.nodes))
def _hierarchy_pos(G, root, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5, pos = None, parent = None):
'''
see hierarchy_pos docstring for most arguments
pos: a dict saying where all nodes go if they have been assigned
parent: parent of this branch. - only affects it if non-directed
'''
if pos is None:
pos = {root:(xcenter,vert_loc)}
else:
pos[root] = (xcenter, vert_loc)
children = list(G.neighbors(root))
if not isinstance(G, nx.DiGraph) and parent is not None:
children.remove(parent)
if len(children)!=0:
dx = width/len(children)
nextx = xcenter - width/2 - dx/2
for child in children:
nextx += dx
pos = _hierarchy_pos(G,child, width = dx, vert_gap = vert_gap,
vert_loc = vert_loc-vert_gap, xcenter=nextx,
pos=pos, parent = root)
return pos
return _hierarchy_pos(G, root, width, vert_gap, vert_loc, xcenter)
import matplotlib.pyplot as plt
import networkx as nx
import re
def deversepile(p1,p2):
while p1!=[]:
p2.append(p1.pop())
return p2
def npiTree(L):
"""transforme l'expression NPI en un dictionnaire
respectant les priorités de calcul
Attention : la liste doit d'abord être mise à l'envers
Utilise un algorithme recursif
Params :
--------
L : list : expression NPI
Returns :
---------
dictionnaire
exemple :
---------
[7,8,'-',6,'*',10,3,'+','*'] => {'*': ({'*': ({'-': (7, 8)}, 6)}, {'+': (10, 3)})}
"""
#print('npiTree')
if len(L)==1: # condition d'arret de l'appel recursif
return L[0]
fg = L.pop()
fd = L.pop()
pere = L.pop()
#print('L : {}'.format(L))
D={}
if pere in ['*','+','-']: # données sous la forme : 'op',fg,fd
D[pere]=fg,fd
L.append(D)
else : # données sous la forme : 'op0',('op1',fg1,fd1),fg0 => 'op0',fg0,fg0
fg0 = fg
fg1 = fd
fd1 = pere
pere1 = L.pop()
D[pere1]=fg1,fd1
L.append(D)
L.append(fg0)
#print('L : {}'.format(L))
return npiTree(L)
def makeTree(L_NPI):
"""transforme liste issue d'une NPI
en un dictionnaire D
La liste est d'abord mise à l'envers avec deversepile
puis on appelle la fonction npiTree
Params :
--------
L_NPI : liste
Returns :
---------
D : dictionnaire à transformer en graphe
"""
D={}
p1 = []
deversepile(L_NPI,p1)
D = npiTree(p1)
return D
def decoupe(texte):
"""transforme la chaine de caractere correspondant au dictionnaire de l'arbre
en une liste
Params :
--------
texte : string : la chaine à découper
Returns :
---------
texte_decoupe : la liste
"""
texte_decoupe = list(re.findall('[{}():,*+-]|\w+',texte))
return texte_decoupe
def creerNodes(D):
"""modifie la liste ou chaque item (valeur numerique ou operateur) est remplacé par le no de noeud
on créé aussi le noeud et son etiquette à partir de l'item
Params :
--------
D : dict : dictionnaire correspondant a l'arbre
Returns :
---------
eval(chaine) : dict : dictionnaire avec les no de noeud à la place des items
"""
texte = decoupe(str(D))
index = 1
for i,c in enumerate(texte):
if c[0] in ['*','+','-','0','1','2','3','4','5','6','7','8','9']:
G.add_node(index,label=c)
texte[i]=str(index)
index+=1
chaine = ''.join(texte)
return eval(chaine)
def createEdges(D,key0=None):
"""créé une liste de tuple correspondant aux aretes de l'arbre
l'algorithme utilise un parcours en profondeur recursif et ajoute la nouvelle arete
à une liste LL
Params :
--------
D : dict : represente l'arbre à parcourir
key0 : list ou int : le noeud parent
Returns :
---------
LL[0] : contient un seul element : la liste de toutes le aretes
tous les operateurs sont mis dans une liste de 1 élément. Il faudra sortir ces elements de la liste pour pouvoir
acceder au aretes seuls.
"""
if not isinstance(D,dict):
#print((key0,D))
LL.append((key0,D))
return LL[0]
else:
key = list(D.keys())
#return key
if key0!=None :
#print((key0,key))
LL.append((key0,key))
createEdges(D[key[0]][0],key)
createEdges(D[key[0]][1],key)
def graphDict(D):
"""construction du graphe G au format de la lib networkx
et affiche le graphe
Params :
--------
D : dict issu de la chaine NPI ou autre
Returns :
---------
G : graphe format networkx
"""
Dnum =creerNodes(D)
global LL # necessaire pour utiliser LL dans la fonction createEdges recursive
LL=[]
createEdges(Dnum)
# arranger le format des elements de la liste d'aretes (suprimer le format list de certains elements)
for i,c in enumerate(LL):
c0 = c[0]
c1 = c[1]
if isinstance(c0,list):c0=c[0][0]
if isinstance(c1,list):c1=c[1][0]
c = c0,c1
LL[i]=c
#print(LL)
# Dict d'etiquette des noeuds
liste = list(G.nodes(data='label'))
labels_nodes = {}
for noeud in liste:
labels_nodes[noeud[0]]=noeud[1]
#labels_nodes
G.root = 1
G.add_edges_from(LL)
#print(list(G.edges()))
pos1 = hierarchy_pos(G,G.root)
nx.draw(G, pos=pos1, labels=labels_nodes, with_labels=True, font_size=15, font_family='sans-serif', node_color='pink',alpha=0.9)
plt.savefig('datas/NPI1.png')
plt.show()
return G
# expression NPI
L3 = [7,8,'-',6,'*',10,3,'+','*']
D = makeTree(L3)
G = nx.Graph()
graphDict(D)
<networkx.classes.graph.Graph at 0x7fc60ce94a10>
list(G.nodes(data='label'))
[(1, '*'),
(2, '*'),
(3, '-'),
(4, '7'),
(5, '8'),
(6, '6'),
(7, '+'),
(8, '10'),
(9, '3')]
list(G.edges())
[(1, 2), (1, 7), (2, 3), (2, 6), (3, 4), (3, 5), (7, 8), (7, 9)]
D
{'*': ({'*': ({'-': (7, 8)}, 6)}, {'+': (10, 3)})}
Dnum =creerNodes(D)
Dnum
{1: ({2: ({3: (4, 5)}, 6)}, {7: (8, 9)})}
