Discussion :

[yappp]

Bonjour à vous,

Je me permets de venir ici pour avoir un peu d'aide !

J'ai une table SQL composée de 3 colonnes : id, label et id_parent

Je récupère les données dans une liste :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
conn = MySQLdb.connect('localhost','user','pass', 'db') 
curs = conn.cursor() 
result=curs.execute("SELECT ....") 
 
cats = curs.fetchall() 
 
curs.close() 
conn.close()

J'aimerais transformer cette liste en dictionnaire de dictionnaires 'hiérarchisé', ressemblant à ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
dict = {"Cat1": {}, "Cat2": {"Cat21": {"Cat211": {"Cat2111": {}}}, "Cat22": {}, "Cat23": {"Cat231": {}, "Cat232": {"Cat2321": {}}, "Cat233" :{}}}}

De plus, il est possible que la colonne 'id_parent' possède plusieurs id .. !

Peut-être existe t'il un moyen d'effectuer ceci en passant directement de SQL à un dictionnaire ?

Je remercie d'avance pour votre aide !

[tyrtamos]

Bonjour,

Ce genre de problème est souvent résolu par une fonction récursive, mais là, on n'en connait pas suffisamment. Par exemple: comment trouver les id qui n'ont pas de parent? Est-il exclu que ça boucle? Etc...

Il faut monter un exemple (seulement la liste issue de fetchall) avec des données bidon , mais qui montre toutes les facettes du problème. Avec le résultat attendu.

[yappp]

Bonjour,

Voici les infos nécessaires :

Jusqu'à présent ma table se présentait comme ceci : (avec un id_parent égal à '0' pour les premiers éléments)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
--
-- Structure de la table `test`
--
 
