Grafalgo
Library of useful data structures and algorithms
|
00001 #include "stdinc.h" 00002 #include "Flograph.h" 00003 #include "ppFifo.h" 00004 #include "ppHiLab.h" 00005 #include "shortPath.h" 00006 #include "dinic.h" 00007 #include "dinicDtrees.h" 00008 #include "Util.h" 00009 00010 void eval(Flograph &fg) { 00011 int n = fg.n(); int m = fg.m(); 00012 int t1, t2, floVal; 00013 00014 t1 = Util::getTime(); 00015 ppFifo(fg,floVal,false); 00016 t2 = Util::getTime(); 00017 cout << n << " " << m; 00018 cout << " " << floVal << " " << t2-t1 << " ppFifo" << endl; 00019 fg.clear(); 00020 00021 t1 = Util::getTime(); 00022 ppFifo(fg,floVal,true); 00023 t2 = Util::getTime(); 00024 cout << n << " " << m; 00025 cout << " " << floVal << " " << t2-t1 << " ppFifoBatch" << endl; 00026 fg.clear(); 00027 00028 t1 = Util::getTime(); 00029 ppHiLab(fg,floVal,false); 00030 t2 = Util::getTime(); 00031 cout << n << " " << m; 00032 cout << " " << floVal << " " << t2-t1 << " ppHiLab" << endl; 00033 fg.clear(); 00034 00035 t1 = Util::getTime(); 00036 ppHiLab(fg,floVal,true); 00037 t2 = Util::getTime(); 00038 cout << n << " " << m; 00039 cout << " " << floVal << " " << t2-t1 << " ppHiLabBatch" << endl; 00040 fg.clear(); 00041 } 00042 00043 void badcase(int k1, int k2, Flograph& fg) { 00044 int i,j, n, m, c1, c2, c3, c4, bl, br; 00045 edge e; 00046 00047 // determine first vertex in each group 00048 c1 = 2; // start of short chain from source 00049 c2 = c1 + 4*(k1-1)+1; // start of long chain from source 00050 bl = c2 + 4*(k1-1)+3; // start of 1st vertex group in bipartite graph 00051 br = bl + k2; // start of 2nd vertex group in bipartite graph 00052 c3 = br + k2; // start of long chain to sink 00053 c4 = c3 + 4*(k1-1)+3; // start of short chain to sink 00054 00055 n = c4 + 4*(k1-1)+1; 00056 m = 16*(k1-1) + k2*k2 + 8*k1 + 4; 00057 fg.resize(n,m); 00058 fg.setSrcSnk(1,n); 00059 00060 // build short chain from source 00061 for (i = 0; c1+i < c2; i++) { 00062 if ((i%4) == 0) { 00063 e = fg.join(fg.src(),c1+i); 00064 if (i == 0) fg.setCapacity(e,k2*k2*k2); 00065 else fg.setCapacity(e,k2*k2); 00066 } 00067 if (c1+i < c2-1) { 00068 e = fg.join(c1+i,c1+i+1); fg.setCapacity(e,2*k2*k2*k2); 00069 } 00070 } 00071 // build long chain from source 00072 for (i = 0; c2+i < bl; i++) { 00073 if ((i%4) == 0) { 00074 e = fg.join(fg.src(),c2+i); 00075 if (i == 0) fg.setCapacity(e,k2*k2*k2); 00076 else fg.setCapacity(e,k2*k2); 00077 } 00078 if (c2+i < bl-1) { 00079 e = fg.join(c2+i,c2+i+1); fg.setCapacity(e,2*k2*k2*k2); 00080 } 00081 } 00082 // connect source chains to bipartite graph 00083 for (i = 0; i < k2; i++) { 00084 e = fg.join(c2-1,bl+i); fg.setCapacity(e,2*k2*k2); 00085 e = fg.join(bl-1,br+i); fg.setCapacity(e,2*k2*k2); 00086 } 00087 // build central bipartite graph 00088 for (i = 0; i < k2; i++) { 00089 for (j = 0; j < k2; j++) { 00090 e = fg.join(bl+i, br+j); fg.setCapacity(e,1); 00091 } 00092 } 00093 // connect bipartite graph to sink chains 00094 for (i = 0; i < k2; i++) { 00095 e = fg.join(bl+i,c3); fg.setCapacity(e,2*k2*k2); 00096 e = fg.join(br+i,c4); fg.setCapacity(e,2*k2*k2); 00097 } 00098 // build long chain to sink 00099 for (i = 0; c3+i < c4; i++) { 00100 if ((i%4) == 2) { 00101 e = fg.join(c3+i,fg.snk()); fg.setCapacity(e,k2*k2); 00102 } 00103 if (c3+i < c4-1) { 00104 e = fg.join(c3+i,c3+i+1); fg.setCapacity(e,2*k2*k2*k2); 00105 } 00106 } 00107 // build short chain to sink 00108 for (i = 0; c4+i < n; i++) { 00109 if ((i%4) == 0) { 00110 e = fg.join(c4+i,fg.snk()); fg.setCapacity(e,k2*k2); 00111 } 00112 if (c4+i < n-1) { 00113 e = fg.join(c4+i,c4+i+1); fg.setCapacity(e,2*k2*k2*k2); 00114 } 00115 } 00116 } 00117 00118 main() { 00119 Flograph fg(10,20); 00120 00121 cout << "increasing density\n"; 00122 int n = 1024; int m; 00123 for (int i = 10; i <= 160; i += i) { 00124 m = i*n; 00125 fg.rgraph(n,m,50,100); 00126 fg.randCapacity(100*m/n,80); 00127 eval(fg); 00128 cout << endl; 00129 } 00130 cout << "bad cases - increasing density\n"; 00131 int k1 = 200; 00132 for (int k2 = 5; k2 <= k1; k2 = (k2 == 5 ? 50 : k2+50)) { 00133 badcase(k1,k2,fg); 00134 eval(fg); 00135 cout << endl; 00136 } 00137 }