[PHP/MYSQL] Recursive tree probleem *

[Reveller]

Ik verontschuldig mij bij voorbaat voor de lengte van mijn post. Laat eenieder zich daar echter niet door afschrikken, het zijn vooral plaatjes Ik heb ze nodig om mijn probleem helder uiteen te kunnen zetten. Voor een meer ervaren PHP'er is de oplossing waarschijnlijk niet eens zo heel moeilijk? Enfin, mijn post:

Ik probeer al een aantal dagen een navigatiescript te maken, maar zit met enkele problemen, welke ook in de topics met zoekwoorden "recursive" en "tree" bijvoorbeeld niet naar voren komen. Ik zet ze hieronder zo goed mogelijk uiteen en hoop dat iemand mij een (stap in de richting van een) oplossing kan aandragen.

Ik heb de volgende MySQL tabel aangemaakt:

code:

------+--------+----------+--------------
ident | parent | haschild | email
------+--------+----------+--------------
   1  |    0   |     1    | Eten
   2  |    1   |     1    | Groenten
   3  |    1   |     1    | Fruit
   4  |    2   |     0    | Spruitjes
   5  |    2   |     0    | Witlof
   6  |    2   |     0    | Spinazie
   7  |    3   |     1    | Appels
   8  |    3   |     0    | Peren
   9  |    3   |     0    | Bananen
  10  |    3   |     0    | Druiven
  11  |    7   |     0    | Elstar
  12  |    7   |     0    | Granny Smith
------+--------+----------+--------------

Ik denk dat dit voor zich spreekt. "Eten" is de parent in deze tree en heeft twee kinderen, "Groenten" en "Fruit". Op haar beurt heeft "Fruit" weer de kinderen "Apples", "Peren", etc.

De volledige boom is:

code:

Eten
  |
  +- Groenten
  |    |
  |    +-- Spruitjes
  |    |
  |    +-- Witlof
  |    |
  |    +-- Spinazie
  |
  |
  +-- Fruit
        |
        +-- Appels
        |     |
        |     +-- Elstar
        |     |
        |     +-- Granny Smith
        |
        +-- Peren
        |
        +-- Bananen
        |
        +-- Druiven

Nu probeer ik een script te maken wat zich gedraagt als de navigatie op, bijvoorbeeld http://www.ibm.com en http://www.nl.issworld.com. Deze werken als volgt (aan de hand van dit voorbeeld):

Zijnavigatie op Homepage:

code:

Eten
+ Groenten
+ Fruit

Vervolgens klik ik bijvoorbeeld op "Fruit" en wordt dan naar http://www.mijnsite.com/index.php?node=2 gestuurd met de volgende zijnavigatie:

code:

Fruit
+ Appels
+ Peren
+ Bananen
+ Druiven

Als ik dan op "Appels" klik, wordt ik naar http://www.mijnsite.com/index.php?node=7 gerstuurd met de volgende zijnavigatie:

code:

Fruit
+ Appels
- Elstar
- Granny Smith
+ Peren
+ Bananen
+ Druiven

Klik ik vervolgens op "Elstar", dan ziet de zijnavigatie op http://www.mijnsite.com/index.php?node=11 er als volgt uit:

code:

Fruit
+ Appels
> Elstar
- Granny Smith
+ Peren
+ Bananen
+ Druiven

Twee live voorbeelden van bovenstaande situatie: http://www-1.ibm.com/indu...sp/event/scheduledevents/ en http://www.nl.issworld.com/view.asp?ID=142. Ik ga in de rest van mijn post uit van het voorbeeld bij IBM. In mijn geval zou "Fruit" bold zijn weergegeven (analoog aan Government bij IBM), Appels zou een lichtblauwe achtergrond hebben, Elsar zou een witte achtergrond hebben, en Peren, Bananen en Druiven een donkerblauwe achtergrond.

Bijvoorbeeld "Bananen" heeft geen kinderen, dus als ik naar http://www.mijnsite.com/index.php?node=9 ga, krijg ik de zijnavigatie:

code:

Fruit
+ Appels
+ Peren
- Bananen
+ Druiven

