Représentation intervallaire des arborescences et mise en oeuvre

hametsu21 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008 - 17 févr. 2008 à 23:44
hametsu21 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008 - 19 févr. 2008 à 00:51
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 (<li></li>) ou une liste de
sélection (<select><option></option></select>).

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 ;)

9 réponses

malalam Messages postés 10839 Date d'inscription lundi 24 février 2003 Statut Membre Dernière intervention 2 mars 2010 25
18 févr. 2008 à 08:02
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 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008
18 févr. 2008 à 13:00
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.

<li>Lors de l'ajout d'une page, il me faudrait un select affichant l'ensemble des pages, sous pages, etc.</li><li>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).</li>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']."\n";

// 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 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008
18 févr. 2008 à 14:33
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 <li></li> and
tags as the depth number increases and decreases.

Et ce qui coince c'est la dernière phrase, comment rajouter ces <li></li> et
lorsque la prodondeur augmente ou diminue...
hametsu21 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008
18 févr. 2008 à 15:02
ç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 '<li>' . $row['title'], $row['lvl'] . '</li>';

    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 :(

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

Posez votre question
malalam Messages postés 10839 Date d'inscription lundi 24 février 2003 Statut Membre Dernière intervention 2 mars 2010 25
18 févr. 2008 à 20:22
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 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008
18 févr. 2008 à 21:09
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 Messages postés 10839 Date d'inscription lundi 24 février 2003 Statut Membre Dernière intervention 2 mars 2010 25
18 févr. 2008 à 22:16
Vu l'heure, on verra ça demain soir, je n'ai plus très envie de coder :-) Mais demain soir je regarde.
malalam Messages postés 10839 Date d'inscription lundi 24 février 2003 Statut Membre Dernière intervention 2 mars 2010 25
18 févr. 2008 à 23:00
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 '<li>',$aFetched['NFM_LIB'], '</li>';
    } elseif($iDepth > $aFetched['parent_count']) {
        echo str_repeat('', ++$iDepth - $aFetched['parent_count']);
        $iDepth = $aFetched['parent_count'];
        echo '<li>',$aFetched['NFM_LIB'], '</li>';
    } else {
        echo '<li>',$aFetched['NFM_LIB'], '</li>';
    }
}
echo '';
hametsu21 Messages postés 37 Date d'inscription mardi 1 novembre 2005 Statut Membre Dernière intervention 24 février 2008
19 févr. 2008 à 00:51
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 >_>
Rejoignez-nous