CREATE TABLE IF NOT EXISTS `test` (
  `id_block` int(11) NOT NULL AUTO_INCREMENT,
  `label` varchar(30) NOT NULL,
  `id_parentblock` int(11) NOT NULL,
  PRIMARY KEY (`id_block`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=12 ;# MySQL a retourné un résultat vide (aucune ligne).
 
--
-- Contenu de la table `test`
--
 
INSERT INTO `test` (`id_block`, `label`, `id_parentblock`) VALUES
(1, 'Cat1', 0),
(2, 'Cat2', 0),
(3, 'Cat3', 2),
(4, 'Cat4', 2),
(5, 'Cat5', 3),
(6, 'Cat6', 4),
(7, 'Cat7', 2);

Or après réflexion, puisque qu'il est possible d'avoir plusieurs parents, je viens de décomposer la table en deux tables pour éviter d'avoir à parser:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
--
-- Structure de la table `test`
--
 
CREATE TABLE IF NOT EXISTS `test` (
  `id_block` int(11) NOT NULL AUTO_INCREMENT,
  `label` varchar(30) NOT NULL,
  PRIMARY KEY (`id_block`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=12 ;
 
--
-- Contenu de la table `test`
--
 
INSERT INTO `test` (`id_block`, `label`) VALUES
(1, 'Cat1'),
(2, 'Cat2'),
(3, 'Cat3'),
(4, 'Cat4'),
(5, 'Cat5'),
(6, 'Cat6'),
(7, 'Cat7');

et:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
--
-- Structure de la table `test2`
--
 
CREATE TABLE IF NOT EXISTS `test2` (
  `id_block` int(11) NOT NULL,
  `id_parent` int(11) NOT NULL,
  PRIMARY KEY (`id_block`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;
 
--
-- Contenu de la table `test2`
--
 
INSERT INTO `test2` (`id_block`, `id_parent`) VALUES
(1, 0),
(2, 0),
(3, 2),
(4, 2),
(5, 3),
(6, 4),
(7, 2);

Ma requête SQL :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT T.id_block, T2.id_block, label, id_parent
FROM test T 
INNER JOIN test2 T2 ON T.id_block = T2.id_block

Ainsi la liste issue du script python est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
cats = ((1L, 1L, 'Cat1', 0L), (2L, 2L, 'Cat2', 0L), (3L, 3L, 'Cat3', 2L), (4L, 4L, 'Cat4', 2L), (5L, 5L, 'Cat5', 3L), (6L, 6L, 'Cat6', 4L), (7L, 7L, 'Cat7', 2L))

Et le résultat souhaité serait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
dict = {"Cat1": {}, "Cat2": {"Cat3": {"Cat5": {}}, "Cat4": {}, "Cat7": {}}}

Il n'est pas exclu qu'il y ait des boucles ! (si c'est bien ça votre question ?)

Merci pour votre aide !

[tyrtamos]

Bonjour,

Voilà un petit code qui a l'air de résoudre l'exemple donné. Je n'ai pas creusé plus loin, et je n'ai pas tenu compte des éventuelles boucles: considère ça comme un code de principe à valider/compléter.

Et quand j'ai comparé le résultat obtenu avec celui que tu donnes, je me suis aperçu que ce dernier était faux: il te manque "cat6".

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#! /usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import division
# Python v2.7
 
#############################################################################
def _creadict(c, d={}):
 
    # recherche des enfants
    for cle in d:
        for cat, catpar in c:
            if catpar==cle:
                d[cle][cat] = {}
        # recherche récursive
        d[cle] = _creadict(c, d[cle])        
 
    return d
 
#============================================================================
def creadict(cats):
 
    # simplification de la liste => [[cat, catparent], ...]
    c = []
    for i, (id1, id2, cat, idpar) in enumerate(cats):
        if idpar==0:
            c.append([cat, 0])
        else:
            for elem in cats:
                if idpar==elem[0]:
                    c.append([cat, elem[2]])
                    break    
 
    # recherche des 'cat' sans parent (catpar==0)
    d = {}
    for cat, catpar in c:
        if catpar==0:
            d[cat] = {}
 
    # recherche récursive des enfants
    d = _creadict(c, d)
 
    return d
 
#############################################################################
 
cats = ((1, 1, 'Cat1', 0), (2, 2, 'Cat2', 0), (3, 3, 'Cat3', 2), (4, 4, 'Cat4', 2), (5, 5, 'Cat5', 3), (6, 6, 'Cat6', 4), (7, 7, 'Cat7', 2))
 
d = creadict(cats)
print d

Ce qui donne le résultat:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

{'Cat1': {}, 'Cat2': {'Cat3': {'Cat5': {}}, 'Cat4': {'Cat6': {}}, 'Cat7': {}}}

Ok?

[yappp]

Tout simplement suuuuper.
Merci ! Il fonctionne parfaitement dans mon cas !

Je me pose juste une question, à quoi sert l'import ? car le script semble fonctionner sans !

Et merci encore !

[tyrtamos]

à quoi sert l'import ? car le script semble fonctionner sans !

Pour moi, c'est du standard, et je le met systématiquement, utile ou pas. Avec Python 2.x, la division entre 2 entiers est un entier (10/3=>3), et moi je veux que ce soit un flottant (10/3=>3.333333333333333), ce qui est le cas maintenant avec Python 3.x.

A part ça, je suis ravi que ma solution te convienne. Garde le principe, car on retrouve ça de temps en temps: comment transformer une liste de liens de filiation en arbre.

Mais ça peut devenir très compliqué en cas de boucle, c'est à dire quand un id a pour parent un de ses enfants: imagine le code si on ne peut pas trouver d'ancêtre (id sans parent). Et la boucle pourrait être seulement locale: comment la détecter pour éviter justement au code de "boucler"?

[yappp]

Merci pour ton explication.

Oui j'ai bien compris la technique, ceci me sera certainement utile dans d'autres projets mais aussi pour aider des personnes qui ont ce besoin.. !

Après discussion, ce cas ne pourra être possible dans mon projet ! (ouf)
En effet, ceci semble donnée un bon cran de difficulté en plus !

Merci encore pour ton aide,
Bonne continuation,

[dividee]

Bonjour,

D'abord une petite remarque: la définition SQL de la table test2 ne permet pas d'avoir plusieurs parents car la clé primaire n'est mise que sur id_block; il faudrait la mettre sur les deux champs (id_block, id_parent).

Voici mon code pour construire la structure:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cats = ((1L, 1L, 'Cat1', 7L),
        (2L, 2L, 'Cat2', 2L),
        (3L, 3L, 'Cat3', 2L),
        (4L, 4L, 'Cat4', 2L),
        (4L, 4L, 'Cat4', 5L),
        (5L, 5L, 'Cat5', 3L),
        (5L, 5L, 'Cat5', 4L),
        (6L, 6L, 'Cat6', 4L),
        (7L, 7L, 'Cat7', 2L))
 
h = {c[0] : {} for c in cats}
 
roots = {}
 
for _, id, name, parent_id in cats:
    if parent_id == 0:
        roots[name] = h[id]
    else:
        h[parent_id][name] = h[id]

La simplicité vient du travail avec des références à des dictionnaires mutables...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
>>> roots
{'Cat1': {},
 'Cat2': {'Cat3': {'Cat5': {'Cat4': {'Cat5': {...},
                                     'Cat6': {}}}},
          'Cat4': {'Cat5': {'Cat4': {...}},
                   'Cat6': {}},
          'Cat7': {}}}

Comme le montre l'exemple, il fonctionne aussi s'il y a plusieurs parents et même s'il y a des boucles, mais dans ce cas-là, il se peut qu'il n'y ait pas toutes les racines (voir aucune). Il faudrait alors choisir arbitrairement une racine pour chaque composante connexe, mais je n'ai pas été jusque là...

Il faudra bien sûr se méfier lors du parcours de ce dictionnaire (ce que fait bien l'interpréteur python en affichant {...} quand il détecte une boucle), et se méfier des memory leaks...

[yappp]

Oui en effet.. je l'avais corrigé mais je ne l'ai pas reporté dans mon énoncé merci de la remarque.

Ton script est très intéressant, je suis impressionné.. Je n'aurais jamais pensé à créer quelque chose comme ceci !

Merci beaucoup pour ton aide.