Tot nu toe heb ik het volgende geschreven:

PHP:

function writenav($node)
{
    $node = $_GET["node"];
    $query = "SELECT * FROM php_tree WHERE (parent='$node' or ident='$node') ORDER BY ident, parent";
    $result = mysql_query($query);
    $num_results = mysql_num_rows($result);
    
    echo "<!-- BEGIN: Display of branches -->\n";
    echo "<table border=1>\n";

    for ($i=0; $i<$num_results; $i++)
    {
        $row = mysql_fetch_array($result);
        echo "  <tr>\n";

        // Yes, children present
        if ($row["haschild"]=="1")
        {
            if ($node==$row["ident"])
            {
                // Root of the tree
                echo '<td>&nbsp;</td>';
                echo '<td>'.$row['email'].'</td>';
            }
            else
            {
                // Leaf with children
                $link_node = $row["ident"];
                echo '<td>+</td>';
                echo '<td><a href="?node='.$row['ident'].'">'.$row['email'].'</a></td>';
            }
        }
        else
        {
            // No, children not present
            if ($node!=$row["ident"])
            {
                //  Root of the tree without children
                echo '<td>&nbsp;</td>';
                echo '<td><a href="?node='.$row['ident'].'">'.$row['email'].'</a></td>';
            }
            else
            {
                // Leaf without children
                echo '<td>'.$row['email'].'</td>';
            }
        }

        // Show database values ...
        echo '<td width=15>'.$row['haschild'].'</td>';
        echo '<td width=15>'.$row['parent'].'</td>';
        echo '<td width=15>'.$row['ident'].'</td>';
    }
    echo "</table>";
}

Voor bijvoorbeeld writenav(1) retourneert deze functie de volgende tabel in html:

HTML:

---+----------+---+---+---
   | Eten     | 1 | 0 | 1
---+----------+---+---+---
 + | Groenten | 1 | 1 | 2
---+----------+---+---+---
 + | Fruit    | 1 | 1 | 3
---+----------+---+---+---

Tot zover gaat alles goed. Wanneer ik in deze tabel op "Fruit" Klik, gaat ook alles nog naar wens -> writenav(3) retourneert:

HTML:

---+----------+---+---+---
   | Fruit    | 1 | 1 | 3
---+----------+---+---+---
 + | Appels   | 1 | 3 | 7
---+----------+---+---+---
 + | Peren    | 0 | 3 | 8
---+----------+---+---+---
 + | Bananen  | 0 | 3 | 9
---+----------+---+---+---
 + | Druiven  | 0 | 3 | 10
---+----------+---+---+---

Maar nu komt het probleem: als ik op bijvoorbeeld "Peren" klik, retourneert writenav(8):

HTML:

+----------+---+---+---
| Peren    | 0 | 3 | 8
+----------+---+---+---

In plaats van:

HTML:

---+----------+---+---+---
   | Fruit    | 1 | 1 | 3
---+----------+---+---+---
 + | Appels   | 1 | 3 | 7
---+----------+---+---+---
 > | Peren    | 0 | 3 | 8    <--- "Peren" heeft een witte achtergrond (vgl. IBM)
---+----------+---+---+---
 + | Bananen  | 0 | 3 | 9
---+----------+---+---+---
 + | Druiven  | 0 | 3 | 10
---+----------+---+---+---

Hetzelfde gebeurt als ik op "Appels" klik. writenav(7) retourneert:

HTML:

---+--------------+---+---+---
   | Appels       | 1 | 3 | 7
---+--------------+---+---+---
   | Elstar       | 0 | 7 | 11
---+--------------+---+---+---
   | Granny Smith | 0 | 7 | 12
---+--------------+---+---+---

In plaats van

HTML:

---+--------------+---+---+---
   | Fruit        | 1 | 1 | 3
---+------------------+---+---
 + | Appels       | 1 | 3 | 7   <-- "Appels" heeft een lichtblauwe achtergrond (vgl IBM)
---+------------------+---+---
 - | Elstar       | 0 | 7 | 11  <-- "Elstar" heeft een lichtblauwe achtergrond
