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 string stats; 00015 t1 = Util::getTime(); 00016 ppHiLab(fg,floVal,false,stats); 00017 t2 = Util::getTime(); 00018 cout << n << " " << m << " " << stats; 00019 cout << " " << floVal << " " << t2-t1 << " ppHiLab" << endl; 00020 fg.clear(); 00021 t1 = Util::getTime(); 00022 ppHiLab(fg,floVal,true,stats); 00023 t2 = Util::getTime(); 00024 cout << n << " " << m << " " << stats; 00025 cout << " " << floVal << " " << t2-t1 << " ppHiLabBatch" << endl; 00026 fg.clear(); 00027 } 00028 00029 void badcase(int k1, int k2, Flograph& fg) { 00030 int i,j, n, m, c1, c2, c3, c4, bl, br; 00031 edge e; 00032 00033 // determine first vertex in each group 00034 c1 = 2; // start of short chain from source 00035 c2 = c1 + 4*(k1-1)+1; // start of long chain from source 00036 bl = c2 + 4*(k1-1)+3; // start of 1st vertex group in bipartite graph 00037 br = bl + k2; // start of 2nd vertex group in bipartite graph 00038 c3 = br + k2; // start of long chain to sink 00039 c4 = c3 + 4*(k1-1)+3; // start of short chain to sink 00040 00041 n = c4 + 4*(k1-1)+1; 00042 m = 16*(k1-1) + k2*k2 + 8*k1 + 4; 00043 fg.resize(n,m); 00044 fg.setSrcSnk(1,n); 00045 00046 // build short chain from source 00047 for (i = 0; c1+i < c2; i++) { 00048 if ((i%4) == 0) { 00049 e = fg.join(fg.src(),c1+i); 00050 if (i == 0) fg.setCapacity(e,k2*k2*k2); 00051 else fg.setCapacity(e,k2*k2); 00052 } 00053 if (c1+i < c2-1) { 00054 e = fg.join(c1+i,c1+i+1); fg.setCapacity(e,2*k2*k2*k2); 00055 } 00056 } 00057 // build long chain from source 00058 for (i = 0; c2+i < bl; i++) { 00059 if ((i%4) == 0) { 00060 e = fg.join(fg.src(),c2+i); 00061 if (i == 0) fg.setCapacity(e,k2*k2*k2); 00062 else fg.setCapacity(e,k2*k2); 00063 } 00064 if (c2+i < bl-1) { 00065 e = fg.join(c2+i,c2+i+1); fg.setCapacity(e,2*k2*k2*k2); 00066 } 00067 } 00068 // connect source chains to bipartite graph 00069 for (i = 0; i < k2; i++) { 00070 e = fg.join(c2-1,bl+i); fg.setCapacity(e,2*k2*k2); 00071 e = fg.join(bl-1,br+i); fg.setCapacity(e,2*k2*k2); 00072 } 00073 // build central bipartite graph 00074 for (i = 0; i < k2; i++) { 00075 for (j = 0; j < k2; j++) { 00076 e = fg.join(bl+i, br+j); fg.setCapacity(e,1); 00077 } 00078 } 00079 // connect bipartite graph to sink chains 00080 for (i = 0; i < k2; i++) { 00081 e = fg.join(bl+i,c3); fg.setCapacity(e,2*k2*k2); 00082 e = fg.join(br+i,c4); fg.setCapacity(e,2*k2*k2); 00083 } 00084 // build long chain to sink 00085 for (i = 0; c3+i < c4; i++) { 00086 if ((i%4) == 2) { 00087 e = fg.join(c3+i,fg.snk()); fg.setCapacity(e,k2*k2); 00088 } 00089 if (c3+i < c4-1) { 00090 e = fg.join(c3+i,c3+i+1); fg.setCapacity(e,2*k2*k2*k2); 00091 } 00092 } 00093 // build short chain to sink 00094 for (i = 0; c4+i < n; i++) { 00095 if ((i%4) == 0) { 00096 e = fg.join(c4+i,fg.snk()); fg.setCapacity(e,k2*k2); 00097 } 00098 if (c4+i < n-1) { 00099 e = fg.join(c4+i,c4+i+1); fg.setCapacity(e,2*k2*k2*k2); 00100 } 00101 } 00102 } 00103 00104 main() { 00105 Flograph fg(10,20); 00106 00107 cout << "increasing n\n"; 00108 int n = 256; 00109 int m; 00110 for (int i = 8; i <= 11; i++) { 00111 m = i*n; 00112 for (int j = 1; j <= 4; j++) { 00113 fg.rgraph(n,m,50,20); 00114 fg.randCapacity(100*m/n,80); 00115 eval(fg); 00116 } 00117 cout << endl; 00118 n += n; 00119 } 00120 }