Newsgroup: it.comp.lang.perl
Titolo: [OT] ricorsività

Salve,
     sto cercando di scrivere una routine ricorsiva in perl che scopra 
tutti gli "amici" di un "amico" e così via...gli amici vengono 
identificati in modo univoco da un numero id e vorrei sapendo il numero 
id d un amico espandermi il pi possibile nella "ragnatela"...un esempio 
della struttura:
io (000001) = [ (000002), (000004), (000019), (000222) ...etc... ];
il mio amico (000002) a sua volta ha altri amici [ (000004), (009521), 
(000023) ...etc... ]; e così all'infinito...
come vedete (000001) e (000002) hanno un amico in comune (000004)
Mi interesserebbe sapere che approccio logico usereste per riunire in 
un'unica lista tutti gli amici di tutti e così via...naturalmente 
immagino che in perl possa essere ancor pi facile arrivare alla 
soluzione...
Grazie

uhm...cerco di spiegarvi meglio lo scenario...avete presente myspace?? 
ogni "amico" ha degli "amici" e ognuno di quegli "amici" ha altri 
"amici" e cosě via...io in pratica dovrei creare uno robot che partendo 
dal mio friend ID prenda tutti i miei friends ID e cosě via e li 
aggiunga in una lista. Viene usata una sola subroutine chiamata 
_return_ids_from_id(id) che si spiega da sola...ora io so come partire 
ma non come continuare dato che questo robot deve espanders all'infinito 
o quasi mi era all'inizio venuta in mente l'idea di forkare ogni volta 
che si saliva di livello ma questa diventerebbe una pazzia.
Ecco come inizierei:
codice:
my @ids = _return_ids_from_id(000001) # questo č il mio id e in @ids 
vanno tutti i miei "amici"
ora dovrei scandire tutti gli @ids e per ognuno ritornare tutta la lista 
di amici e cosě via...
foreach my $id ( @ids )
{
      my @ids = _return_ids_from_id($id);
      foreach my $id ( @ids )
      {
           my @ids = _return_ids_from_id($id)
           ...etc... e cosě via all'infinito
       }
}
spero di essere stato pi chiaro...Grazie!

 aggiunga in una lista. 
Se non faccio un errore di sbaglio, quello che cerchi è un "tree 
traversal" (
http://en.wikipedia.org/wiki/Tree_traversal
).
Può essere effettuato sia in ricorsivo che in iterativo.
Su cpan trovi un po' di moduli che fanno del lavoro per te (per esempio: 
http://en.wikipedia.org/wiki/Tree_traversal
)

 
http://en.wikipedia.org/wiki/Tree_traversal
)
lo sbaglio c'è stato, intendevo: 
http://search.cpan.org/search?query=tree&mode=module

soluzione...
Non credo che in perl sia particolarmente più facile che in altri
linguaggi: può essere un po' più semplice costruire la struttura dati che
rappresenta il problema (e solo perché c'è un po' meno "burocrazia"), ma
nulla di più.
Quello che può veramente aiutare, invece, è la considerazione che la
relazione "amico di", come definita dal problema, definisce delle "classi
di relazione" sull'universo considerato.
Come ricordiamo dall'algebra, "due classi di relazione o coincidono o non
hanno nessun punto in comune". Non è quindi necessario percorrere
esaustivamente tutto l'albero degli amici degli amici: ogni volta che si
scopre che due amici hanno un elemento comune, si possono riunire tutti gli
insiemi di amici a cui appartengono.
Ciao.

 
http://search.cpan.org/search?query=tree&mode=module
ho letto gli articoli sul tree traversal e solo che non riesco ad 
immaginare come far fare ad uno script la completa attraversata (o 
camminata) dei vari tree (loro giustamente parlavano di fare prima i 
left child e poi i right child) questo è un semplice script ricorsivo...
#!/perl
#
# start
#
&_getFriends(000001); # my id
sub _getFriends {
 
   my $id = shift;
 
   my @amici = _return_ids_from_id($id);
   &_saveid(@amici); ## or &_saveid($id)
 
   foreach(@amici){
 
       &_getFriends($_);
 
   }
 
}
credo che così possa funzionare...ma secondo te impegnerà tanto la CPU e 
come faccio a calcolare in anticipo quanto tempo ci potrà mettere? 
dovrei scaricare tutti gli array su file di testo?? e quindi far 
lavorare pi su disco che su ram?
Grazie

questo è lo script in questione...tuttavia non so dove mettere il codice 
che stampi su file tutti i numeri ids in generale...vi ricordo che il 
primo scopo di questo script e di mettere da parte più numeri id 
possibili partento dal mio (trovare più amici possibili su myspace 
partendo da me, poi dagli amici dei miei amici e così via)
#!/usr/bin/perl
use strict;
use warnings;
use lib "libwww-perl-5.812/lib";
use LWP::UserAgent;
&_getfriends(60964437); # my id;
sub _getfriends {
   my $friend_id = shift;
   my @friends = &_return_ids_from_id($friend_id);
   foreach (@friends)
   {
      &_getfriends($_);
   }
}
sub _return_ids_from_id {
   my $friend_id = shift;
   my $page      = 0;
   my $last_friend;
   my @main;
 
   while (1)
   {
      $page++;
      my $ua   = LWP::UserAgent->new;
            $ua->agent('Mozilla/5.0 (compatible; MSIE 7.0b; Windows NT 
6.0)');
      my $url  = 
'
http://friends.myspace.com:80/index.cfm?fuseaction=user.viewfriends2&fri
endID=' . $friend_id . '&p=' . $page;
      my $res  = $ua->get($url);
      my $html;
      if ($res->is_success) { $html = $res->content } else { die 
$res->status_line }
 
      my @friends;
 
      if (  $html !~ m/<div friendid="(\d+)">/) { return }
      while ( $html =~ /<div friendid="(\d+)">/g ) { push @friends, $1 }
 
      if ( $last_friend && $last_friend == $friends[$#friends] )
      {
         last
      } else {
         $last_friend = $friends[$#friends];
         push @main, @friends
      }
   }
   return @main;
}
__END__;
rcredo che mi toccherà far partire questo script dal mio web server che 
ha una CPU maggiore ed una connesione ad internet più veloce...

di relazione" sull'universo considerato.
"Classi di equivalenza", naturalmente. 30 anni, anche nei più forti,
qualche segno lo lasciano.
Ciao.

soluzione...
Non credo che in perl sia particolarmente più facile che in altri
linguaggi: può essere un po' più semplice costruire la struttura dati che
rappresenta il problema (e solo perché c'è un po' meno "burocrazia"), ma
nulla di più.
Quello che può veramente aiutare, invece, è la considerazione che la
relazione "amico di", come definita dal problema, definisce delle "classi
di relazione" sull'universo considerato.
Come ricordiamo dall'algebra, "due classi di relazione o coincidono o non
