Progetto di Laboratorio di Programmazione
Canale P-Z, A.A. 2004/05

Stefano Guerrini

Sono disponibili i main di prova per il III e IV Modulo

INVIO DELLE SOLUZIONI

I file delle soluzioni dovranno essere inviati usando gli appositi moduli elettronici per l'invio delle soluzioni

• del terzo modulo (termini scaduti).

• del quarto modulo (termini scaduti).

• del quinto modulo.

La scadenza per la consegna del terzo e quarto modulo è prorogata a domenica 19 giugno ore 24.00 .

Specifiche del progetto

• descrizione generale del progetto

• primo modulo

• secondo modulo - Per implementare questo modulo si deve includere la versione aggiornata del file nodes.h e utilizzare la funzione next_word definita nel file parser.c, in cui è implementato il parser degli ipertesti. Per utilizzare il parser si deve includere l'header file parser.h e compilare il programma insieme a parser.c. (Per maggiori informazioni si veda la pagina che descrive il parser).

• terzo e quarto modulo - Per implementare questi moduli si deve usare la versione aggiornata del file nodes.h. I prototipi delle funzioni da implementare, oltre che la definizione dei principali tipi di dato e delle costanti da utilizzare per implementare il modulo sono definiti nell'header file dgp.h.

• quinto modulo - I prototipi delle funzioni da implementare, oltre che la definizione dei principali tipi di dato e delle costanti da utilizzare per implementare il modulo sono definiti nell'header file rank.h. Tutte le funzioni da implementare in questo modulo dovranno essere contenute in un unico file modulo5.c.

Sorgenti forniti dai docenti

Controllare sempre se ci sono aggiornamenti dei file

Header files

• table.h - Interfaccia della tavola composta da una tavola hash e da una lista degli elementi nella tavola hash da implementare nel primo modulo del progetto. [aggiornato il 10/05]
• nodes.h - Principali definizioni dei tipi per l'implementazione del grafo degli ipertesti e dei prototipi delle funzioni che creano la tavola degli ipertesti da analizzare, il dizionario delle parole di ogni pagina e il grafo dei colegamenti tra le pagine. (Aggiornato al terzo e quarto modulo del progetto.) [aggiornato il 23/05]
• dgp.h - Header file con i prototipi delle funzioni da implementare nel terzo e quarto modulo, e con la definizione dei principali tipi di dato e delle costanti da utilizzare nell'implementazione di questi moduli. [aggiornato il 09/06]
• rank.h - Header file con i prototipi delle funzioni da implementare nel quinto modulo, e con la definizione dei principali tipi di dato e delle costanti da utilizzare nell'implementazione di questi moduli. [aggiornato il 14/06]

Il parser

• parser.h - Interfaccia del parser per la lettura degli ipertesti. [aggiornato il 10/05]
• parser.c - Implementazione del parser per la lettura degli ipertesti. [aggiornato il 10/05]

Pagine di input

Sono disponibili una decina di pagine html semplificate sulle quali verificare i moduli del progetto. Le pagine possono essere scaricate sotto forma di archivio tar-gzipped.

Nei prossimi giorni verranno aggiunte altre pagine a quelle già disponibili.

Soluzioni fornite dai docenti

Soluzioni I modulo

La soluzione fornita implementa una tavola hash con gestione interna (lineare) delle collisioni.

• hashtab.h
• hashtab.c
• table.c
• modulo1.c

Chi non ha sviluppato il primo modulo, o lo ha sviluppato in modo incompleto o errato, può utilizzare la soluzione fornita dal docente per verificare e completare il secondo modulo.

NOTE

I modulo

• Un esempio di funzione hash

• (21/04/05) Per quanto riguarda la dimensione della tavola hash. Questa può essere fissata con una costante (ad esempio, 10000). Se si vuole poter avere tavole hash di dimensione diverse, si può assumere che la dimensione di una nuova tavola sia memorizzata in una variabile globale, cambiando il valore di questa variabile le successive tavole cambiano di dimensione. Si osservi che ciò richiede che per ogni istanza di tavola sia memorizzata in qualche forma la sua dimensione, ciò si può ottenere con una opportuna definizione di HASHTABLE.

• (22/04/05) A proposito del main di prova. Un semplice modo per provare il modulo è quello di scrivere un main che, dopo aver creato la tavola prendendo i file da una directory (ad esempio, prefissata o il cui nome è letto da input o ottenuto sulla linea di comando), scandisce gli elementi nella tavola (usando la lista) e per ogni elemento prova a cercarlo nella tavola (così si prova la ricerca nella tavola hash) e poi ne stampa la chiave. Se tutto va bene, si dovrebbe ottenere la lista dei file contenuti nella directory data. Un file main che esegue il precedente test e che sarà usato per verificare i seguenti programmi è scaricabile: scarica il file main1.c.

II modulo

• (04/05/05) Il parser. Il parsing dei file ipertesto è implementato dalla funzione next_word. La descrizione del modo in cui utilizzare questa funzione e dei valori ritornati da tale funzione è riporato alla pagina che descrive il parser fornito dai docenti per leggere le parole contenute negli ipertesti.

• (12/05/05) Directory con i file da ricercare. Nella tavola progettata nel primo modulo non è stata prevista la memorizzazione del path della directory contenente i file, nonostante sia stata prevista la possibilità di leggere i file da una qualsiasi directory passata come argomento sulla linea di comando. Inoltre, dato che la funzione crea_diz_ipertesti da implementare nel secondo modulo non riceve come parametro la directory dei file, nel secondo modulo non è possibile accedere agli ipertesti (a meno che non si trovino nella directory in cui è eseguito il programma). Per ovviare a questo inconveniente, è stata aggiunta al file nodes.h la dichiarazione esterna di una variabile char *main_path. Questa variabile serve per memorizzare il path della directory degli ipertesti; quindi, tutte le funzioni progettate nel secondo modulo potranno usare tale variabile globale per determinare il path completo dei file da leggere. La variabile main_path sarà definita nel file del main e il main, prima dell'esecuzione di crea_diz_ipertesti, dovrà associargli il valore opportuno.

