Mese: Gennaio 2009

P4A 3 framework: db_navigator helper per estrarre un ramo da un dbtree

di

Esempio di db_navigatorQuesto helper deriva naturalmente dalla funzione descritta nel precedente post.P4A mette a disposizione un widget chiamato P4A_DB_Navigator che si basa su archivi di tipo albero a liste di adiacenza e fornisce un output grafico della lista dei nodi, con un buon grado di interattività. Esiste, per esempio, un metodo che si chiama getPath() che restituisce in un array, il percorso dalla root al nodo fornito in input attraverso la chiave primaria. Purtroppo però, non esiste nessun metodo per estrarre l’insieme di nodi figli da un certo nodo parentale, così ho pensato di adottare la funzione presentata nel precedente post.

I parametri di input sono:

  • $navigator – l’oggetto da cui discende (implicito)
  • $id – l’identificativo del nodo da cui partire
  • $table – il nome della tabella che rappresenta l’albero
  • $pk – il nome della chiave primaria
  • $recursor – il nome del campo che identifica il nodo parentale

Ecco il codice:

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

// File: P4A_db_navigator_getBranch.php
<?php
function P4A_db_navigator_getBranch ($navigator, $params)
{
  list($id, $table, $pk, $recursor) = $params;
  $arr = p4a_db::singleton()->getAll("SELECT * FROM $table");
  $pksArr = array();
  foreach ($arr as $rec) {
    $pksArr[$rec[$pk]]=$rec[$recursor];
  }
  $branchIds = array($id);
  $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;
}
?>

Come esempio ho costruito una semplicissima maschera nella quale, ogni volta che viene selezionato un nodo, viene mostrato un messaggio con l’array dei nodi figli.

Ecco il codice:

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

class dbtree extends P4A_Base_Mask
{
  public function __construct()
  {
    parent::__construct();
    $this->setTitle('Test dbTree');
    //Source
    $this->build("p4a_db_source","dbtree")
      ->setTable("tree")
      ->setPk("id")
      ->load()
      ->firstRow();
    $this->setSource($this->dbtree);
    // db_navigator
    $this->build("p4a_db_navigator","navigator")
      ->setSource($this->dbtree)
      ->setRecursor("parent_id")
      ->setDescription("nome")
      ->setStyleProperty("height","85%")
      ->setStyleProperty("overflow","auto")
      ->collapse(true);
    // Display
    $this->display("sidebar_left",$this->navigator);
    // Intercept action afterMoveRow
    $this->intercept($this->dbtree,"afterMoveRow","showBranch");
  }
	public function showBranch()
  {
    $idCommessa = $this->dbtree->fields->id->getNewValue();
    $arr = $this->navigator->getBranch ($idCommessa, "tree", "id", "parent_id");
    $this->info(print_r($arr,true));
  }
}

L’esempio completo è scaricabile qui

Conclusioni

Lancio l’idea di mettere questa funzione fra i metodi del P4A_db_navigator, sempre che non esca fuori qualche dannato baco :-).

Riferimenti ed approfondimenti:

PHP: estrarre un ramo da un albero a liste di adiacenza senza ricorsione

di

Esempio di struttura ad albero
Esempio di struttura ad albero
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

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

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: