542/doc/mst_rep_8cpp_source.html

00001 // usage:
00002 //      mstRep method reps n m maxkey
00003 //
00004 // mstRep repeatedly generates a random graph and computes
00005 // its minimum spanning tree using the specified method.
00006 // Reps is the number of repetitions.
00007 // n is the number of vertices, m is the number of edges,
00008 // maxkey is the maximum key
00009 //
00010
00011 #include "stdinc.h"
00012 #include <sys/times.h>
00013 #include <unistd.h>
00014 #include "Wgraph.h"
00015 #include "Util.h"
00016
00017 using namespace grafalgo;
00018
00019 extern void kruskal(Wgraph&, list<int>&);
00020 extern void prim(Wgraph&, list<int>&);
00021 extern void primF(Wgraph&, list<int>&);
00022 extern void rrobin(Wgraph&, list<int>&);
00023
00024 int main(int argc, char* argv[]) {
00025         int i, reps, n, m, maxkey;
00026         int time1, time2, maxtime, mintime, totaltime;
00027         if (argc != 6 ||
00028             sscanf(argv[2],"%d",&reps) != 1 ||
00029             sscanf(argv[3],"%d",&n) != 1 ||
00030             sscanf(argv[4],"%d",&m) != 1 ||
00031             sscanf(argv[5],"%d",&maxkey) != 1)
00032                 Util::fatal("usage: mstRep method reps n m maxkey");
00033
00034         srand(1);
00035         Wgraph wg(n,m);
00036         list<edge> mstree;
00037         mintime = Util::BIGINT32; maxtime = 0; totaltime = 0;
00038         for (i = 1; i <= reps; i++) {
00039                 wg.rcgraph(n,m);
00040                 wg.randWeight(0,maxkey);
00041
00042                 if (strcmp(argv[1],"kruskal") == 0) {
00043                         time1 = Util::getTime();
00044                         kruskal(wg,mstree);
00045                 } else if (strcmp(argv[1],"prim") == 0) {
00046                         time1 = Util::getTime();
00047                         prim(wg,mstree);
00048                 } else if (strcmp(argv[1],"primF") == 0) {
00049                         time1 = Util::getTime();
00050                         primF(wg,mstree);
00051                 } else if (strcmp(argv[1],"rrobin") == 0) {
00052                         time1 = Util::getTime();
00053                         rrobin(wg,mstree);
00054                 } else {
00055                         Util::fatal("mstRep: undefined method");
00056                 }
00057                 time2 = Util::getTime();
00058                 mstree.clear();
00059                 if (time1 == -1 || time2 == -1) {
00060                         Util::fatal("mstRep: can't read time values");
00061                 }
00062                 int diff = time2 - time1;
00063                 mintime = min(diff,mintime);
00064                 maxtime = max(diff,maxtime);
00065                 totaltime += diff;
00066         }
00067         double avgtime = ((double) totaltime/reps);
00068         cout << "avgtime=" << avgtime << " us  ";
00069         cout << "mintime=" << mintime << " us  ";
00070         cout << "maxtime=" << maxtime << " us" << endl;
00071 }