• (12/05/05) Verifica del II modulo. È disponibile una versione preliminare del main che sarà usato per verificare le soluzioni del secondo modulo (scarica il file main2.c). Questo main,
  • per prima cosa richiama la funzione create_node_table fornita nel primo modulo (la directory in cui vengono ricercati gli ipertesti è quella in cui è eseguito il programma oppure una dircetory passata come argomento sulla linea di programma);
  • quindi richiama la create_diz_locale sviluppata nel secondo modulo (a proposito del problema della conoscenza del path della directory degli ipertesti all'interno di questa funzione, si veda una nota precedente);
  • infine, stampa le informazioni memorizzate negli elementi della tavola dei nodi.

III modulo

• (03/06/05) PageRank. Nella specifica del modulo ignorare la frase del paragrafo 1.1 che dice: "Non è difficile provare che la somma dei PageRank di tutti gli ipertesti è uguale al numero degli ipertesti.". Questa proprietà si riferisce ad una formula per il calcolo del PageRank diversa da quella proposta nelle specifiche del modulo.

• (09/06/05) Il prototipo della funzione page_rank è stato corretto, aggiungendo il parametro che indica il numero massimo di iterazioni da eseguire per il calcolo del PageRank (come dalle specifiche del modulo). Vedere la versione aggiornata di dgp.h.

• (14/06/05) [NEW!] Verifica del III modulo. È disponibile una versione preliminare del main che sarà usato per verificare le soluzioni del terzo modulo (scarica il file main3.c). Questo main, dopo aver creato il grafo degli ipertesti usando le funzioni del primo e secondo modulo, calcola e stampa il PageRank di tutte le pagine.

IV modulo

• (03/06/05) struct info_parola. Nella definizioe di questa struttura occorre aggiungere un campo in cui memorizzare il nome dell'ipertesto contenente la parola (il campo struct info_ipertesto *it contiene solo le informazioni relative ai link entranti e uscenti dall'ipertesto, al dizionario locale e al PageRank. Alla struttura si deve pertanto aggiungere il campo char *it_name; che punta alla stringa del nome dell'ipertesto (vedi la versione aggiornata del file dgp.h).

• MODIFICA ANULLATA *(09/06/05) * Nella dichiarazione della funzione dgp_ins si è aggiunto un terzo parametro di tipo struct tabelem * per accedere sia al nome dell'ipertesto che contiene la parola da inserire nel dgp, sia al puntatore alla struct info_ipertesto da salvare nel dgp;

• *(09/06/05) Nel file dgp.h è stata rimossa la linea #include "hashtab.h". Vedere la versione aggiornata di dgp.h.

• *(09/06/05) La modifica al prototipo della dgp_ins è annullata. Quindi, il prototipo rimane
  struct tabelem *dgp_ins(struct dgp *DGP, char *key);
  Il modo di operare per inserire gli elementi nel dgp è il seguente:
  • si scandisce il dizionario locale di tutte le pagine e per ogni parola si crea una struct info_parola contenente i dati dell'ipertesto di cui si sta scandendo il dizionario locale; quindi,
    1. si verifica se la parola è già presente nel dgp e, se la parola non è presente, la si aggiunge al dgp richiamando la dgp_ins, la quale assocerè al nuovo elemento inserito nella tavola una lista di ipertesti in cui occorre la parola vuota;
    2. si aggiunge la struct info_parola alla lista degli ipertesti in cui occorre la parola.

• (14/06/05) [NEW!] Verifica del IV modulo. È disponibile una versione preliminare del main che sarà usato per verificare le soluzioni del quarto modulo (scarica il file main4.c).
  NB. Questo main è ancora preliminare e potrebbe contenere errori. Si prega di segnalare al docente eventuali problemi incontrati nel suo utilizzo.
  Il main di prova, dopo aver creato il grafo degli ipertesti usando le funzioni del primo e secondo modulo
  • crea il dizionario globale usando la funzione crea_dgp implemenatata nel IV modulo
  • scandisce tutti i dizionari locali degli ipertesti, e per ogni parola trovata in un dizionario locale
    1. ricerca la parola nel dgp
    2. stampa la parola e l'ipertesto del dizionario locale che si sta scandendo
    3. preleva dal dgp e stampa la lista degli ipertesti in cui la parola occorre

V modulo

• *(11/06/05) struct LiIp. Come nel caso della struct info_parola, nella definizione di questa struttura occorre aggiungere un campo in cui memorizzare il nome dell'ipertesto. Alla struttura si deve pertanto aggiungere il campo char *it_name; che punta alla stringa del nome dell'ipertesto (vedi la versione aggiornata del file rank.h).

• *(11/06/05) Nella dichiarazione della funzione buid_LiIp si è aggiunto un parametro di struct dgp * che fa riferimento al dizionario globale delle parole.

• (14/06/05) [NEW!] Come già fatto nel modulo 3 per il calcolo del PageRank, in struct LiIp conviene aggiungere un campo double rank_aux di ausilio per il calcolo del valore non normalizzato del rank di una pagina (un campo è sufficiente perchè il rank della pagina relativo a una ricerca ricerca non richiede l'applicazione di un procedimento iterativo). Il file rank.h è stato aggiornato con la nuova definizione di struct LiIp.