---+--------------+---+---+---
 - | Granny Smith | 0 | 7 | 12  <-- "Granny S" heeft een lichtblauwe achtergrond
---+--------------+---+---+---
 + | Peren        | 0 | 3 | 8
---+--------------+---+---+---
 + | Bananen      | 0 | 3 | 9
---+--------------+---+---+---
 + | Druiven      | 0 | 3 | 10
---+--------------+---+---+---

Als ik nu op "Elstar" zou klikken (writenav(11)), zou ik het volgende willen krijgen:

HTML:

---+--------------+---+---+---
   | Fruit        | 1 | 1 | 3
---+------------------+---+---
 + | Appels       | 1 | 3 | 7   <-- "Appels" heeft een lichtblauwe achtergrond (vgl IBM)
---+------------------+---+---
 > | Elstar       | 0 | 7 | 11  <-- "Elstar" heeft een witte achtergrond
---+--------------+---+---+---
 - | Granny Smith | 0 | 7 | 12  <-- "Granny S" heeft een lichtblauwe achtergrond
---+--------------+---+---+---
 + | Peren        | 0 | 3 | 8
---+--------------+---+---+---
 + | Bananen      | 0 | 3 | 9
---+--------------+---+---+---
 + | Druiven      | 0 | 3 | 10
---+--------------+---+---+---

Mijn probleem is dus duidelijk. Ik wil met een en dezelfde functie, middels het aanroepen van alleen de waarde van de node wiens pagina de bezoeker oproept (index.php?node=waarde), een zich als hierboven beschreven tree laten schrijven.

Als we stellen dat:

level 1 = eten
level 2 = groenten, fruit
level 3 = spruitjes, witlof, spinazie, appels, peren, bananen, druiven
level 4 = elstar, granny smith

