Représentation intervallaire des arborescences et mise en oeuvre

Question

Bonjour, après de nombreuses recherches je n'arrive toujours pas réellement à comprendre comment mettre en œuvre une arborescence dans une table mysql . j'ai une table `pages` où j'ajoute comme le nom de la table l'indique des ... pages ! une page peut avoir plusieurs "enfants" et appartenir à un "parent", chaque "enfant" peut être "parent" de plusieurs autres "enfants" etc... j'ai lu un étonnant article sur les "représentation intervallaire des arborescences" : lire l'article Mais je ne vois pas réellement comment l'utiliser pour créer par exemple une liste (

) ou une liste de sélection (). Si vous pouviez ne serais-ce que m'aiguiller ou me fournir d'autres liens afin que je poursuive mes recherches ça serait cool :D Au revoir ! PS : je tiens à préciser que c'est pour un projet d'étude et pas une lubie ;)

malalam · Answer

Hello,

l'article est en effet intéressant.
Et le principe fort simple!
Qu'est ce que tu ne comprends pas là-dedans ? 
Commence par coucher sur papier ton arbo (le deuxième type de représentation me semble plus simple pour ça), note tes bordures gauche et droite pour chaque feuille et noeud, le reste devrait être évident. Un exemple linéaire :
dossier : 1-6
sous-dossier : 2-5
fichier : 3-4

mettons que ton fichier ait un id = 3
pour reproduire l'arbo :
SELECT * FROM arbo WHERE (BG < 3 AND bd > 4) OR id = 3
(en pratique, on procèdera différemment sans doute, dans le cadre d'un script dynamique).

Le défaut de cette représentation, à garder en mémoire, c'est qu'il faut une arbo complète : difficile d'ajouter une profondeur en cours de route (par contre, on peut ajouter des noeuds et des feuilles si on ne sort pas de l'intervalle défini au départ).

hametsu21 · Answer

Oui, j'ai bien compris le principe qu'un noeud englobe d'autres noeuds / éléments mais là ou je coince est par exemple pour ajouter une page ou générer le menu.

Lors de l'ajout d'une page, il me faudrait un select affichant l'ensemble des pages, sous pages, etc.

Sur la page index, il me faudrait le menu générer avec des listes et dont les noeuds / éléments fils sont cachés jusqu'au clic de l'utilisateur (en javascript, pas un problème).

Pour mieux t'illustrer mon problème function display_tree($root) { // retrieve the left and right value of the $root node $result = mysql_query('SELECT lft, rgt FROM tree '. 'WHERE title="'.$root.'";'); $row = mysql_fetch_array($result); // start with an empty $right stack $right = array(); // now, retrieve all descendants of the $root node $result = mysql_query('SELECT title, lft, rgt FROM tree '. 'WHERE lft BETWEEN '.$row['lft'].' AND '. $row['rgt'].' ORDER BY lft ASC;'); // display each row while ($row = mysql_fetch_array($result)) { // only check stack if there is one if (count($right)>0) { // check if we should remove a node from the stack while ($right[count($right)-1]<$row['rgt']) { array_pop($right); } } // display indented node title echo str_repeat(' ',count($right)).$row['title']." "; // add this node to the stack $right[] = $row['rgt']; } } Cette fonction permet d'afficher un noeud à partir d'un nom de noeud passé en paramètre, elle répéte des espaces pour indenter les différents noeuds / éléments. A la place, il faudrait que je trouve comment afficher un select ou une liste, donc de générer un tableau pour ensuite le parcourir à l'aide de foreach. De plus, j'ai l'impression que ce système nécessite un élément "root". Y'a peut être plus simple ? mes noeuds pourrait avoir des centaines d'éléments, et une profondeur d'environ 5 niveaux, la majorité des requête serait des selects (75%)... Si vous avez eu le courage de tout lire eet que vous avez compris ! Je vous tire mon chapeau :p

hametsu21 · Answer

J'ai vu ça aussi : We can use the depth value to indent our category names with the CONCAT and REPEAT string functions: SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name FROM nested_category AS node, nested_category AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY node.lft; +-----------------------+ | name | +-----------------------+ | ELECTRONICS | | TELEVISIONS | | TUBE | | LCD | | PLASMA | | PORTABLE ELECTRONICS | | MP3 PLAYERS | | FLASH | | CD PLAYERS | | 2 WAY RADIOS | +-----------------------+ Of course, in a client-side application you will be more likely to use the depth value directly to display your hierarchy. Web developers could loop through the tree, adding

and tags as the depth number increases and decreases. Et ce qui coince c'est la dernière phrase, comment rajouter ces

et lorsque la prodondeur augmente ou diminue...

hametsu21 · Answer

