API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 18th, 2018
77
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.04 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5.  
  6. typedef struct link {
  7. int source;
  8. int dest;
  9.  
  10. }Link;
  11.  
  12. typedef struct resultat{
  13. int ** res;
  14. Link ** adj;
  15.  
  16. }Resultat;
  17.  
  18.  
  19.  
  20.  
  21. double * powerIteration(int *d_out, Link ** adj, double alpha, int n, int m, int nb_ite){
  22.  
  23.  
  24. double * P1 = calloc(n, sizeof(double));
  25. double * P2 = calloc(n, sizeof(double));
  26. double *P3;
  27.  
  28. int i;
  29. int j;
  30. int s=0;
  31. int k=0;
  32. double sum=0;
  33.  
  34. for(i=0; i<n; i++){
  35. P1[i] = 1/n;
  36. }
  37.  
  38. for(i=0; i<nb_ite; i++){
  39.  
  40. for(j=0; j<n; j++){
  41. P2[j] = 0;
  42. }
  43.  
  44.  
  45.  
  46. for(j=0 ; j<m; j++){
  47.  
  48. if(d_out[adj[j]->source]==0) continue;
  49. P2[adj[j]->dest] += P1[adj[j]->source]/(double)d_out[adj[j]->source];
  50.  
  51. }
  52.  
  53.  
  54.  
  55. sum=0;
  56.  
  57. for(j=0; j<n; j++){
  58. P2[j] = (1.0-alpha)*P2[j];
  59. P2[j] += alpha/(double)n;
  60. sum += P2[j];
  61.  
  62. }
  63.  
  64.  
  65.  
  66. for(j=0; j<n; j++){
  67. P2[j] += (1.0-sum)/(double)n;
  68.  
  69. }
  70.  
  71. P3 = P2;
  72. P2 = P1;
  73. P1 = P3;
  74.  
  75.  
  76. }
  77.  
  78. free(P2);
  79.  
  80. return P1;
  81.  
  82.  
  83. }
  84.  
  85. Resultat formatFile2(char *fileLink, char* fileName){
  86.  
  87.  
  88. FILE *f = fopen(fileName, "r");
  89.  
  90. FILE *l = fopen(fileLink, "r");
  91.  
  92.  
  93.  
  94.  
  95. int s=-1, t;
  96. char name[1000];
  97. char num[12];
  98. char reste[1000];
  99. int ** res = calloc(4, sizeof(int*));
  100.  
  101. if(f==NULL) exit(1);
  102. if(l==NULL) exit(1);
  103.  
  104. int i=0;
  105.  
  106. while(i<5){
  107. fgets(name, 1000, f);
  108. fgets(name, 1000, l);
  109. i++;
  110. }
  111. i=0;
  112. int j;
  113. int source, dest;
  114.  
  115. int sum=0;
  116. int p=0;
  117.  
  118. int* d_out = calloc(13834640, sizeof(int));
  119. Link ** adj = calloc(46092178, sizeof(Link*));
  120. int* n = calloc(2, sizeof(int));
  121.  
  122.  
  123. Resultat ret ;
  124.  
  125. ret.res = res;
  126.  
  127. ret.adj = adj;
  128.  
  129. int* correspondance = calloc(13834640, sizeof(int));
  130. int* correspondance2 = calloc(13834640, sizeof(int));
  131.  
  132. int max=0;
  133.  
  134. for(i =0; i<13834640; i++){
  135. correspondance[i] = -1;
  136. }
  137.  
  138. res[0] = d_out;
  139. //res[1] = adj;
  140. res[2] = n;
  141. s = 12;
  142. correspondance[12] = 0;
  143. /*while(fgets(name, 1000, f)!=NULL){
  144. j=0;
  145.  
  146. while(name[j] != '\t'){
  147. num[j] = name[j];
  148. j++;
  149. }
  150.  
  151.  
  152. int k =0;
  153. while(j<1000){
  154. reste[k++] = name[j];
  155. j++;
  156. }
  157.  
  158. reste[k] = '\n';
  159.  
  160. num[j] = '\n';
  161.  
  162. s = atoi(num);*/
  163.  
  164. i=0;
  165.  
  166. correspondance2[0] = 12;
  167.  
  168. Link* lien ;
  169.  
  170. while(fscanf(l, "%d\t%d\n", &source, &dest)!=EOF){
  171.  
  172. lien =(Link*) (malloc(sizeof(struct link)));
  173.  
  174. if(source==s){
  175.  
  176.  
  177.  
  178. d_out[i]++;
  179.  
  180. adj[p++] = lien;
  181. lien->source = s;
  182. lien->dest = dest;
  183.  
  184. }
  185. else{
  186.  
  187. d_out[i+1] ++;
  188. adj[p++] = lien;
  189.  
  190.  
  191.  
  192. s = source;
  193. i++;
  194. lien->source = s;
  195. lien->dest = dest;
  196.  
  197. correspondance[source]=i;
  198. correspondance2[i] = source;
  199. }
  200.  
  201. }
  202.  
  203.  
  204.  
  205. int w;
  206. for(w=0; w<p; w++){
  207.  
  208. if(correspondance[adj[w]->dest]==-1){
  209. //printf("ICI %d\n",adj[w]);
  210. s = adj[w]->source;
  211. adj[w]->dest = i++;
  212. correspondance2[i-1] = s;
  213. correspondance[adj[w]->dest] = i-1;
  214. }
  215. else{
  216. adj[w]->dest = correspondance[adj[w]->dest];
  217. }
  218. }
  219.  
  220.  
  221.  
  222.  
  223. n[0] = i;
  224. n[1] = p;
  225.  
  226. fclose(f);
  227.  
  228. fclose(l);
  229.  
  230. res[3] = correspondance2;
  231.  
  232. free(correspondance);
  233.  
  234. return ret;
  235.  
  236. }
  237.  
  238.  
  239. int * computeInDegrees(Link **adj, int n, int m){
  240.  
  241. int * d_in = calloc(n, sizeof(double));
  242.  
  243. int i;
  244.  
  245. for(i=0; i<m; i++){
  246. d_in[adj[i]->dest]++;
  247. }
  248.  
  249.  
  250. return d_in;
  251.  
  252. }
  253.  
  254. void writeFilePageRankResult(char *file, double *P, int n){
  255.  
  256. FILE *f = fopen(file, "w");
  257.  
  258. int i;
  259.  
  260. for(i=0; i<n; i++){
  261. if(P[i] > 0.0000009){
  262. fprintf(f, "%d %.81f\n", i, P[i]);
  263. }
  264.  
  265.  
  266. }
  267.  
  268. fclose(f);
  269.  
  270.  
  271. }
  272.  
  273.  
  274. void writeFileDegrees(char *file, int *deg, int n, int * correspondance){
  275.  
  276. FILE *f = fopen(file, "w");
  277. int i;
  278.  
  279. for(i=0; i<n; i++){
  280.  
  281. fprintf(f, "%d %d\n", correspondance[i], deg[i]);
  282.  
  283.  
  284.  
  285. }
  286.  
  287.  
  288. fclose(f);
  289. }
  290.  
  291.  
  292. int main(){
  293.  
  294.  
  295. time_t t1=time(NULL);
  296.  
  297. Resultat ret = formatFile2("alr21--dirLinks--enwiki-20071018.txt", "alr21--pageNum2Name--enwiki-20071018.txt");
  298.  
  299. int ** res = ret.res;
  300.  
  301. int * d_out = res[0];
  302. Link ** adj = ret.adj;
  303.  
  304. int n = res[2][0];
  305. int m = res[2][1];
  306.  
  307. int * correspondance=res[3];
  308.  
  309. int i;
  310.  
  311.  
  312.  
  313. double * P = powerIteration(d_out, adj, 0.15, n, m, 20);
  314.  
  315. time_t t2 = time(NULL);
  316.  
  317. printf("Temps total %lds\n", (t2-t1)%60 );
  318.  
  319. double max1=0, max2=0, max3=0, max4=0, max5= 0;
  320. int k1, k2, k3, k4, k5;
  321.  
  322. double max1_tmp, max2_tmp, max3_tmp, max4_tmp, max5_tmp;
  323. int k1_tmp, k2_tmp, k3_tmp, k4_tmp, k5_tmp;
  324.  
  325. double min1=1, min2=1, min3=1, min4=1, min5= 1;
  326. int p1, p2, p3, p4, p5;
  327.  
  328. double min1_tmp, min2_tmp, min3_tmp, min4_tmp, min5_tmp;
  329. int p1_tmp, p2_tmp, p3_tmp, p4_tmp, p5_tmp;
  330.  
  331.  
  332.  
  333.  
  334.  
  335. double sum = 0;
  336.  
  337. for(i=0; i<n; i++){
  338. sum += P[i];
  339. max1_tmp = max1;
  340. max2_tmp = max2;
  341. max3_tmp = max3;
  342. max4_tmp = max4;
  343. max5_tmp = max5;
  344.  
  345. k1_tmp = k1;
  346. k2_tmp = k2;
  347. k3_tmp = k3;
  348. k4_tmp = k4;
  349. k5_tmp = k5;
  350.  
  351. min1_tmp = min1;
  352. min2_tmp = min2;
  353. min3_tmp = min3;
  354. min4_tmp = min4;
  355. min5_tmp = min5;
  356.  
  357. p1_tmp = p1;
  358. p2_tmp = p2;
  359. p3_tmp = p3;
  360. p4_tmp = p4;
  361. p5_tmp = p5;
  362.  
  363.  
  364.  
  365.  
  366. if(max1 < P[i]){
  367.  
  368. max1 = P[i];
  369. k1 = i;
  370.  
  371. max2 = max1_tmp;
  372. k2 = k1_tmp;
  373.  
  374. max3 = max2_tmp;
  375. k3 = k2_tmp;
  376.  
  377. max4 = max3_tmp;
  378. k4 = k3_tmp;
  379.  
  380. max5 = max4_tmp;
  381. k5 = k4_tmp;
  382.  
  383. }
  384. else{
  385. if(max2 < P[i] ){
  386.  
  387. max2 = P[i];
  388. k2 = i;
  389.  
  390. max3 = max2_tmp;
  391. k3 = k2_tmp;
  392.  
  393. max4 = max3_tmp;
  394. k4 = k3_tmp;
  395.  
  396. max5 = max4_tmp;
  397. k5 = k4_tmp;
  398.  
  399.  
  400. }
  401. else{
  402. if(max3 < P[i]){
  403. max3 = P[i];
  404. k3 = i;
  405.  
  406. max4 = max3_tmp;
  407. k4 = k3_tmp;
  408.  
  409. max5 = max4_tmp;
  410. k5 = k4_tmp;
  411.  
  412. }
  413. else{
  414. if(max4 < P[i]){
  415. max4 = P[i];
  416. k4 = i;
  417.  
  418. max5 = max4_tmp;
  419. k5 = k4_tmp;
  420. }
  421. else{
  422. if(max5 < P[i]){
  423.  
  424. max5 = P[i];
  425. k5 = i;
  426.  
  427. }
  428.  
  429. }
  430.  
  431. }
  432.  
  433. }
  434.  
  435. }
  436.  
  437.  
  438. if(min1 > P[i] ){
  439. min1 = P[i];
  440. p1 = i;
  441.  
  442. min2 = min1_tmp;
  443. p2 = p1_tmp;
  444.  
  445. min3 = min2_tmp;
  446. p3 = p2_tmp;
  447.  
  448. min4 = min3_tmp;
  449. p4 = p3_tmp;
  450.  
  451. min5 = min4_tmp;
  452. p5 = p4_tmp;
  453.  
  454. }
  455. else{
  456. if(min2 > P[i]){
  457.  
  458. min2 = P[i];
  459. p2 = i;
  460.  
  461. min3 = min2_tmp;
  462. p3 = p2_tmp;
  463.  
  464. min4 = min3_tmp;
  465. p4 = p3_tmp;
  466.  
  467. min5 = min4_tmp;
  468. p5 = p4_tmp;
  469.  
  470. }
  471. else{
  472.  
  473. if(min3 > P[i]){
  474.  
  475. min3 = P[i];
  476. p3 = i;
  477.  
  478. min4 = min3_tmp;
  479. p4 = p3_tmp;
  480.  
  481. min5 = min4_tmp;
  482. p5 = p4_tmp;
  483.  
  484. }
  485. else{
  486. if(min4 > P[i]){
  487.  
  488. min4 = P[i];
  489. p4 = i;
  490.  
  491. min5 = min4_tmp;
  492. p5 = p4_tmp;
  493.  
  494. }
  495. else{
  496. if(min5 > P[i]){
  497. min5 = P[i];
  498. p5 = i;
  499.  
  500. }
  501.  
  502. }
  503.  
  504. }
  505.  
  506.  
  507. }
  508.  
  509. }
  510.  
  511.  
  512.  
  513. }
  514.  
  515.  
  516. printf("%.20f\t%d\n", max1, correspondance[k1]);
  517. printf("%.20f\t%d\n", max2, correspondance[k2]);
  518. printf("%.20f\t%d\n", max3, correspondance[k3]);
  519. printf("%.20f\t%d\n", max4, correspondance[k4]);
  520. printf("%.20f\t%d\n", max5, correspondance[k5]);
  521.  
  522.  
  523. printf("%.20f\t%d\n", min1, correspondance[p1]);
  524. printf("%.20f\t%d\n", min2, correspondance[p2]);
  525. printf("%.20f\t%d\n", min3, correspondance[p3]);
  526. printf("%.20f\t%d\n", min4, correspondance[p4]);
  527. printf("%.20f\t%d\n", min5, correspondance[p5]);
  528.  
  529.  
  530. printf("Somme %f\n", sum);
  531.  
  532. fflush(NULL);
  533.  
  534. int *d_in = computeInDegrees(adj, n, m);
  535.  
  536. /*writeFilePageRankResult("pr_15.txt", P, n);
  537. writeFileDegrees("deg_out_15.txt", d_out, n, correspondance);
  538. writeFileDegrees("deg_in_15.txt", d_in, n, correspondance);*/
  539.  
  540. /*free(P);
  541.  
  542. free(d_out);
  543. free(adj);
  544. free(res[2]);*/
  545.  
  546. return 0;
  547. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!