dan heb ik een routine nodig die kijkt tot welk level het de gevraagde node behoort. Als dat level 4 (bijvoorbeeld "elstar") is, moet writenav() uitzoeken tot welke parent deze node behoort ("appels") en dan de overige kinderen van die parent ("granny s") opzoeken. Vervolgens de overige nodes uit het level van die parent opzoeken ("peren", "bananen", "druiven") die tot dezelfde familie ("fruit") behoren en in de tabeloutput verwerken. Ik ga er vanuit dat de tree in principe oneindig diep kan worden. Als de tree dus meer levels dan vier heeft, bijvoorbeeld 6 (waarbij elstar wordt onderverdeeld in groene en rode en groene en rode beiden worden onderverdeeld in kleine en grote), dan blijft het principe heftzelfde. De html output van writenav zou dan ongeveer als volgt moeten zijn (aangenomen dat "kleine rode elstar is aangeklikt middels writenav(19) ofzo):

HTML:

---+--------------+
   | Fruit        |
---+---------------
 + | Appels       |
---+---------------
 - | Elstar       |
---+---+----------+
   | - | rode     |
---+---+----------+
   | > | grote    |
---+---+----------+
   | > | kleine   |   <-- geselecteerd
---+---+----------+
   | - | groene   |
---+---+----------+
 - | Granny Smith |
---+--------------+
 + | Peren        |
---+--------------+
 + | Bananen      |
---+--------------+
 + | Druiven      |
---+--------------+

Ik breek er mijn hoofd nu al enkele dagen over, maak ga rond in cirkels. Ook zoeken op google heeft geen zin: ik heb tientallen artikelen gelezen en scripts bekeken, maar het heeft me niet op ideeen gebracht. Ik geef toe dat het gebruik van +, - en > niet erg consistent is. Als je een oneindig lange boom gaat uitklappen moet je goed nadenken over hoe je eea overzichtelijk houdt. Dat is echter voor de volgende stap. De reden dat ik puur html wil is dat er nog steeds bedrijven zijn die voor alle werknemers bepalen dat javascript uitstaat (in Duitsland vooral nog veel heb ik me laten vertellen). En daarbuiten: als het eenmaal werkt is het gewoon cool

Ik hoop dat er mensen zijn die mij verder kunnen helpen.

P.S. Voor als iemand het nodig heeft:

#
# Tabel structuur voor tabel `php_tree`
#

CREATE TABLE php_tree (
ident int(12) NOT NULL auto_increment,
uid int(12) NOT NULL default '0',
gui int(12) NOT NULL default '0',
parent int(12) NOT NULL default '-1',
haschild enum('0','1') NOT NULL default '0',
email varchar(80) default NULL,
UNIQUE KEY ident (ident),
KEY parent (parent)
) TYPE=ISAM PACK_KEYS=1;

#
# Gegevens worden uitgevoerd voor tabel `php_tree`
#

INSERT INTO php_tree VALUES (1, 1069541031, 999, 0, '1', 'Eten');
INSERT INTO php_tree VALUES (2, 1069541054, 999, 1, '1', 'Groenten');
INSERT INTO php_tree VALUES (3, 1069541079, 999, 1, '1', 'Fruit');
INSERT INTO php_tree VALUES (4, 1069541088, 999, 2, '0', 'Spruitjes');
INSERT INTO php_tree VALUES (5, 1069541108, 999, 2, '0', 'Witlof');
INSERT INTO php_tree VALUES (6, 1069541118, 999, 2, '0', 'Spinazie');
INSERT INTO php_tree VALUES (7, 1069541126, 999, 3, '1', 'Appels');
INSERT INTO php_tree VALUES (8, 1069541130, 999, 3, '0', 'Peren');
INSERT INTO php_tree VALUES (9, 1069541134, 999, 3, '0', 'Bananen');
INSERT INTO php_tree VALUES (10, 1069541137, 999, 3, '0', 'Druiven');
INSERT INTO php_tree VALUES (11, 1069546322, 999, 7, '0', 'elstar');
INSERT INTO php_tree VALUES (12, 1069546340, 999, 7, '0', 'granny smith');

De eigenlijke tabel bevat, zoals je ziet, wat meer gegevens dan hierboven beschreven. Met deze extra waarden gebeurt voorals nog niets. Ze zijn er voor om in de toekomst een zijnavigatie te kunnen maken aan de hand van iemand zijn inlog credentials

[ Voor 10% gewijzigd door Reveller op 28-11-2003 01:05 ]

[curry684]

100% top openingspost, maar alleen al de tekst "(GoT Search geprobeerd)" in de titel doet me jeuken om een slot hiertegenaan te gooien. Ik heb 'm maar verwijderd...

[Verwijderd]

Omdat je wel weg weet in PHP, hieronder een pseudo-PHP scriptje.

PHP:

haal vanaf de huidige node de parent op totdat je op het hoogste level zit
sla dit op in menu[];
(menu bevat dus het pad vanaf de opgegeven node naar de top van de 
boom, waarbij de top in het laatste element van de array zit)

displaychildren(count(menu)-1, 0);

function displaychildren(index,level) {
  haal alle kinderen op
  
  foreach (kinderen as kind) {
    if (kind['node'] == huidigenode) {
        display als huidige
    }
    display kleur op grond van level
    //als we nog niet op de opgevraagde node zijn aangekomen en de huidige
    //node staat in het pad van opgevraagd naar top, dan moeten de kinderen
    //afgebeeld worden...
    if (index > 0 && kind['node'] == menu[index-1]['node']) {
        toonkinderen(index-1, level+1)
    }
  }
}

Voorbeeld van het werkende script:
http://www.berger-blanc-suisse.nl/index.php?page=l5wk1

Hopelijk is dit wat je zoekt...

[ Voor 3% gewijzigd door Verwijderd op 28-11-2003 13:09 ]

[Reveller]

Jigal,

ik ga ermee aan de slag. Het vullen van menu[] moet geen probleem zijn. Ik moet alleen nog wel even twee keer naar de rest van je code kijken, en zien of ik je begrijp Zou je anders net wat uitgebreider kunnen zijn daarin? Ik ken mijn weg weliswaar enigszins in PHP, maar ben pas enkele weken bezig. Het script zoals dat in mijn openingspost staat is het resultaat van zeker een week denkwerk

[Verwijderd]

mail me ff (zie profiel), dan kan ik je wel wat meer gedetailleerde sources sturen...

[Verwijderd]

Ik heb er laatst ook nog mee gezeten en ik wilde daar een heel mooie mysql oplossing voor bedenken.

Het mooie van een join bij mysql is dat je tot maximaal 32 keer kan joinen in 1 query. Dit betekent dat je een boom kan samenstellen tot 32 levels aan diepte.

Op deze manier kun je de mysql db een tree laten generen met een pad naar de juiste nodes.

bijv

code:

node beschrijving node1 node2 node3 node4 no....
1    fruit         1
2    appels        2     1
3    elstar        3     2     1
..enz

De mysql code om dit te doen voor een diepte van 10 is(zonder node vooraf en beschrijving v/d node):

SQL:

SELECT t1.NodeId,t2.NodeId,t3.NodeId,t4.NodeId,t5.NodeId,t6.NodeId,t7.NodeId,t8.NodeId,t9.NodeId,t10.NodeId
FROM node AS t1 
LEFT JOIN node AS t2 on t1.parentID = t2.NodeId 
LEFT JOIN node AS t3 on t2.parentID = t3.NodeId
LEFT JOIN node AS t4 on t3.parentID = t4.NodeId
LEFT JOIN node AS t5 on t4.parentID = t5.NodeId
LEFT JOIN node AS t6 on t5.parentID = t6.NodeId
LEFT JOIN node AS t7 on t6.parentID = t7.NodeId
LEFT JOIN node AS t8 on t7.parentID = t8.NodeId
LEFT JOIN node AS t9 on t8.parentID = t9.NodeId
LEFT JOIN node AS t10 on t9.parentID = t10.NodeId
order by t1.nodeid

De nodes staan nu wel achterste voren:
dus ff omdraaien

PHP:

$results = mysql_query($query,db());
while ($row = @mysql_fetch_array($results))
{
  $array=array_reverse(array_unique(array($row[1],$row[2],$row[3],$row[4],$row[5],$row[6],$row[7],$row[8],$row[9],$row[10])));
  reset($array);
  list($oldKey, $oldElement) = each($array);
  unset($array[$oldKey]);
  $tree[$row[0]]=$array;


}

in $tree staat nu de hele boom. met als sleutels de waarde van de nodes.

Deze code is totaal niet geoptimaliseerd maar op deze manier heb met mysql in 1 keer ALLE nodes in je php omgeving in 1 query.

[drm]

Jigal:
mail me ff (zie profiel), dan kan ik je wel wat meer gedetailleerde sources sturen...

Ik hoop toch dat je wel begrijpt dat het fijner is als het gewoon hier besproken kan worden
[/ot]

[Tom-my]

Verwijderd schreef op 02 december 2003 @ 09:13:
Ik heb er laatst ook nog mee gezeten en ik wilde daar een heel mooie mysql oplossing voor bedenken.

..heel veel tekst ...

Eerlijk gezegd vind ik dat wel een oplossing die doeltreffend kan zijn (32 nodes tja kom je niet veel tegen denk ik zo). Maar waarom kiezen jullie niet gewoon voor een recursive functie? Ik weet dat ze pittig zijn, zeker in de combinatie met menutjes (hell op aarde is more like it soms ) maar zeker doeltreffend, en het mooiste is dat je nooit rekening hoeft te houden met de grote van je geneste children.

[Verwijderd]

drm schreef op 02 december 2003 @ 09:18:
[...]
Ik hoop toch dat je wel begrijpt dat het fijner is als het gewoon hier besproken kan worden
[/ot]

De pseudo-PHP die ik gaf, ging m.i. al ver genoeg om vrij simpel om te zetten in werkende code; "haal alle kinderen op" is met een paar regels en 1 simpele query te realiseren.
Gezien de code die in de openingspost getoond werd, leek me dat geen probleem; er was meer behoefte aan het algoritme.

Om complete, werkende code in antwoorden te voorkomen en om de vragensteller te helpen wilde ik wel m'n werkende code opsturen. Het leek me gewoon dat dit niet binnen de doelstellingen van dit forum viel, vandaar.

Uitleg over het algoritme of de pseudocode wil ik best geven, maar "nog gedetailleerder" mondt uit in copy/paste...