-
Notifications
You must be signed in to change notification settings - Fork 4
/
pagerank.c
184 lines (157 loc) · 5.44 KB
/
pagerank.c
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include <stdio.h>
#include <math.h>
// CONSTANTS
#define MAX_PAGES 100 // Integer in [MIN_PAGES, +inf)
#define MIN_PAGES 2 // Integer in [2, MAX_PAGES]
#define WEIGHT 0.15 // Real in (0, 1), best at 0.15
#define ERROR 0.0001 // Real in (0, +inf), best at 0.0001
// PROTOTYPES
int get_num_pages();
void init_link_matrix(int num_pages, float link_matrix[][num_pages]);
void scalar_multiplication(float *matrix, int num_rows, int num_cols, float scalar);
void column_multiplication(float *matrix, int num_rows, int num_cols, float *column);
void addition(float *matrix1, float *matrix2, int num_rows, int num_cols);
float norm(float *column, int num_rows);
void print_standings(float score_column[], int num_pages);
int main() {
// INPUT
printf("Let's start by creating a model of the web.\n");
int num_pages = get_num_pages();
float link_matrix[num_pages][num_pages];
init_link_matrix(num_pages, link_matrix);
// CONVERGENCE LOOP
// Initialize mean column and score column
float mean_column[num_pages], score_column[num_pages];
for (int i = 0; i < num_pages; i++) {
float entry = 1 / (float) num_pages;
mean_column[i] = entry;
score_column[i] = entry;
}
// Weigh link matrix and mean column
scalar_multiplication(link_matrix[0], num_pages, num_pages, 1 - WEIGHT);
scalar_multiplication(mean_column, num_pages, 1, WEIGHT);
float score_norm;
do {
// Store score column before operations
float score_diff[num_pages];
for (int i = 0; i < num_pages; i++)
score_diff[i] = score_column[i];
// Multiply score column by weighted link matrix
column_multiplication(link_matrix[0], num_pages, num_pages, score_column);
// Add weighted mean column to score column
addition(score_column, mean_column, num_pages, 1);
// Subtract previous score column from score column
scalar_multiplication(score_diff, num_pages, 1, -1);
addition(score_diff, score_column, num_pages, 1);
// Calculate norm of the difference
score_norm = norm(score_diff, num_pages);
// Repeat until score norm is smaller than error
} while (score_norm > ERROR);
// OUTPUT
printf("Here are the standings:\n");
print_standings(score_column, num_pages);
}
// INPUT
// Get number of pages
int get_num_pages() {
int num_pages;
do {
printf("How many pages does your web have? ");
scanf("%d", &num_pages);
if (num_pages < MIN_PAGES)
printf("Your web has too few pages, try %d or more.\n", MIN_PAGES);
else if (num_pages > MAX_PAGES)
printf("Your web has too many pages, try %d or less.\n", MAX_PAGES);
} while (num_pages < MIN_PAGES || num_pages > MAX_PAGES);
return num_pages;
}
// Initialize link matrix
void init_link_matrix(int num_pages, float link_matrix[][num_pages]) {
// Set all entries to 0
for (int i = 0; i < num_pages; i++)
for (int j = 0; j < num_pages; j++)
link_matrix[i][j] = 0;
// Links
for (int i = 0; i < num_pages; i++) {
// Number of links
int num_links;
do {
printf("How many links does page %d have? ", i + 1);
scanf("%d", &num_links);
if (num_links < 1)
printf("Page %d has too few links, try 1 or more.\n", i + 1);
else if (num_links > num_pages - 1)
printf("Page %d has too many links, try %d or less.\n", i + 1, num_pages - 1);
} while (num_links < 1 || num_links > num_pages - 1);
// Linked pages
for (int j = 0; j < num_links; j++) {
int page_num;
do {
printf("%d. What page does page %d link? ", j + 1, i + 1);
scanf("%d", &page_num);
if (page_num < 1 || page_num > num_pages)
printf("Page %d does not exist, try again.\n", page_num);
else if (page_num == i + 1)
printf("A page can't link itself, try again.\n");
else if (link_matrix[page_num - 1][i])
printf("Page %d already links page %d, try again.\n", i + 1, page_num);
} while (page_num < 1 || page_num > num_pages || page_num == i + 1 || link_matrix[page_num - 1][i]);
// Set entry
link_matrix[page_num - 1][i] = 1 / (float) num_links;
}
}
}
// MATRIX OPERATIONS
// Multiply matrix by scalar
// Product stored in the matrix
void scalar_multiplication(float *matrix, int num_rows, int num_cols, float scalar) {
int num_entries = num_rows * num_cols;
for (int i = 0; i < num_entries; i++)
*matrix++ *= scalar;
}
// Multiply matrix by column
// Product stored in the column
// Column must have num_cols rows
void column_multiplication(float *matrix, int num_rows, int num_cols, float *column) {
float product[num_cols];
for (int i = 0; i < num_rows; i++) {
float sum = 0;
float *temp = column;
for (int j = 0; j < num_cols; j++)
sum += *matrix++ * *temp++;
product[i] = sum;
}
// Copy entries in the column
for (int i = 0; i < num_cols; i++)
*column++ = product[i];
}
// Sum two matrices
// Sum stored in the first matrix
// Matrices must have the same dimensions
void addition(float *matrix1, float *matrix2, int num_rows, int num_cols) {
int num_entries = num_rows * num_cols;
for (int i = 0; i < num_entries; i++)
*matrix1++ += *matrix2++;
}
// Return Euclidean norm of column
float norm(float *column, int num_rows) {
float sum = 0;
for (int i = 0; i < num_rows; i++)
sum += pow(*column++, 2);
return sqrt(sum);
}
// OUTPUT
// Print standings
void print_standings(float score_column[], int num_pages) {
for (int i = 0; i < num_pages; i++) {
float max_score = 0;
int page_num;
for (int j = 0; j < num_pages; j++)
if (score_column[j] > max_score) {
max_score = score_column[j];
page_num = j;
}
score_column[page_num] = 0;
printf("%d. Page %d: %f\n", i + 1, page_num + 1, max_score);
}
}