Hello there,
I'm writing a dictionary that stores keywords and the pages which contain the keyword. This is a follow-up on a PageRank algorithm we're doing for an assignment. The first part is the read from a file containing all the web addresses and store the in a matrix, and then read the addresses themselves to add even more names in the matrix. Now this part works fine but I'm having trouble with the current assignment. In my dictionary I have and index that stores all the keywords and their pages, A keyword + page is an Entry class in my case. So in the dictionnary I have Entry **Index. I'm not sure if this is the right way to do it or should I have something like Entry *Index[100],
//YANCHEV Konstantin
//Projet 4
//Groupe 3
#include<iostream>
#include<fstream>
#include<cstring>
#include<math.h>
#include<iomanip>
#include <string>
#include"ListeSL.hpp"
using namespace std;
const int MAX_NB_LINK = 500;
const int MAX_SIZE_URL = 300;
const double eps = 10e-5;
const double c = 0.15;
int nmbr_liens = 0;
class Dictionnaire{
class Entry{
public:
string motClef;
Liste pages;
};
public:
Dictionnaire();
Dictionnaire(const Dictionnaire& orig);
Dictionnaire& operator=(const Dictionnaire& orig);
void inserer(char*);
void inserer(int m, int key);
int chercher(char*);
bool estPresent(char*);
bool contientMot(string str, char ligne[MAX_SIZE_URL]);
void generateDictionnary(char L[MAX_NB_LINK][MAX_SIZE_URL], char *words, char *urls);
void afficherIndex() const;
~Dictionnaire();
Liste returnPages(char *v);
private:
int indiceCourant;
Entry **Index;
void effacer();
void copier(const Dictionnaire& orig);
};
Dictionnaire::Dictionnaire(){
Index = NULL;
indiceCourant = 0;
}
Dictionnaire::Dictionnaire(const Dictionnaire& orig){
copier(orig);
}
Dictionnaire& Dictionnaire::operator=(const Dictionnaire& orig){
if(&orig != this){
for(int i = 0; i < indiceCourant; i++){
Index[i]->pages = orig.Index[i]->pages;
Index[i]->motClef = orig.Index[i]->motClef;
}
}
return *this;
}
void Dictionnaire::inserer(char* name){
Index[indiceCourant] = new Entry;
Index[indiceCourant]->motClef = name;
indiceCourant++;
}
void Dictionnaire::afficherIndex() const{
for(int i = 0; i < indiceCourant; i++){
cout<<"Mot: "<<Index[i]->motClef<<endl;
cout<<"Pages: ";
Index[i]->pages.afficherListe();
}
}
void Dictionnaire::inserer(int m, int key){
Index[m]->pages.insererEnTete(key);
}
int Dictionnaire::chercher(char* name){
int ligne;
bool found = false;
string str1 = name;
for(ligne = 0; ligne<indiceCourant and !found; ligne++){
if(str1.compare(Index[ligne]->motClef) == 0)
found = true;
}
if(!found){
cerr<<"Le mots n'est pas dans l'index"<<endl;
exit(1);
}
return ligne-1;
}
bool Dictionnaire::estPresent(char* name){
string str1 = name;
bool present = false;
for(int i = 0; i < indiceCourant and !present; i++){
if(str1.compare(Index[i]->motClef) == 0)
present = true;
}
return present;
}
bool Dictionnaire::contientMot(string str, char ligne[MAX_SIZE_URL]){
bool contient = false;
//conversion du string en char
char mot[50];
int i, longueur = 0;
for(i = 0; str[i] !='\0';i++){
mot[i] = str[i];
}
mot[i] = '\0';
//recherche sur la ligne;
for(int j = 0; ligne[j] != '\0' and !contient; j++){
for(int k = 0; k < i;k++){
if(mot[k] == ligne[j+k])
longueur++;
}
if(longueur == i)
contient = true;
longueur = 0;
}
return contient;
}
void Dictionnaire::generateDictionnary(char L[MAX_NB_LINK][MAX_SIZE_URL], char *words, char *urls){
char URL[MAX_SIZE_URL];
//1)Rempli Index[] avec les mots
ifstream file;
file.open(words);
while(!file.eof()){
file.getline(URL, MAX_SIZE_URL);
if(!estPresent(URL))
inserer(URL);
}
//Cherche Pour le mots dans Index[i] tout les pages webs qui contient ce MC
for(int mot = 0; mot < indiceCourant; mot++){
//Ouvre le fichier qui se situe a la Ieme ligne de L pour le mot X
for(int ligne = 0; ligne < nmbr_liens; ligne++){
ifstream file2;
file2.open(L[ligne]);
bool contient = false;
//Ouvre la Jeme ligne de la page I
for(int line_file = 0; !file.eof() and !contient; line_file++){
file2.getline(URL, MAX_SIZE_URL);
if(contientMot(Index[mot]->motClef, URL)){
inserer(mot, ligne);
contient = true;
}
}
}
}
}
Dictionnaire::~Dictionnaire(){
for(int i = 0; i < indiceCourant; i++){
delete Index[i];
}
delete [] Index;
}
Liste Dictionnaire::returnPages(char *v){
int index;
index = chercher(v);
return Index[index]->pages;
}
void Dictionnaire::effacer(){
for(int i = 0; i < indiceCourant; i++)
delete Index[i];
delete [] Index;
}
void Dictionnaire::copier(const Dictionnaire& orig){
}
void calculMu1(double A[MAX_NB_LINK][MAX_NB_LINK], double Mu[MAX_NB_LINK], double eps, int n);
void calculMuGoogle(double A[MAX_NB_LINK][MAX_NB_LINK], double Mu[MAX_NB_LINK], double c, double eps, int n);
int totalLiens(int i,double M[MAX_NB_LINK][MAX_NB_LINK]){
int Liens = 0;
for(int indx = 0; indx < nmbr_liens; indx++){
Liens += M[i][indx];
}
return Liens;
}
void MversA(double M[MAX_NB_LINK][MAX_NB_LINK], int n){
double Mu[n], save;
int LiensParLigne[n];
for(int indx = 0; indx < n; indx++){
LiensParLigne[indx] = totalLiens(indx,M) ;
}
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
if(M[i][j] >=1){
save = M[i][j];
M[i][j] = M[j][i]/LiensParLigne[j];
M[j][i] = save/LiensParLigne[i];
}
else if(M[j][i] >=1){
save = M[j][i];
M[j][i] = 0;
M[i][j] = save/LiensParLigne[j];
}
else{
M[i][j] = 0;
M[j][i] = 0;
}
}
}
cout<<"???METHODE GOOGLE???"<<endl;
calculMuGoogle(M, Mu, c, eps, n);
for(int page = 0; page < n; page++){
cout<<"Page "<<page<<": "<<Mu[page]<<endl;
}
cout<<"???METHODE ULB???"<<endl;
calculMu1(M, Mu, eps, n);
for(int page = 0; page < n; page++){
cout<<"Page "<<page<<": "<<setprecision(3)<<Mu[page]<<endl;
}
/*Affichage de la matrice A */
/*for(int ligne =0;ligne < nmbr_liens; ligne++){
cout<<"Lien"<<ligne<<":";
for(int colonne = 0; colonne < nmbr_liens; colonne++){
cout<<M[ligne][colonne];
}
cout<<endl;
}*/
}
void calculMu1(double A[MAX_NB_LINK][MAX_NB_LINK], double Mu[MAX_NB_LINK], double eps, int n){
int iterrations = 0;
double vectTemp[n];
for(int i=0; i < n; i++){
vectTemp[i] = 1.0/n;
}
bool test;
do{
if(iterrations>0){
for(int k = 0; k < n; k++){
vectTemp[k] = Mu[k];
}
}
for(int ligneA = 0; ligneA < n;ligneA ++){
double Somme = 0.0;
for(int colA = 0; colA < n; colA++){
Somme += (A[ligneA][colA] * vectTemp[colA]);
}
Mu[ligneA] = Somme;
}
iterrations++;
test = true;
for(int j = 0; j < n; j++){
if(fabs(Mu[j]-vectTemp[j]) >= eps)
test = false;
}
}while(!test);
cout<<"Iterrations Mu1: "<<iterrations<<endl;
}
void calculMuGoogle(double A[MAX_NB_LINK][MAX_NB_LINK], double Mu[MAX_NB_LINK], double c, double eps, int n){
bool test;
int iterrations = 0;
double E[n], vectTemp[n];
/*initialisation e*/
for(int i=0; i < n; i++){
E[i] = 1.0/n;
}
for(int i=0; i < n; i++){
vectTemp[i] = 1.0/n;
}
for(int i=0; i < n; i++){
Mu[i] = 0;
}
do{
if(iterrations>0){
for(int k = 0; k < n; k++){
vectTemp[k] = Mu[k];
}
}
for(int ligneA = 0; ligneA < n;ligneA ++){
double Somme = 0.0;
for(int colA = 0; colA < n; colA++){
Somme += (A[ligneA][colA] * vectTemp[colA]);
}
Mu[ligneA] = E[ligneA]*c+(1-c)*Somme;
}
iterrations++;
test = true;
for(int j = 0; j < n; j++){
if(fabs(Mu[j]-vectTemp[j]) >= eps)
test = false;
}
}
while(!test);
cout<<"Iterrations MuGoogle: "<<iterrations<<endl;
}
void cptLiens(char L[MAX_NB_LINK][MAX_SIZE_URL], double M[MAX_NB_LINK][MAX_NB_LINK]){
char line[MAX_SIZE_URL];
char lien_tmp[MAX_SIZE_URL];
int resultat, lien_traitee;
ifstream file;
file.open("listepages.txt");
//Rempli la matrice L
for(; nmbr_liens < MAX_NB_LINK and !file.eof(); nmbr_liens++){
resultat = 1;
file.getline(line,MAX_SIZE_URL);
if(nmbr_liens==0){
int long_lien;
for(long_lien=0;long_lien<MAX_SIZE_URL and line[long_lien] !='\0';
long_lien++){
L[nmbr_liens][long_lien] = line[long_lien];
}
L[nmbr_liens][long_lien] = '\0';
}
for(int k = 0; k<nmbr_liens and resultat !=0;k++){
resultat = strcmp(L[k], line);
if(resultat == 0){
nmbr_liens--;
}
else if(k+1 == nmbr_liens){
int long_lien;
for(long_lien=0;long_lien<MAX_SIZE_URL
and line[long_lien] !='\0'; long_lien++){
L[nmbr_liens][long_lien] = line[long_lien];
}
L[nmbr_liens][long_lien]='\0';
}
}
}
/* A la sortie du cycle le dernier index de L reste vide. Il faut
* donc enlever l'indice non-rempli*/
nmbr_liens--;
/* Le cycle suivant ce deroule ainsi:
1)Lis L ligne par ligne.
2)Cherche <a href..> dans la ligne actuelle.
3)Lis le lien trouvee.
4)Compare le lien trouvee aux autres
5)Si le lien est deja dans L on recuper son indice sinon on le
rajoute a la fin de L.
6)M[lien_actu][lien_traitee] ++.
*/
for(int g=0;g < MAX_NB_LINK; g++){
for(int t=0; t <MAX_NB_LINK; t++){
M[g][t] = 0.0;
}
}
//ouvre un site qui se trouve sur L[i];
for(int lien_actu = 0; lien_actu < nmbr_liens; lien_actu++){
ifstream file2;
file2.open(L[lien_actu]);
//ouvre la I-eme ligne du site sur L[i];
for(int lignes_fich = 0; lignes_fich < MAX_NB_LINK and !file2.eof();
lignes_fich++){
file2.getline(line,MAX_SIZE_URL);
//parcours la ligne a la recherche de <a href>
for(int char_line = 0;line[char_line] != '\0'; char_line++){
if(line[char_line] == '<'
and (line[char_line+1] =='a' or line[char_line+1]=='A')
and line[char_line+2] == ' '
and (line[char_line+3] == 'h' or line[char_line+3]=='H')
and (line[char_line+4] == 'r' or line[char_line+4]=='R')){
//recopie le lien trouvee dans un vectuer temporaire
int p=0;
for(int debut_line = char_line + 9; line[debut_line] != '#'
and line[debut_line] !='"';debut_line ++, p++){
lien_tmp[p] = line[debut_line];
}
lien_tmp[p] = '\0';
resultat = 1;
//compare le lien trouvee aux liens dans L
int k;
for(k = 0; k < nmbr_liens and resultat !=0; k++){
resultat = strcmp(lien_tmp,L[k]);
if(resultat == 0){
lien_traitee = k;
}
}
//si c'est un lien nouveau on le met dans L
if(k == nmbr_liens){
int long_lien;
for(long_lien = 0;long_lien < MAX_SIZE_URL
and line[long_lien] != '\0';long_lien++){
L[nmbr_liens][long_lien]= lien_tmp[long_lien];
}
L[nmbr_liens][long_lien]='\0';
lien_traitee = nmbr_liens;
nmbr_liens++;
}
M[lien_actu][lien_traitee]++;
}
}
}
}
}
void affiche(char L[MAX_NB_LINK][MAX_SIZE_URL], double M[MAX_NB_LINK][MAX_NB_LINK]){
/*Affichage de la matrice L */
for(int ligne = 0; ligne<nmbr_liens; ligne++){
cout<<ligne+1<<":"<<L[ligne]<<endl;
}
/*Affichage de la matrice M */
for(int ligne =0;ligne < nmbr_liens; ligne++){
cout<<"Lien"<<ligne+1<<":";
for(int colonne = 0; colonne < nmbr_liens; colonne++){
cout<<M[ligne][colonne];
}
cout<<endl;
}
}
int main(){
Dictionnaire Dico;
char words[] = {"motscle.txt"};
char urls[] = {"listepages.txt"};
char L[MAX_NB_LINK][MAX_SIZE_URL];
double M[MAX_NB_LINK][MAX_NB_LINK];
cptLiens(L, M);
affiche(L, M);
Dico.generateDictionnary(L, words, urls);
//Dico.afficherIndex();
MversA(M, (nmbr_liens));
}
This is the whole thing. If I use Entry **Index by the time I get to generateDictionnary() I get a Segmentation Fault. If I use Entry *Index[100] I get nothing after affiche(); or I get free() invalid pointer followed by abort. I tried to check it with gdb but since I just picked it up it didn't help me very much, I used valgrind but it showed no memory leaks. I really have no idea what to do. I suspect the problem is with the Entry **Index and maybe the initializing of a Dictionnaire object. Btw the important code is upto line 188, below that it's tested and working.