Newsgroup: it.comp.www.php
Titolo: Un algoritmo per estrapolare gli annidamenti?

Volevo costruire un sistema libero di categorie/sottocategorie/ecc.
basato su una tabella di mysql con questa struttura:
id, nome, parent_id
 
Utilizzando parent_id come relazione verso un id della stessa tabella le
parentele potrebbero essere virtualmente infinite, io vorrei trovare il
modo di recuperare queste parentele per costruire un menù di
navigazione.
Sapete come si chiama questa tecnica?
Mi potete illustrare in breve i concetti di base per realizzarla o
indirizzarmi verso qualche risorsa in rete?
Grazie
 
Max
-- 
http://www.maxori.it
 
L'Arte è la capacità di fare cose di nessun valore
e di riuscire a venderle
F. Zappa

Sapete come si chiama questa tecnica?
 
tree-walking, credo.
 
Leonardo
 
-- 
Tell us whether you spy, in the light of the morn,
what saluted was fiercely at the fall of the past day:
whose pips and whose bands in the very heart of the fray
bravely floated from the bulwarks to which we were sworn?

 rete? Grazie
 
Se vuoi permettere cicli nella struttura o genitori multipli (e quindi 
hai un grafo e non un albero) puoi cercare "algoritmo visita grafi", ma 
ti avviso che ti stai ficcando in un ginepraio. :)
 
Bye.

 Leonardo
 
Grazie, tieni presente che questa cosa la sto studiando giusto perchè ho
qualche giorno libero.
Visto che spesso mi capita di realizzare CMS ad-hoc potrebbe essere
utile avere qualcosa di già pronto ma fatto nel tempo libero.
 
Ciao


 Bye.
 
Qualcosa di simile mi era passato per la mente...
In tutti i casi, come ho detto anche a Leonardo, è giusto una cosa che
mi sarebbe piaciuto studiare adesso che ho qualche giorno libero, nel
caso che in futuro possa tornare utile.


Risolto? A me sembra di si...
 
Serve una prima query:
 
<?php
mysql_select_db($database_DBConn, $DBConn);
$query_level = "SELECT * FROM navigazione WHERE p_id = 0 ORDER BY nome
ASC";
$level = mysql_query($query_level, $DBConn) or die(mysql_error());
$row_level = mysql_fetch_assoc($level);
$totalRows_level = mysql_num_rows($level);
 
un funzione ricorsiva:
 
 
function recupera($id,$db,$dbconn) {
  mysql_select_db($db, $dbconn);
  $query_sub_level = "SELECT * FROM navigazione WHERE p_id = '$id' ORDER
BY nome ASC";
  $sub_level = mysql_query($query_sub_level, $dbconn) or
die(mysql_error());
  $row_sub_level = mysql_fetch_assoc($sub_level);
  $totalRows_sub_level = mysql_num_rows($sub_level);
  $lista = "";
  if($totalRows_sub_level>0) {
   $lista .= "<ol>";
   do {
     $lista .= "<li>" . $row_sub_level['nome'] .
     recupera($row_sub_level['id'],$db,$dbconn) . "</li>";
   } while($row_sub_level = mysql_fetch_assoc($sub_level));
   $lista .= "</ol>";
   }
   return $lista;
}
?>
 
body della pagina:
 
<ol>
   <?php do { ?>
   <li><?php echo $row_level['nome']; ?>
   <?php echo recupera($row_level['id'],$database_DBConn, $DBConn);
?></li>
<?php } while ($row_level = mysql_fetch_assoc($level)); ?>
</ol>
 
 
E' un pò grezza, certo, però mi sembra che funzioni.


 navigazione.
 
Sullo specifico argomento:
- 
http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
 
 
Un buon approccio per iterare sul risultato potrebbero essere gli 
iteratori della libreria SPL... da quando ho avuto il coraggio provare a 
superare l'ostacolo della mancanza di documentazione mi hanno salvato da 
una miriade di casi dove sarei dovuto altrimenti ricorrere a funzioni 
ricorsive (che odio).
Segnalo un ottimo articolo introduttivo che copre molte delle lacune 
nella documentazione ufficiale:
- 
http://www.phpro.org/tutorials/Introduction-to-SPL.html
 
 
Un piccolo esempio di codice trovato negli appunti (non è farina del mio 
sacco) che dato un array multidimensionale di profondità arbitraria lo 
attraversa e genera una lista annidata.
 
<?php
class TranformArrayIterator extends RecursiveIteratorIterator
{
   protected function indent()
   {
     echo str_repeat("\t", $this->getDepth());
     return $this;
   }
   public function beginIteration()
   {
     echo '<ul>', PHP_EOL;
   }
   public function endIteration()
   {
     echo '</ul>', PHP_EOL;
   }
   public function beginChildren()
   {
     $this->indent()->beginIteration();
   }
   public function endChildren()
   {
     $this->indent()->endIteration();
   }
   public function current()
   {
     return sprintf('%s<li>%s</li>%s',
       str_repeat("\t", $this->getDepth() +1),
       parent::current(),
       PHP_EOL
     );
   }
}
 