ça devrait donner un truc dans le genre... $query = 'SELECT `node`.`title`, (COUNT(`parent`.`title`) - 1) AS `lvl`' . ' FROM `tree` AS `node`, `tree` AS `parent`' . ' WHERE `node`.`lft` BETWEEN `parent`.`lft` AND `parent`.`rgt`' . ' GROUP BY `node`.`title` ORDER BY `node`.`lft`'; $result = mysql_query ($query) or die (mysql_error ()); $lvl = 0; while ($row = mysql_fetch_assoc ($result)) { if ($row['lvl'] > $lvl) { $lvl = $row['lvl']; echo ''; } echo '

' . $row['title'], $row['lvl'] . '

'; if ($row['lvl'] < $lvl) { echo ''; $lvl--; } } mais ça me donne pas le résultat attendu, et le must serait de mettre tout sous forme d'un immense tableau ou je testerai une valeur pour en extraire les enfants... enfin bref, cela reste utopique :(

malalam · Answer

Hello,

attention : cet algo n'est PAS fait pour une arbo que tu es amenée à modifier fréquemment. Nref, l'ajout de pages, par exemple, sera une plaie avec ce système.
En général, dans une arbo, on a une racine...mais tu n'es pas obligé d'en avoir une avec ce principe, non.
C'est une arbo purement SQL...si tu as besoin de la retravailler en php...autant ne pas utiliser cet algo. 
Ca reste possible...mais pas comme tu le fais ;-)
Si tu veux que je t'aide plus avant, comme j'ai la flemme de le faire moi-même, balance moi un create table avec ce que tu testes, les INSERT qui vont bien afin que j'ai une base toute prête.
Et je jetterai un oeil.

hametsu21 · Answer

Par exemple :


-- 
-- Table structure for table `NEW_FAMILLE`
-- 

CREATE TABLE `NEW_FAMILLE` (
  `NFM_ID` int(11) NOT NULL auto_increment,
  `NFM_BG` int(11) default NULL,
  `NFM_BD` int(11) default NULL,
  `NFM_LIB` varchar(16) default NULL,
  PRIMARY KEY  (`NFM_ID`)
);;

-- 
-- Dumping data for table `NEW_FAMILLE`
-- 

INSERT INTO `NEW_FAMILLE` VALUES (1, 1, 44, 'Transport');
INSERT INTO `NEW_FAMILLE` VALUES (2, 2, 21, 'Aérien');
INSERT INTO `NEW_FAMILLE` VALUES (3, 3, 4, 'Planeur');
INSERT INTO `NEW_FAMILLE` VALUES (4, 5, 6, 'Parachute');
INSERT INTO `NEW_FAMILLE` VALUES (5, 7, 8, 'Hélico');
INSERT INTO `NEW_FAMILLE` VALUES (6, 9, 10, 'Fusée');
INSERT INTO `NEW_FAMILLE` VALUES (7, 11, 12, 'ULM');
INSERT INTO `NEW_FAMILLE` VALUES (8, 13, 20, 'Avion');
INSERT INTO `NEW_FAMILLE` VALUES (9, 14, 15, 'Militaire');
INSERT INTO `NEW_FAMILLE` VALUES (10, 16, 17, 'Tourisme');
INSERT INTO `NEW_FAMILLE` VALUES (11, 18, 19, 'Civil');
INSERT INTO `NEW_FAMILLE` VALUES (12, 22, 35, 'Terrestre');
INSERT INTO `NEW_FAMILLE` VALUES (13, 23, 24, 'Vélo');
INSERT INTO `NEW_FAMILLE` VALUES (14, 25, 26, 'Voiture');
INSERT INTO `NEW_FAMILLE` VALUES (15, 27, 28, 'Camion');
INSERT INTO `NEW_FAMILLE` VALUES (16, 29, 34, 'Moto');
INSERT INTO `NEW_FAMILLE` VALUES (17, 30, 31, 'Side-car');
INSERT INTO `NEW_FAMILLE` VALUES (18, 32, 33, 'Trail');
INSERT INTO `NEW_FAMILLE` VALUES (19, 36, 43, 'Marin');
INSERT INTO `NEW_FAMILLE` VALUES (20, 37, 38, 'Planche à voile');
INSERT INTO `NEW_FAMILLE` VALUES (21, 39, 40, 'Paquebot');
INSERT INTO `NEW_FAMILLE` VALUES (22, 41, 42, 'Voilier');


Si tu arrives a créer une liste ordonner de chaque noeuds, enfants, éléments, etc. je te tire ma révérence ^^
Merci de ton aide :)

malalam · Answer

Vu l'heure, on verra ça demain soir, je n'ai plus très envie de coder :-) Mais demain soir je regarde.

malalam · Answer

Bon...finalement je l'ai fait ;-) $sQuery = " SELECT node.NFM_LIB, count(parent.NFM_LIB) as parent_count FROM NEW_FAMILLE AS node, NEW_FAMILLE AS parent WHERE node.NFM_BG BETWEEN parent.NFM_BG AND parent.NFM_BD GROUP BY node.NFM_LIB ORDER BY node.NFM_BG "; $rQry = mysql_query($sQuery); $iDepth= 0; echo ''; while($aFetched = mysql_fetch_assoc($rQry)) { if($iDepth < $aFetched['parent_count']) { echo str_repeat('', $aFetched['parent_count'] - $iDepth); $iDepth = $aFetched['parent_count']; echo '

',$aFetched['NFM_LIB'], '

'; } elseif($iDepth > $aFetched['parent_count']) { echo str_repeat('', ++$iDepth - $aFetched['parent_count']); $iDepth = $aFetched['parent_count']; echo '

',$aFetched['NFM_LIB'], '

'; } else { echo '

',$aFetched['NFM_LIB'], '

'; } } echo '';

hametsu21 · Answer

c'est un sacré ... bordel :D
je peux faire aucune séparation code/présentation à ce niveau et je me vois mal comment nommer les ul pour qu'avec javascript je cache les noeuds enfants T_T.
Par contre... Chapeau, ça l'air de foncionner.
Quelle méthode me conseille, au vu de ton expérience, pour réaliser ceci :
système de page

- ajouter une page
- supprimer une page
- editer une page

- une page peut se reférrer à une autre pouvant créer un système de catégorie, article, chapitre, section, paragraphe etc..

Je pense que j'ai pas finis d'angoisser >_>

Représentation intervallaire des arborescences et mise en oeuvre

9 réponses

Votre réponse