root / cpp / pagerank.cpp @ 22:645db3196f17
History | View | Annotate | Download (5 kB)
1 | 0:7349ba594cdb | louridas | /* Copyright (c) 2010, Panos Louridas, GRNET S.A.
|
---|---|---|---|
2 | 0:7349ba594cdb | louridas | |
3 | 0:7349ba594cdb | louridas | All rights reserved.
|
4 | 0:7349ba594cdb | louridas | |
5 | 0:7349ba594cdb | louridas | Redistribution and use in source and binary forms, with or without
|
6 | 0:7349ba594cdb | louridas | modification, are permitted provided that the following conditions
|
7 | 0:7349ba594cdb | louridas | are met:
|
8 | 0:7349ba594cdb | louridas | |
9 | 0:7349ba594cdb | louridas | * Redistributions of source code must retain the above copyright
|
10 | 0:7349ba594cdb | louridas | notice, this list of conditions and the following disclaimer.
|
11 | 0:7349ba594cdb | louridas | |
12 | 0:7349ba594cdb | louridas | * Redistributions in binary form must reproduce the above copyright
|
13 | 0:7349ba594cdb | louridas | notice, this list of conditions and the following disclaimer in the
|
14 | 0:7349ba594cdb | louridas | documentation and/or other materials provided with the
|
15 | 0:7349ba594cdb | louridas | distribution.
|
16 | 0:7349ba594cdb | louridas | |
17 | 0:7349ba594cdb | louridas | * Neither the name of GRNET S.A, nor the names of its contributors
|
18 | 0:7349ba594cdb | louridas | may be used to endorse or promote products derived from this
|
19 | 0:7349ba594cdb | louridas | software without specific prior written permission.
|
20 | 0:7349ba594cdb | louridas | |
21 | 0:7349ba594cdb | louridas | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
22 | 0:7349ba594cdb | louridas | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
23 | 0:7349ba594cdb | louridas | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
|
24 | 0:7349ba594cdb | louridas | FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
|
25 | 0:7349ba594cdb | louridas | COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
|
26 | 0:7349ba594cdb | louridas | INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
27 | 0:7349ba594cdb | louridas | (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
28 | 0:7349ba594cdb | louridas | SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
29 | 0:7349ba594cdb | louridas | HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
30 | 0:7349ba594cdb | louridas | STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
31 | 0:7349ba594cdb | louridas | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
|
32 | 0:7349ba594cdb | louridas | OF THE POSSIBILITY OF SUCH DAMAGE.
|
33 | 0:7349ba594cdb | louridas | */
|
34 | 0:7349ba594cdb | louridas | |
35 | 0:7349ba594cdb | louridas | #include <iostream> |
36 | 0:7349ba594cdb | louridas | #include <vector> |
37 | 11:694b17feb881 | louridas | #include <cstring> |
38 | 11:694b17feb881 | louridas | #include <cstdlib> |
39 | 0:7349ba594cdb | louridas | |
40 | 0:7349ba594cdb | louridas | using namespace std; |
41 | 0:7349ba594cdb | louridas | |
42 | 0:7349ba594cdb | louridas | #include "table.h" |
43 | 0:7349ba594cdb | louridas | |
44 | 13:cf0df862e245 | louridas | const char *TRACE_ARG = "-t"; |
45 | 0:7349ba594cdb | louridas | const char *NUMERIC_ARG = "-n"; |
46 | 22:645db3196f17 | louridas | const char *ALPHA_ARG = "-a"; |
47 | 22:645db3196f17 | louridas | const char *CONVERGENCE_ARG = "-c"; |
48 | 22:645db3196f17 | louridas | const char *SIZE_ARG = "-s"; |
49 | 22:645db3196f17 | louridas | const char *DELIM_ARG = "-d"; |
50 | 22:645db3196f17 | louridas | const char *ITER_ARG = "-m"; |
51 | 22:645db3196f17 | louridas | |
52 | 22:645db3196f17 | louridas | void usage() {
|
53 | 22:645db3196f17 | louridas | cerr << "pagerank [-tn] [-a alpha ] [-s size] [-d delim] "
|
54 | 22:645db3196f17 | louridas | << "[-m max_iterations] <graph_file>" << endl
|
55 | 22:645db3196f17 | louridas | << " -t enable tracing " << endl
|
56 | 22:645db3196f17 | louridas | << " -n treat graph file as numeric; i.e. input comprises "
|
57 | 22:645db3196f17 | louridas | << "integer vertex names" << endl
|
58 | 22:645db3196f17 | louridas | << " -a alpha" << endl
|
59 | 22:645db3196f17 | louridas | << " the dumping factor " << endl
|
60 | 22:645db3196f17 | louridas | << " -c convergence" << endl
|
61 | 22:645db3196f17 | louridas | << " the convergence criterion " << endl
|
62 | 22:645db3196f17 | louridas | << " -s size" << endl
|
63 | 22:645db3196f17 | louridas | << " hint for internal tables " << endl
|
64 | 22:645db3196f17 | louridas | << " -d delim" << endl
|
65 | 22:645db3196f17 | louridas | << " delimiter for separating vertex names in each input"
|
66 | 22:645db3196f17 | louridas | << "line " << endl
|
67 | 22:645db3196f17 | louridas | << " -m max_iterations" << endl
|
68 | 22:645db3196f17 | louridas | << " maximum number of iterations to perform" << endl;
|
69 | 22:645db3196f17 | louridas | } |
70 | 22:645db3196f17 | louridas | |
71 | 22:645db3196f17 | louridas | int check_arg(int i, int max) { |
72 | 22:645db3196f17 | louridas | if (i == max) {
|
73 | 22:645db3196f17 | louridas | usage(); |
74 | 22:645db3196f17 | louridas | exit(1);
|
75 | 22:645db3196f17 | louridas | } |
76 | 22:645db3196f17 | louridas | return i + 1; |
77 | 22:645db3196f17 | louridas | } |
78 | 0:7349ba594cdb | louridas | |
79 | 0:7349ba594cdb | louridas | int main(int argc, char **argv) { |
80 | 0:7349ba594cdb | louridas | |
81 | 0:7349ba594cdb | louridas | Table t; |
82 | 0:7349ba594cdb | louridas | char *pos;
|
83 | 0:7349ba594cdb | louridas | char *endptr;
|
84 | 11:694b17feb881 | louridas | string input = "stdin"; |
85 | 22:645db3196f17 | louridas | |
86 | 22:645db3196f17 | louridas | int i = 1; |
87 | 22:645db3196f17 | louridas | while (i < argc) {
|
88 | 13:cf0df862e245 | louridas | if (!strcmp(argv[i], TRACE_ARG)) {
|
89 | 0:7349ba594cdb | louridas | t.set_trace(true);
|
90 | 0:7349ba594cdb | louridas | } else if (!strcmp(argv[i], NUMERIC_ARG)) { |
91 | 0:7349ba594cdb | louridas | t.set_numeric(true);
|
92 | 0:7349ba594cdb | louridas | } else if ((pos = strstr(argv[i], ALPHA_ARG))) { |
93 | 22:645db3196f17 | louridas | i = check_arg(i, argc); |
94 | 22:645db3196f17 | louridas | double alpha = strtod(argv[i], &endptr);
|
95 | 22:645db3196f17 | louridas | if ((alpha == 0 || alpha > 1) && endptr) { |
96 | 0:7349ba594cdb | louridas | cerr << "Invalid alpha argument" << endl;
|
97 | 0:7349ba594cdb | louridas | exit(1);
|
98 | 0:7349ba594cdb | louridas | } |
99 | 0:7349ba594cdb | louridas | t.set_alpha(alpha); |
100 | 0:7349ba594cdb | louridas | } else if ((pos = strstr(argv[i], CONVERGENCE_ARG))) { |
101 | 22:645db3196f17 | louridas | i = check_arg(i, argc); |
102 | 22:645db3196f17 | louridas | double convergence = strtod(argv[i], &endptr);
|
103 | 0:7349ba594cdb | louridas | if (convergence == 0 && endptr) { |
104 | 0:7349ba594cdb | louridas | cerr << "Invalid convergence argument" << endl;
|
105 | 0:7349ba594cdb | louridas | exit(1);
|
106 | 0:7349ba594cdb | louridas | } |
107 | 0:7349ba594cdb | louridas | t.set_convergence(convergence); |
108 | 0:7349ba594cdb | louridas | } else if ((pos = strstr(argv[i], SIZE_ARG))) { |
109 | 22:645db3196f17 | louridas | i = check_arg(i, argc); |
110 | 22:645db3196f17 | louridas | size_t size = strtol(argv[i], &endptr, 10);
|
111 | 0:7349ba594cdb | louridas | if (size == 0 && endptr) { |
112 | 0:7349ba594cdb | louridas | cerr << "Invalid size argument" << endl;
|
113 | 0:7349ba594cdb | louridas | exit(1);
|
114 | 0:7349ba594cdb | louridas | } |
115 | 11:694b17feb881 | louridas | t.set_num_rows(size); |
116 | 18:d97c66c4b2bc | louridas | } else if ((pos = strstr(argv[i], ITER_ARG))) { |
117 | 22:645db3196f17 | louridas | i = check_arg(i, argc); |
118 | 22:645db3196f17 | louridas | size_t iterations = strtol(argv[i], &endptr, 10);
|
119 | 18:d97c66c4b2bc | louridas | if (iterations == 0 && endptr) { |
120 | 18:d97c66c4b2bc | louridas | cerr << "Invalid iterations argument" << endl;
|
121 | 18:d97c66c4b2bc | louridas | exit(1);
|
122 | 18:d97c66c4b2bc | louridas | } |
123 | 18:d97c66c4b2bc | louridas | t.set_max_iterations(iterations); |
124 | 0:7349ba594cdb | louridas | } else if ((pos = strstr(argv[i], DELIM_ARG))) { |
125 | 22:645db3196f17 | louridas | i = check_arg(i, argc); |
126 | 22:645db3196f17 | louridas | t.set_delim(argv[i]); |
127 | 22:645db3196f17 | louridas | } else if (i == argc-1) { |
128 | 22:645db3196f17 | louridas | input = argv[i]; |
129 | 22:645db3196f17 | louridas | } else {
|
130 | 22:645db3196f17 | louridas | usage(); |
131 | 22:645db3196f17 | louridas | exit(1);
|
132 | 0:7349ba594cdb | louridas | } |
133 | 22:645db3196f17 | louridas | i++; |
134 | 0:7349ba594cdb | louridas | } |
135 | 0:7349ba594cdb | louridas | |
136 | 18:d97c66c4b2bc | louridas | t.print_params(cerr); |
137 | 14:a00868c06f27 | louridas | cerr << "Reading input from " << input << "..." << endl; |
138 | 22:645db3196f17 | louridas | if (!strcmp(input.c_str(), "stdin")) { |
139 | 22:645db3196f17 | louridas | t.read_file("");
|
140 | 22:645db3196f17 | louridas | } else {
|
141 | 22:645db3196f17 | louridas | t.read_file(input); |
142 | 22:645db3196f17 | louridas | } |
143 | 22:645db3196f17 | louridas | t.print_table(); |
144 | 22:645db3196f17 | louridas | exit(1);
|
145 | 14:a00868c06f27 | louridas | cerr << "Calculating pagerank..." << endl;
|
146 | 0:7349ba594cdb | louridas | t.pagerank(); |
147 | 14:a00868c06f27 | louridas | cerr << "Done calculating!" << endl;
|
148 | 0:7349ba594cdb | louridas | t.print_pagerank_v(); |
149 | 0:7349ba594cdb | louridas | } |