Supponiamo di avere un archivio con una struttura ad albero di tipo a liste di adiacenza. Ogni record sarà
necessariamente caratterizzato da un identificativo univoco e da un attributo che serve a riconoscere il proprio genitore.
Per esempio, nella figura accanto, l'elemento 4 avrà id = 4, e parentId = 1,
l'elemento 9 avrà id = 9, e parentId = 4, e così via. Questo modello offre alcuni
vantaggi, che sono principalmente la semplicità della struttura e la velocità negli inserimenti. D'altro canto,
risultano piuttosto onerosi processi come l'estrazione o la cancellazione di interi rami. Le query risultano quindi,
complesse e spesso ricorsive.
Sebbene l'utilizzo di una struttura di tipo nested tree model ideata da Joe Celko sia quasi sempre preferibile, alle volte è necessario cimentarsi con gli algoritmi per la manipolazione delle liste di adiacenza.
Se si deve salire da una foglia fino alla root, non è troppo difficile, basta risalire, attraverso
il parentId, il genitore finché parentId = NULL. Il procedimento è naturalmente ricorsivo,
per questo motivo spesso si indica l'attributo parentId anche con il nome di ricorsore.
Il gioco si fa duro quando si deve estrarre un ramo a partire da un certo genitore... ma come disse John Belushi:
"When the going gets tough, the toughs get going!". Vediamo come fare evitando di farci del male con stored procedure,
query ricorsive o tabelle temporanee.
La soluzione che ho adottato prende spunto dagli algoritmi di attraversamento dei grafi: Breadth-first search
e Depth-first search. Questi sono procedimenti non ricorsivi che utilizzano stack di tipo FIFO
e LIFO per l'esplorazione dei nodi.
L'operazione di fetching da un archivio che rappresenta l'albero della figura in alto produrrà un'array di questo tipo:
$arrTest = array (
0 => array ("id"=>1, "parent_id"=>NULL),
1 => array ("id"=>2, "parent_id"=>1),
2 => array ("id"=>3, "parent_id"=>1),
3 => array ("id"=>4, "parent_id"=>1),
4 => array ("id"=>5, "parent_id"=>2),
5 => array ("id"=>6, "parent_id"=>2),
6 => array ("id"=>7, "parent_id"=>3),
7 => array ("id"=>8, "parent_id"=>3),
8 => array ("id"=>9, "parent_id"=>4),
9 => array ("id"=>10, "parent_id"=>4),
10 => array ("id"=>11, "parent_id"=>4),
11 => array ("id"=>12, "parent_id"=>5),
12 => array ("id"=>13, "parent_id"=>5),
13 => array ("id"=>14, "parent_id"=>6),
14 => array ("id"=>15, "parent_id"=>7),
15 => array ("id"=>16, "parent_id"=>7),
16 => array ("id"=>17, "parent_id"=>9),
17 => array ("id"=>18, "parent_id"=>9),
18 => array ("id"=>19, "parent_id"=>10),
19 => array ("id"=>20, "parent_id"=>11),
20 => array ("id"=>21, "parent_id"=>11)
);
Ammettiamo ora di voler estrarre l'intero ramo che ha come radice l'elemento 4.
La funzione seguente utilizza un nuovo array che viene costruito utilizzando come chiave gli id
e come valori i parent_id. Questo ci permette di utilizzare la
funzione PHP: array_keys() per le ricerche dei figli, che è piuttosto efficiente.
Ecco il codice:
function getBranch ($arr,$pk,$recursor,$idBranch)
{
$pksArr = array();
foreach ($arr as $rec) {
$pksArr[$rec[$pk]]=$rec[$recursor];
}
$branchIds = array($idBranch);
$i=0;
while ($i<count($branchIds)) {
$newKeys = array_keys($pksArr,$branchIds[$i]);
if (!empty($newKeys)) {
foreach ($newKeys as $newKey){
array_push($branchIds, $newKey);
}
}
++$i;
}
$res = array();
foreach ($arr as $child) {
if (in_array($child[$pk], $branchIds)) {
$res[] = $child;
}
}
return $res;
}
Certo, il codice di questa funzione non è troppo ottimizzato: utilizza tre array
(anche se $pksArr e $branchIds sono monodimensionali e quindi "leggeri")
ed esegue tre cicli. In particolare il ciclo (righe 19-23) è piuttosto lento, ma è necessario
se si vuole recuperare tutti gli attributi degli elementi estratti oltre agli indispensabili
id già presenti in $branchIds. Dalle prove che ho fatto, per archivi fino a 10-15000 records risulta comunque abbastanza efficiente.
Questo è il risultato dell'estrazione del ramo con radice 4 (si nota che l'andamento è di tipo "breadth-first-search" ricerca in ampiezza, seguendo i colori: rosso-verde-blu-giallo):
Array
(
[0] => Array
(
[id] => 4
[parent_id] => 1
)
[1] => Array
(
[id] => 9
[parent_id] => 4
)
[2] => Array
(
[id] => 10
[parent_id] => 4
)
[3] => Array
(
[id] => 11
[parent_id] => 4
)
[4] => Array
(
[id] => 17
[parent_id] => 9
)
[5] => Array
(
[id] => 18
[parent_id] => 9
)
[6] => Array
(
[id] => 19
[parent_id] => 10
)
[7] => Array
(
[id] => 20
[parent_id] => 11
)
[8] => Array
(
[id] => 21
[parent_id] => 11
)
)
// Tempo di esecuzione: 0.2388 msecs
Conclusioni
Personalmente, ho una certa ritrosia nell'uso di funzioni ricorsive, per questo ho perso del tempo a cercare soluzioni alternative e cicliche, ciò non toglie che, ad esempio per recuperare il percorso di una foglia (risalendo quindi verso la root), la ricorsione sia la soluzione più adatta.
Riferimenti ed approfondimenti:
Non ho capito come applicare la funtione getBranch() al caso sopra esposto.
Penso che:
-$arr -> $arrTest
-$pk -> $arrTest[0]
-$recursor -> $arrTest[1]
-$idBranch -> ? nodo di partenza?
-$rec -> ?
-$child -> ?
Simone
La funzione getBranch() restituisce un array, quindi per ottenere tutti i rami a partire dal nodo 4 (per esempio):
$newArr = getBranch($arrTest,"id","parent_id",4);
print_r($newArr);