Grafalgo
Library of useful data structures and algorithms
|
00001 00008 #include "Wflograph.h" 00009 00010 #define flo(x) floInfo[x].flo 00011 #define cpy(x) floInfo[x].cpy 00012 #define cst(x) cst[x] 00013 00014 namespace grafalgo { 00015 00022 Wflograph::Wflograph(int numv, int maxe, int s1, int t1) 00023 : Flograph(numv, maxe, s1, t1) { 00024 makeSpace(numv,maxe); 00025 } 00026 00027 Wflograph::~Wflograph() { freeSpace(); } 00028 00033 void Wflograph::makeSpace(int numv, int maxe) { 00034 try { 00035 cst = new floCost[maxe+1]; 00036 } catch (std::bad_alloc e) { 00037 stringstream ss; 00038 ss << "Wflograph::makeSpace: insufficient space for " 00039 << maxe << " edge costs"; 00040 string s = ss.str(); 00041 throw OutOfSpaceException(s); 00042 } 00043 } 00044 00046 void Wflograph::freeSpace() { delete [] cst; } 00047 00053 void Wflograph::resize(int numv, int maxe) { 00054 freeSpace(); 00055 Flograph::resize(numv,maxe); 00056 try { makeSpace(numv,maxe); } catch(OutOfSpaceException e) { 00057 string s; s = "Wflograph::resize:" + e.toString(s); 00058 throw OutOfSpaceException(s); 00059 } 00060 } 00061 00066 void Wflograph::expand(int numv, int maxe) { 00067 if (numv <= n() && maxe <= maxEdge) return; 00068 Wflograph old(this->n(),this->maxEdge); old.copyFrom(*this); 00069 resize(numv,maxe); this->copyFrom(old); 00070 } 00071 00073 void Wflograph::copyFrom(const Wflograph& source) { 00074 if (&source == this) return; 00075 if (source.n() > n() || source.m() > maxEdge) 00076 resize(source.n(),source.m()); 00077 else clear(); 00078 for (edge e = source.first(); e != 0; e = source.next(e)) { 00079 edge ee = join(source.tail(e),source.head(e)); 00080 setCapacity(ee,source.cap(source.tail(e),e)); 00081 setFlow(ee,source.f(source.tail(e),e)); 00082 setCost(ee,source.cost(source.tail(e),e)); 00083 } 00084 sortAdjLists(); 00085 } 00086 00091 bool Wflograph::readAdjList(istream& in) { 00092 if (!Util::verify(in,'[')) return 0; 00093 bool isSrc = false; bool isSnk = false; 00094 if (Util::verify(in,'-')) { 00095 if (!Util::verify(in,'>',true)) return 0; 00096 isSnk = true; 00097 } 00098 vertex u; 00099 if (!Adt::readItem(in,u)) return 0; 00100 if (Util::verify(in,'-')) { 00101 if (!Util::verify(in,'>',true)) return 0; 00102 isSrc = true; 00103 } 00104 if (!Util::verify(in,':')) return 0; 00105 if (u > n()) expand(u,m()); 00106 if (isSrc) setSrc(u); 00107 if (isSnk) setSnk(u); 00108 while (in.good() && !Util::verify(in,']')) { 00109 vertex v; 00110 if (!Adt::readItem(in,v)) return 0; 00111 if (v > n()) expand(v,m()); 00112 if (m() >= maxEdge) expand(n(),max(1,2*m())); 00113 flow capacity, flow; floCost ecost; 00114 if (!Util::verify(in,'(') || !Util::readInt(in,capacity) || 00115 !Util::verify(in,',') || !Util::readInt(in,ecost) || 00116 !Util::verify(in,',') || !Util::readInt(in,flow) || 00117 !Util::verify(in,')')) 00118 return 0; 00119 edge e = join(u,v); 00120 setCapacity(e,capacity); setFlow(e,flow); setCost(e,ecost); 00121 } 00122 return in.good(); 00123 } 00124 00130 string& Wflograph::adjList2string(vertex u, string& s) const { 00131 stringstream ss; s = ""; 00132 if (firstAt(u) == 0) return s; 00133 int cnt = 0; 00134 ss << "["; 00135 if (u == snk()) ss << "->"; 00136 ss << Adt::item2string(u,s); 00137 if (u == src()) ss << "->"; 00138 ss << ":"; 00139 for (edge e = firstAt(u); e != 0; e = nextAt(u,e)) { 00140 vertex v = head(e); 00141 ss << " " << item2string(v,s) << "(" << cap(u,e) << "," 00142 << cost(u,e) << "," << f(u,e) << ")"; 00143 if (++cnt >= 15 && nextAt(u,e) != 0) { 00144 ss << "\n"; cnt = 0; 00145 } 00146 } 00147 ss << "]\n"; 00148 s = ss.str(); 00149 return s; 00150 } 00151 00156 string& Wflograph::toDotString(string& s) const { 00157 stringstream ss; 00158 ss << "digraph G { " << endl; 00159 ss << Adt::item2string(src(),s) 00160 << " [ style = bold, peripheries = 2, color = red]; " 00161 << endl; 00162 ss << Adt::item2string(snk(),s) 00163 << " [ style = bold, peripheries = 2, color = blue]; " 00164 << endl; 00165 int cnt = 0; 00166 for (edge e = first(); e != 0; e = next(e)) { 00167 vertex u = min(left(e),right(e)); 00168 vertex v = max(left(e),right(e)); 00169 ss << Adt::item2string(u,s) << " -> "; 00170 ss << Adt::item2string(v,s); 00171 ss << " [label = \"(" << cap(u,e) << "," << cost(u,e) << "," 00172 << f(u,e) << ")\"]; "; 00173 if (++cnt == 10) { s += "\n"; cnt = 0; } 00174 } 00175 ss << "}\n" << endl; 00176 s = ss.str(); 00177 return s; 00178 } 00179 00185 string& Wflograph::edge2string(edge e, string& s) const { 00186 stringstream ss; 00187 vertex u = tail(e); vertex v = head(e); 00188 if (e == 0) { 00189 ss << "-"; 00190 } else { 00191 ss << "(" << item2string(u,s); 00192 ss << "," << item2string(v,s) << "," << cap(u,e) 00193 << "," << cost(u,e) << "," << f(u,e) << ")"; 00194 } 00195 s = ss.str(); 00196 return s; 00197 } 00198 00204 edge Wflograph::join(vertex u, vertex v) { 00205 assert(1 <= u && u <= n() && 1 <= v && v <= n() && m() < maxEdge); 00206 edge e = Flograph::join(u,v); cst[e] = 0; 00207 return e; 00208 } 00209 00214 void Wflograph::shuffle(int vp[], int ep[]) { 00215 edge e; 00216 floCost *cst1 = new floCost[m()+1]; 00217 00218 Flograph::shuffle(vp,ep); 00219 for (e = 1; e <= m(); e++) cst1[ep[e]] = cst[e]; 00220 for (e = 1; e <= m(); e++) cst[e] = cst1[e]; 00221 00222 delete [] cst1; 00223 } 00224 00230 void Wflograph::randCost(floCost lo, floCost hi) { 00231 for (edge e = first(); e != 0; e = next(e)) 00232 setCost(e,Util::randint(lo,hi)); 00233 } 00234 00235 } // ends namespace