$nodes = array(
   'Padre',
   'Padre',
   array(
     'Figlio',
     'Figlio',
     array(
       'Nipote',
       'Nipote',
       array(
         'Pronipote',
         'Pronipote'
       )
     )
   )
);
 
$iterator = new TranformArrayIterator(
   new RecursiveArrayIterator($nodes)
   );
 
foreach($iterator as $val) {
   echo $val;
}
 
$a = $val;
 
/* output
 
<ul>
   <li>Padre</li>
   <li>Padre</li>
   <ul>
     <li>Figlio</li>
     <li>Figlio</li>
     <ul>
       <li>Nipote</li>
       <li>Nipote</li>
       <ul>
         <li>Pronipote</li>
         <li>Pronipote</li>
       </ul>
     </ul>
   </ul>
</ul>
*/
?>
 
 
-- 
Design for the future, because it will be here sooner than you think.
(C) Eric S. Raymond, from "The Art of Unix Programming"

$totalRows_level = mysql_num_rows($level);
 
Se devi fare cosi', pero', in pratica ti stai caricando TUTTO il database
in memoria, con piu' query.
 
A quel punto, ti conviene fare una SELECT *, e trattare la tabella che ti
viene ritornata come una "hill" iterativamente. Lievemente piu' complesso
della ricorsione, ma penso piu' efficiente.
 
Tutto dipende comunque da cosa vuoi ottenere alla fine.
 
Un sistema potabile in PHP potrebbe essere di costruire un array partendo
dalla tabella (niente hill),
 
	$exec = SQLExec('SELECT * FROM navigazione;');
	$TREE = array();
	while($tuple = SQLFetchTuple($exec))
	{
		$id = $tuple['id'];
		unset($tuple['id'] // Risparmio di Coccolino
		$TREE[$id] = $tuple;
		if ($id < $tuple['parent_id'])
			die("Puppa!"); // Controllo stupido
	}
	SQLFree($exec);
 
	function full_breadcrumbs($id)
	{
		global $TREE;
		if (!isset($TREE))
			loadTree();
		$result = array();
		while(isset($tree[$id]))
		{
			$node = $tree[$id];
			$id   = $node['parent_id'];
			$result[] = $node;
		}
		return $result;
	}
 
	function breadcrumbs($id)
	{
		$path	= array();
		$nodes	= full_breadcrumbs($id);
		foreach($nodes as $node)
			$path[] = $node['name'];
		// Chi gli piace, puo' fare array_reverse di $path
		return implode(" >> ", $path);
	}
 
Leonardo forse


 Max
 
Se la vuoi fare in MySQL (ma anche in un qualsiasi altro database 
relazionale SQL), allora è buono usare il modello dei Nested Set 
descritto nell'articolo postato da giovanni.v di mike hillery, perché 
con una sola query semplice puoi ottenere, ad esempio, tutti i genitori 
di un id in un colpo solo.
 
Se invece lo vuoi fare in PHP e basta, è molto più "semplice", basta 
implementare il modello classico di albero radicato, oppure trovare 
qualche libreria che lo fa già.
 
Questo ovviamente se NON hai cicli. Se hai cicli (come credo tu voglia, 
visto che parli di parentele virtualmente infinite), allora devi andare 
sui grafi e lì non credo che puoi utilizzare qualcosa che ti faciliti il 
lavoro come il modello del Nested Set, cioè senza fare una caterva di 
query per avere, ad esempio, tutti i parenti di un nodo.
 
Piuttosto devi spostarti sulla programmazione in PHP.
 
Comunque questi sono argomenti di algoritmi e strutture dati con una 
base di teoria abbastanza interessante e che soprattutto deve essere 
appresa. Ti suggerirei di studiarti un libro, l'onnipresente Cormen 
(Introduzione agli algoritmi e strutture dati) dovrebbe andare 
abbastanza bene.

 Tutto dipende comunque da cosa vuoi ottenere alla fine.
 
Innanzitutto Buon Anno! E grazie per l'interessamento.
Scusa se non ho risposto prima ma ero impegnato a digerire il cibo delle
feste in stile "anaconda", sdraiato sul divano ed emettendo notevoli
rumori intestinali...
 
Ovviamente hai ragione, in termini di "buona" programmazione la
questione da te sollevata � sicuramente corretta, e infatti nei prossimi
momenti liberi mi studier� meglio la cosa seguendo anche le tue
indicazioni.
(S)fortunatamente non ho mai avuto bisogno in passato di un sistema cos�
"free", ma non si sa mai...
 
Ciao
 
Max
-- 
http://www.maxori.it
 
L'Arte � la capacit� di fare cose di nessun valore


 attraversa e genera una lista annidata.
 
Grazie per i links, studier�, studier�...
 
Max
-- 
http://www.maxori.it
 
L'Arte � la capacit� di fare cose di nessun valore


 abbastanza bene.
 
Mmmmh, ok, mi sa di tomo "pesante", ma non sarebbe il primo.
 
Grazie molte per le info.
 
Max
-- 
http://www.maxori.it
 
L'Arte � la capacit� di fare cose di nessun valore
