Untitled
unknown
plain_text
4 years ago
7.4 kB
3
Indexable
#include "stdio.h" #include "stdlib.h" #include "string.h" #include "File_OP.h" #include "Graph_OP.h" #define _TEST_ 2000 #define INFINITIVE_VALUE 10e6 Graph LoadtoGraph(char *filename, int mode) { int maxrow = 0; int line = 0; rowdata *fileline = UnStructureFileRead(filename, &maxrow, &line); if (mode == _TEST_) PrintRowData(fileline, line); Graph gph = createGraph(); for (int i = 0; i < line; i++) { char str[10] = "\0"; strcpy(str, fileline[i].rowdata[0]); str[strlen(str) - 1] = '\0'; char *newstr = (char *)malloc(10 * sizeof(char)); strcpy(newstr, str); addVertex(gph, i, newstr); if (mode == _TEST_) printf("Here insert vertex = %s\n", newstr); strcpy(str, "\0"); } if (mode == _TEST_) printf("Here line = %d\n", line); for (int i = 0; i < line; i++) { char str[10] = "\0"; strcpy(str, fileline[i].rowdata[0]); str[strlen(str) - 1] = '\0'; int u = getID(gph, str); if (mode == _TEST_) printf("Here rownum = %d\n", fileline[i].rownum); for (int j = 1; j < fileline[i].rownum; j++) { char *out1 = NULL, *out2 = NULL; SeperateWord(fileline[i].rowdata[j], &out1, &out2, '-'); int v = getID(gph, out1); int w = atoi(out2); if (mode == _TEST_) printf("Insert Edge (%s,%s) = (%d,%d) = %d\n", out1, str, v, u, w); addEdge(gph, v, u, w); } } //************************************************************** for (int i = 0; i < line; i++) { freePointer(fileline[i].rowdata, fileline[i].rownum); } return gph; } Graph readURL(char *filename1, char *filename2) { int maxrow = 0; int maxline = 0; rowdata *row = UnStructureFileRead(filename1, &maxrow, &maxline); Graph gph = createGraph(); for (int i = 1; i < maxline; i++) { char *url = row[i].rowdata[0]; //printf("%s\n", url); char *id = row[i].rowdata[1]; int t = atoi(id); addVertex(gph, t, url); } int maxrow1 = 0; int maxline1 = 0; rowdata *row1 = UnStructureFileRead(filename2, &maxrow1, &maxline1); for (int i = 1; i < maxline1; i++) { int u = atoi(row1[i].rowdata[0]); for (int j = 1; j < row1[i].rownum; j++) { int v = atoi(row1[i].rowdata[j]); //printf("Add edge (u,v) = (%d,%d) = 1\n", u, v); addEdge(gph, u, v, 1); } } return gph; } double RankPoint[5000]; void PageRank(Graph g, int m) { JRB tmp; double LastRank[5000]; jrb_traverse(tmp, g.vertices){ int k = jval_i(tmp->key); LastRank[k] = RankPoint[k]; } int output[100]; for (int i = 0; i < m; i++) { jrb_traverse(tmp, g.vertices) { double S = 0; int t = jval_i(tmp->key); int n = indegree(g, t, output); for (int j = 0; j < n; j++) { int outsub[100]; int d = outdegree(g, output[j], outsub); if (d > 0) { S += LastRank[output[j]] / (double)d; } } RankPoint[t] = S; } } } int IsVertex(Graph g, int v) { if (jrb_find_int(g.vertices, v) != NULL) return 1; return 0; } void SearchforTop(int* Rank, int* output){ int max = 0; for (int i = 0; i < 5000; i++) { } } int main(int argc, char const *argv[]) { Graph gph; for (int i = 0; i < 5000; i++) { RankPoint[i] = 1; } int sel = 0; int cont = 1; int count_out = 0; int count_in = 0; int output2[100] = {0}; JRB tmp2, sub2; int id1, id2; while (cont) { printf("================== Here's program menu ===================\n"); printf("1. Print Webpage, URL\n2. PageRank(1)\n3. PageRank(m)\n4. Pages only out/in-connected\n5. SPT URL\n6. Exit\n"); printf("Select: "); scanf("%d", &sel); switch (sel) { case 1: gph = readURL("webpages.txt", "pageConnections.txt"); JRB tmp1; jrb_traverse(tmp1, gph.vertices) { printf("%s %d\n", jval_s(tmp1->val), jval_i(tmp1->key)); } //========================================================================================= int max = 0; int min = 1000; JRB tmp; JRB maxnode, minnode; int output[100] = {0}; jrb_traverse(tmp, gph.vertices) { int t = indegree(gph, jval_i(tmp->key), output); //printf("Here %d: %d\n", jval_i(tmp->key), t); if (t > max) { max = t; maxnode = tmp; } if (t < min) { min = t; minnode = tmp; } } printf("Page with highest in-connection: %s %d\n", jval_s(maxnode->val), jval_i(maxnode->key)); printf("Page with lowest in-connection: %s %d\n", jval_s(minnode->val), jval_i(minnode->key)); break; case 2: PageRank(gph, 1); printf("After 1 Loop, Ranks are: \n"); JRB tr; jrb_traverse(tr, gph.vertices) { int u = jval_i(tr->key); char *web = jval_s(tr->val); printf("%s %d %.2f\n", web, u, RankPoint[u]); } break; case 3: printf("Insert m = "); int loop = 0; scanf("%d", &loop); PageRank(gph, loop); jrb_traverse(tr, gph.vertices) { int u = jval_i(tr->key); char *web = jval_s(tr->val); printf("%s %d %.2f\n", web, u, RankPoint[u]); } printf("Top 3 page rank: \n"); break; case 4: jrb_traverse(tmp2, gph.vertices) { if (outdegree(gph, jval_i(tmp2->key), output2) == 0) { count_out++; } if (indegree(gph, jval_i(tmp2->key), output2) == 0) { count_in++; } } printf("Number of out-only pages: %d\nNumber of in-only pages: %d\n", count_out, count_in); break; case 5: do { printf("Insert id1 id2: "); scanf("%d %d", &id1, &id2); } while (IsVertex(gph, id1) && IsVertex(gph, id2)); int path[100]; int length[100]; double f = shortestPath(gph, id1, id2, path, length); if (f != INFINITIVE_VALUE) printf("Shortest Path: %.2f\n", f); else printf("No connection found\n"); break; case 6: printf("End of service\nExitting....\n"); cont = 0; break; default: printf("Please select again from 1 to 6 only\n"); break; } } dropGraph(gph); return 0; }
Editor is loading...