[174] | 1 | // -*- c++ -*- |
---|
[259] | 2 | #ifndef HUGO_GRAPH_WRAPPER_H |
---|
| 3 | #define HUGO_GRAPH_WRAPPER_H |
---|
[76] | 4 | |
---|
[174] | 5 | #include <invalid.h> |
---|
| 6 | |
---|
[105] | 7 | namespace hugo { |
---|
[76] | 8 | |
---|
[312] | 9 | // template<typename Graph> |
---|
| 10 | // class TrivGraphWrapper { |
---|
| 11 | // protected: |
---|
| 12 | // Graph* graph; |
---|
[76] | 13 | |
---|
[312] | 14 | // public: |
---|
| 15 | // // typedef Graph BaseGraph; |
---|
| 16 | // typedef Graph ParentGraph; |
---|
[303] | 17 | |
---|
[312] | 18 | // // TrivGraphWrapper() : graph(0) { } |
---|
| 19 | // TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
---|
| 20 | // // void setGraph(Graph& _graph) { graph = &_graph; } |
---|
| 21 | // // Graph& getGraph() const { return *graph; } |
---|
[76] | 22 | |
---|
[312] | 23 | // typedef typename Graph::Node Node; |
---|
| 24 | // class NodeIt : public Graph::NodeIt { |
---|
| 25 | // public: |
---|
| 26 | // NodeIt() { } |
---|
| 27 | // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
---|
| 28 | // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
---|
| 29 | // NodeIt(const TrivGraphWrapper<Graph>& _G) : |
---|
| 30 | // Graph::NodeIt(*(_G.graph)) { } |
---|
| 31 | // }; |
---|
| 32 | // typedef typename Graph::Edge Edge; |
---|
| 33 | // class OutEdgeIt : public Graph::OutEdgeIt { |
---|
| 34 | // public: |
---|
| 35 | // OutEdgeIt() { } |
---|
| 36 | // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
---|
| 37 | // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
---|
| 38 | // OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : |
---|
| 39 | // Graph::OutEdgeIt(*(_G.graph), n) { } |
---|
| 40 | // }; |
---|
| 41 | // class InEdgeIt : public Graph::InEdgeIt { |
---|
| 42 | // public: |
---|
| 43 | // InEdgeIt() { } |
---|
| 44 | // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
---|
| 45 | // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
---|
| 46 | // InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : |
---|
| 47 | // Graph::InEdgeIt(*(_G.graph), n) { } |
---|
| 48 | // }; |
---|
| 49 | // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 50 | // class EdgeIt : public Graph::EdgeIt { |
---|
| 51 | // public: |
---|
| 52 | // EdgeIt() { } |
---|
| 53 | // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
---|
| 54 | // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
---|
| 55 | // EdgeIt(const TrivGraphWrapper<Graph>& _G) : |
---|
| 56 | // Graph::EdgeIt(*(_G.graph)) { } |
---|
| 57 | // }; |
---|
[168] | 58 | |
---|
[312] | 59 | // NodeIt& first(NodeIt& i) const { |
---|
| 60 | // i=NodeIt(*this); |
---|
[265] | 61 | // return i; |
---|
| 62 | // } |
---|
[312] | 63 | // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 64 | // i=OutEdgeIt(*this, p); |
---|
[265] | 65 | // return i; |
---|
| 66 | // } |
---|
[312] | 67 | // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 68 | // i=InEdgeIt(*this, p); |
---|
| 69 | // return i; |
---|
| 70 | // } |
---|
| 71 | // EdgeIt& first(EdgeIt& i) const { |
---|
| 72 | // i=EdgeIt(*this); |
---|
| 73 | // return i; |
---|
| 74 | // } |
---|
| 75 | // // template<typename I> I& first(I& i) const { |
---|
| 76 | // // i=I(*this); |
---|
| 77 | // // return i; |
---|
| 78 | // // } |
---|
| 79 | // // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 80 | // // i=I(*this, p); |
---|
| 81 | // // return i; |
---|
| 82 | // // } |
---|
[76] | 83 | |
---|
[312] | 84 | // // template<typename I> I getNext(const I& i) const { |
---|
| 85 | // // return graph->getNext(i); } |
---|
[76] | 86 | |
---|
[312] | 87 | // NodeIt& next(NodeIt& i) const { graph->next(i); return i; } |
---|
| 88 | // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } |
---|
| 89 | // InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } |
---|
| 90 | // EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } |
---|
| 91 | // // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
---|
| 92 | // template< typename It > It first() const { |
---|
| 93 | // It e; this->first(e); return e; } |
---|
[76] | 94 | |
---|
[312] | 95 | // template< typename It > It first(const Node& v) const { |
---|
| 96 | // It e; this->first(e, v); return e; } |
---|
[76] | 97 | |
---|
[312] | 98 | // Node head(const Edge& e) const { return graph->head(e); } |
---|
| 99 | // Node tail(const Edge& e) const { return graph->tail(e); } |
---|
[155] | 100 | |
---|
[312] | 101 | // template<typename I> bool valid(const I& i) const { |
---|
| 102 | // return graph->valid(i); } |
---|
[155] | 103 | |
---|
[312] | 104 | // //template<typename I> void setInvalid(const I &i); |
---|
| 105 | // //{ return graph->setInvalid(i); } |
---|
[155] | 106 | |
---|
[312] | 107 | // int nodeNum() const { return graph->nodeNum(); } |
---|
| 108 | // int edgeNum() const { return graph->edgeNum(); } |
---|
[76] | 109 | |
---|
[312] | 110 | // template<typename I> Node aNode(const I& e) const { |
---|
| 111 | // return graph->aNode(e); } |
---|
| 112 | // template<typename I> Node bNode(const I& e) const { |
---|
| 113 | // return graph->bNode(e); } |
---|
[76] | 114 | |
---|
[312] | 115 | // Node addNode() const { return graph->addNode(); } |
---|
| 116 | // Edge addEdge(const Node& tail, const Node& head) const { |
---|
| 117 | // return graph->addEdge(tail, head); } |
---|
[76] | 118 | |
---|
[312] | 119 | // template<typename I> void erase(const I& i) const { graph->erase(i); } |
---|
[76] | 120 | |
---|
[312] | 121 | // void clear() const { graph->clear(); } |
---|
[155] | 122 | |
---|
[312] | 123 | // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
[303] | 124 | // public: |
---|
[312] | 125 | // NodeMap(const TrivGraphWrapper<Graph>& _G) : |
---|
| 126 | // Graph::NodeMap<T>(*(_G.graph)) { } |
---|
| 127 | // NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : |
---|
| 128 | // Graph::NodeMap<T>(*(_G.graph), a) { } |
---|
[303] | 129 | // }; |
---|
[266] | 130 | |
---|
[312] | 131 | // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
---|
[303] | 132 | // public: |
---|
[312] | 133 | // EdgeMap(const TrivGraphWrapper<Graph>& _G) : |
---|
| 134 | // Graph::EdgeMap<T>(*(_G.graph)) { } |
---|
| 135 | // EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : |
---|
| 136 | // Graph::EdgeMap<T>(*(_G.graph), a) { } |
---|
[303] | 137 | // }; |
---|
[312] | 138 | |
---|
| 139 | // // template<typename Map, typename T> class NodeMapWrapper { |
---|
| 140 | // // protected: |
---|
| 141 | // // Map* map; |
---|
| 142 | // // public: |
---|
| 143 | // // NodeMapWrapper(Map& _map) : map(&_map) { } |
---|
| 144 | // // void set(Node n, T a) { map->set(n, a); } |
---|
| 145 | // // T get(Node n) const { return map->get(n); } |
---|
| 146 | // // }; |
---|
| 147 | |
---|
| 148 | // // template<typename Map, typename T> class EdgeMapWrapper { |
---|
| 149 | // // protected: |
---|
| 150 | // // Map* map; |
---|
| 151 | // // public: |
---|
| 152 | // // EdgeMapWrapper(Map& _map) : map(&_map) { } |
---|
| 153 | // // void set(Edge n, T a) { map->set(n, a); } |
---|
| 154 | // // T get(Edge n) const { return map->get(n); } |
---|
| 155 | // // }; |
---|
| 156 | // }; |
---|
[76] | 157 | |
---|
[303] | 158 | |
---|
| 159 | template<typename Graph> |
---|
| 160 | class GraphWrapper { |
---|
[212] | 161 | protected: |
---|
[303] | 162 | Graph* graph; |
---|
[212] | 163 | |
---|
| 164 | public: |
---|
[311] | 165 | typedef Graph BaseGraph; |
---|
[303] | 166 | typedef Graph ParentGraph; |
---|
[212] | 167 | |
---|
[303] | 168 | // GraphWrapper() : graph(0) { } |
---|
| 169 | GraphWrapper(Graph& _graph) : graph(&_graph) { } |
---|
| 170 | // void setGraph(Graph& _graph) { graph=&_graph; } |
---|
| 171 | // Graph& getGraph() const { return *graph; } |
---|
| 172 | |
---|
| 173 | typedef typename Graph::Node Node; |
---|
| 174 | class NodeIt : public Graph::NodeIt { |
---|
[312] | 175 | typedef typename Graph::NodeIt GraphNodeIt; |
---|
[265] | 176 | public: |
---|
| 177 | NodeIt() { } |
---|
[303] | 178 | NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
---|
| 179 | NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
---|
| 180 | NodeIt(const GraphWrapper<Graph>& _G) : |
---|
| 181 | Graph::NodeIt(*(_G.graph)) { } |
---|
[312] | 182 | // operator Node() const { |
---|
| 183 | // std::cout << "ize" << std::endl; |
---|
| 184 | // return Node(this->GraphNodeIt); |
---|
| 185 | // } |
---|
[265] | 186 | }; |
---|
[303] | 187 | typedef typename Graph::Edge Edge; |
---|
| 188 | class OutEdgeIt : public Graph::OutEdgeIt { |
---|
[312] | 189 | typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
---|
[265] | 190 | public: |
---|
| 191 | OutEdgeIt() { } |
---|
[303] | 192 | OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
---|
| 193 | OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
---|
| 194 | OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : |
---|
| 195 | Graph::OutEdgeIt(*(_G.graph), n) { } |
---|
[312] | 196 | // operator Edge() const { |
---|
| 197 | // std::cout << "ize" << std::endl; |
---|
| 198 | // return Edge(this->GraphOutEdgeIt); |
---|
| 199 | // } |
---|
[265] | 200 | }; |
---|
[303] | 201 | class InEdgeIt : public Graph::InEdgeIt { |
---|
[312] | 202 | typedef typename Graph::InEdgeIt GraphInEdgeIt; |
---|
[265] | 203 | public: |
---|
| 204 | InEdgeIt() { } |
---|
[303] | 205 | InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
---|
| 206 | InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
---|
| 207 | InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : |
---|
| 208 | Graph::InEdgeIt(*(_G.graph), n) { } |
---|
[312] | 209 | // operator Edge() const { |
---|
| 210 | // std::cout << "ize" << std::endl; |
---|
| 211 | // return Edge(this->InOutEdgeIt); |
---|
| 212 | // } |
---|
[265] | 213 | }; |
---|
[303] | 214 | //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 215 | class EdgeIt : public Graph::EdgeIt { |
---|
[312] | 216 | typedef typename Graph::EdgeIt GraphEdgeIt; |
---|
[265] | 217 | public: |
---|
| 218 | EdgeIt() { } |
---|
[303] | 219 | EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
---|
| 220 | EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
---|
| 221 | EdgeIt(const GraphWrapper<Graph>& _G) : |
---|
| 222 | Graph::EdgeIt(*(_G.graph)) { } |
---|
[312] | 223 | // operator Edge() const { |
---|
| 224 | // std::cout << "ize" << std::endl; |
---|
| 225 | // return Edge(this->GraphEdgeIt); |
---|
| 226 | // } |
---|
[265] | 227 | }; |
---|
[303] | 228 | |
---|
| 229 | NodeIt& first(NodeIt& i) const { |
---|
| 230 | i=NodeIt(*this); |
---|
[265] | 231 | return i; |
---|
| 232 | } |
---|
[303] | 233 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 234 | i=OutEdgeIt(*this, p); |
---|
| 235 | return i; |
---|
| 236 | } |
---|
| 237 | InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 238 | i=InEdgeIt(*this, p); |
---|
| 239 | return i; |
---|
| 240 | } |
---|
[311] | 241 | EdgeIt& first(EdgeIt& i) const { |
---|
| 242 | i=EdgeIt(*this); |
---|
| 243 | return i; |
---|
| 244 | } |
---|
[312] | 245 | // template<typename I> I& first(I& i) const { |
---|
| 246 | // i=I(*this); |
---|
| 247 | // return i; |
---|
| 248 | // } |
---|
[303] | 249 | // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 250 | // i=I(*this, p); |
---|
| 251 | // return i; |
---|
| 252 | // } |
---|
[212] | 253 | |
---|
[303] | 254 | // template<typename I> I getNext(const I& i) const { |
---|
| 255 | // return gw.getNext(i); } |
---|
[312] | 256 | |
---|
[311] | 257 | NodeIt& next(NodeIt& i) const { graph->next(i); return i; } |
---|
| 258 | OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } |
---|
| 259 | InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } |
---|
| 260 | EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } |
---|
[312] | 261 | // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
---|
[212] | 262 | template< typename It > It first() const { |
---|
| 263 | It e; this->first(e); return e; } |
---|
| 264 | |
---|
| 265 | template< typename It > It first(const Node& v) const { |
---|
| 266 | It e; this->first(e, v); return e; } |
---|
| 267 | |
---|
[303] | 268 | Node head(const Edge& e) const { return graph->head(e); } |
---|
| 269 | Node tail(const Edge& e) const { return graph->tail(e); } |
---|
[312] | 270 | // Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); } |
---|
[212] | 271 | |
---|
[303] | 272 | template<typename I> bool valid(const I& i) const { |
---|
| 273 | return graph->valid(i); } |
---|
[212] | 274 | |
---|
| 275 | //template<typename I> void setInvalid(const I &i); |
---|
| 276 | //{ return graph->setInvalid(i); } |
---|
| 277 | |
---|
[303] | 278 | int nodeNum() const { return graph->nodeNum(); } |
---|
| 279 | int edgeNum() const { return graph->edgeNum(); } |
---|
[212] | 280 | |
---|
[303] | 281 | template<typename I> Node aNode(const I& e) const { |
---|
| 282 | return graph->aNode(e); } |
---|
| 283 | template<typename I> Node bNode(const I& e) const { |
---|
| 284 | return graph->bNode(e); } |
---|
[212] | 285 | |
---|
[303] | 286 | Node addNode() const { return graph->addNode(); } |
---|
[212] | 287 | Edge addEdge(const Node& tail, const Node& head) const { |
---|
[303] | 288 | return graph->addEdge(tail, head); } |
---|
[212] | 289 | |
---|
[303] | 290 | template<typename I> void erase(const I& i) const { graph->erase(i); } |
---|
[212] | 291 | |
---|
[303] | 292 | void clear() const { graph->clear(); } |
---|
[212] | 293 | |
---|
[303] | 294 | template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
[212] | 295 | public: |
---|
[303] | 296 | NodeMap(const GraphWrapper<Graph>& _G) : |
---|
| 297 | Graph::NodeMap<T>(*(_G.graph)) { } |
---|
| 298 | NodeMap(const GraphWrapper<Graph>& _G, T a) : |
---|
| 299 | Graph::NodeMap<T>(*(_G.graph), a) { } |
---|
[212] | 300 | }; |
---|
| 301 | |
---|
[303] | 302 | template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
---|
[212] | 303 | public: |
---|
[303] | 304 | EdgeMap(const GraphWrapper<Graph>& _G) : |
---|
| 305 | Graph::EdgeMap<T>(*(_G.graph)) { } |
---|
| 306 | EdgeMap(const GraphWrapper<Graph>& _G, T a) : |
---|
| 307 | Graph::EdgeMap<T>(*(_G.graph), a) { } |
---|
[212] | 308 | }; |
---|
| 309 | }; |
---|
| 310 | |
---|
[303] | 311 | |
---|
[230] | 312 | // template<typename Graph> |
---|
| 313 | // class RevGraphWrapper |
---|
| 314 | // { |
---|
| 315 | // protected: |
---|
| 316 | // Graph* graph; |
---|
| 317 | |
---|
| 318 | // public: |
---|
[303] | 319 | // typedef Graph ParentGraph; |
---|
[230] | 320 | |
---|
| 321 | // typedef typename Graph::Node Node; |
---|
| 322 | // typedef typename Graph::NodeIt NodeIt; |
---|
| 323 | |
---|
| 324 | // typedef typename Graph::Edge Edge; |
---|
| 325 | // typedef typename Graph::OutEdgeIt InEdgeIt; |
---|
| 326 | // typedef typename Graph::InEdgeIt OutEdgeIt; |
---|
| 327 | // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 328 | // typedef typename Graph::EdgeIt EdgeIt; |
---|
| 329 | |
---|
| 330 | // //RevGraphWrapper() : graph(0) { } |
---|
| 331 | // RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
---|
| 332 | |
---|
| 333 | // void setGraph(Graph& _graph) { graph = &_graph; } |
---|
| 334 | // Graph& getGraph() const { return (*graph); } |
---|
| 335 | |
---|
| 336 | // template<typename I> I& first(I& i) const { return graph->first(i); } |
---|
| 337 | // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 338 | // return graph->first(i, p); } |
---|
| 339 | |
---|
| 340 | // template<typename I> I getNext(const I& i) const { |
---|
| 341 | // return graph->getNext(i); } |
---|
| 342 | // template<typename I> I& next(I &i) const { return graph->next(i); } |
---|
| 343 | |
---|
| 344 | // template< typename It > It first() const { |
---|
| 345 | // It e; first(e); return e; } |
---|
| 346 | |
---|
| 347 | // template< typename It > It first(const Node& v) const { |
---|
| 348 | // It e; first(e, v); return e; } |
---|
| 349 | |
---|
| 350 | // Node head(const Edge& e) const { return graph->tail(e); } |
---|
| 351 | // Node tail(const Edge& e) const { return graph->head(e); } |
---|
| 352 | |
---|
| 353 | // template<typename I> bool valid(const I& i) const |
---|
| 354 | // { return graph->valid(i); } |
---|
| 355 | |
---|
| 356 | // //template<typename I> void setInvalid(const I &i); |
---|
| 357 | // //{ return graph->setInvalid(i); } |
---|
| 358 | |
---|
| 359 | // template<typename I> Node aNode(const I& e) const { |
---|
| 360 | // return graph->aNode(e); } |
---|
| 361 | // template<typename I> Node bNode(const I& e) const { |
---|
| 362 | // return graph->bNode(e); } |
---|
| 363 | |
---|
| 364 | // Node addNode() const { return graph->addNode(); } |
---|
| 365 | // Edge addEdge(const Node& tail, const Node& head) const { |
---|
| 366 | // return graph->addEdge(tail, head); } |
---|
| 367 | |
---|
| 368 | // int nodeNum() const { return graph->nodeNum(); } |
---|
| 369 | // int edgeNum() const { return graph->edgeNum(); } |
---|
| 370 | |
---|
| 371 | // template<typename I> void erase(const I& i) const { graph->erase(i); } |
---|
| 372 | |
---|
| 373 | // void clear() const { graph->clear(); } |
---|
| 374 | |
---|
| 375 | // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
| 376 | // public: |
---|
| 377 | // NodeMap(const RevGraphWrapper<Graph>& _G) : |
---|
| 378 | // Graph::NodeMap<T>(_G.getGraph()) { } |
---|
| 379 | // NodeMap(const RevGraphWrapper<Graph>& _G, T a) : |
---|
| 380 | // Graph::NodeMap<T>(_G.getGraph(), a) { } |
---|
| 381 | // }; |
---|
| 382 | |
---|
| 383 | // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
---|
| 384 | // public: |
---|
| 385 | // EdgeMap(const RevGraphWrapper<Graph>& _G) : |
---|
| 386 | // Graph::EdgeMap<T>(_G.getGraph()) { } |
---|
| 387 | // EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : |
---|
| 388 | // Graph::EdgeMap<T>(_G.getGraph(), a) { } |
---|
| 389 | // }; |
---|
| 390 | // }; |
---|
| 391 | |
---|
[235] | 392 | |
---|
[303] | 393 | template<typename Graph> |
---|
| 394 | class RevGraphWrapper : public GraphWrapper<Graph> { |
---|
[230] | 395 | public: |
---|
[303] | 396 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 397 | typedef typename GraphWrapper<Graph>::Edge Edge; |
---|
[279] | 398 | //FIXME |
---|
[303] | 399 | //If Graph::OutEdgeIt is not defined |
---|
[279] | 400 | //and we do not want to use RevGraphWrapper::InEdgeIt, |
---|
| 401 | //this won't work, because of typedef |
---|
| 402 | //OR |
---|
| 403 | //graphs have to define their non-existing iterators to void |
---|
| 404 | //Unfortunately all the typedefs are instantiated in templates, |
---|
| 405 | //unlike other stuff |
---|
[303] | 406 | typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; |
---|
| 407 | typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; |
---|
[237] | 408 | |
---|
[303] | 409 | // RevGraphWrapper() : GraphWrapper<Graph>() { } |
---|
| 410 | RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
---|
[238] | 411 | |
---|
[237] | 412 | Node head(const Edge& e) const |
---|
[303] | 413 | { return GraphWrapper<Graph>::tail(e); } |
---|
[237] | 414 | Node tail(const Edge& e) const |
---|
[303] | 415 | { return GraphWrapper<Graph>::head(e); } |
---|
[76] | 416 | }; |
---|
| 417 | |
---|
[263] | 418 | //Subgraph on the same node-set and partial edge-set |
---|
[311] | 419 | template<typename Graph, typename NodeFilterMap, |
---|
| 420 | typename EdgeFilterMap> |
---|
[303] | 421 | class SubGraphWrapper : public GraphWrapper<Graph> { |
---|
[263] | 422 | protected: |
---|
[311] | 423 | NodeFilterMap* node_filter_map; |
---|
| 424 | EdgeFilterMap* edge_filter_map; |
---|
[263] | 425 | public: |
---|
[311] | 426 | // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { } |
---|
| 427 | SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, |
---|
| 428 | EdgeFilterMap& _edge_filter_map) : |
---|
| 429 | GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), |
---|
| 430 | edge_filter_map(&_edge_filter_map) { } |
---|
[263] | 431 | |
---|
| 432 | |
---|
[311] | 433 | typedef typename Graph::Node Node; |
---|
| 434 | class NodeIt : public Graph::NodeIt { |
---|
| 435 | // typedef typename Graph::NodeIt GraphNodeIt; |
---|
| 436 | public: |
---|
| 437 | NodeIt() { } |
---|
| 438 | NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
---|
| 439 | NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
---|
| 440 | NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
---|
| 441 | Graph::NodeIt(*(_G.graph)) { |
---|
| 442 | while (_G.graph->valid((*this)/*.GraphNodeIt*/) && |
---|
| 443 | !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) |
---|
| 444 | _G.graph->next((*this)/*.GraphNodeIt*/); |
---|
| 445 | } |
---|
| 446 | }; |
---|
| 447 | typedef typename Graph::Edge Edge; |
---|
| 448 | class OutEdgeIt : public Graph::OutEdgeIt { |
---|
| 449 | // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
---|
| 450 | public: |
---|
| 451 | OutEdgeIt() { } |
---|
| 452 | OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
---|
| 453 | OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
---|
| 454 | OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& |
---|
| 455 | _G, const Node& n) : |
---|
| 456 | Graph::OutEdgeIt(*(_G.graph), n) { |
---|
| 457 | while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && |
---|
| 458 | !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) |
---|
| 459 | _G.graph->next((*this)/*.GraphOutEdgeIt*/); |
---|
| 460 | } |
---|
| 461 | }; |
---|
| 462 | class InEdgeIt : public Graph::InEdgeIt { |
---|
| 463 | // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
---|
| 464 | public: |
---|
| 465 | InEdgeIt() { } |
---|
| 466 | InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
---|
| 467 | InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
---|
| 468 | InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, |
---|
| 469 | const Node& n) : |
---|
| 470 | Graph::InEdgeIt(*(_G.graph), n) { |
---|
| 471 | while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && |
---|
| 472 | !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) |
---|
| 473 | _G.graph->next((*this)/*.GraphInEdgeIt*/); |
---|
| 474 | } |
---|
| 475 | }; |
---|
| 476 | // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 477 | class EdgeIt : public Graph::EdgeIt { |
---|
| 478 | // typedef typename Graph::EdgeIt GraphEdgeIt; |
---|
| 479 | public: |
---|
| 480 | EdgeIt() { } |
---|
| 481 | EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
---|
| 482 | EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
---|
| 483 | EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
---|
| 484 | Graph::EdgeIt(*(_G.graph)) { |
---|
| 485 | while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && |
---|
| 486 | !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) |
---|
| 487 | _G.graph->next((*this)/*.GraphEdgeIt*/); |
---|
| 488 | } |
---|
| 489 | }; |
---|
| 490 | |
---|
| 491 | NodeIt& first(NodeIt& i) const { |
---|
| 492 | i=NodeIt(*this); |
---|
[263] | 493 | return i; |
---|
| 494 | } |
---|
[311] | 495 | OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { |
---|
| 496 | i=OutEdgeIt(*this, n); |
---|
| 497 | return i; |
---|
| 498 | } |
---|
| 499 | InEdgeIt& first(InEdgeIt& i, const Node& n) const { |
---|
| 500 | i=InEdgeIt(*this, n); |
---|
| 501 | return i; |
---|
| 502 | } |
---|
| 503 | EdgeIt& first(EdgeIt& i) const { |
---|
| 504 | i=EdgeIt(*this); |
---|
[263] | 505 | return i; |
---|
| 506 | } |
---|
| 507 | |
---|
[311] | 508 | // template<typename I> I& first(I& i) const { |
---|
| 509 | // graph->first(i); |
---|
| 510 | // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
---|
| 511 | // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
---|
| 512 | // return i; |
---|
| 513 | // } |
---|
| 514 | // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 515 | // graph->first(i, p); |
---|
| 516 | // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
---|
| 517 | // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
---|
| 518 | // return i; |
---|
| 519 | // } |
---|
| 520 | |
---|
| 521 | NodeIt& next(NodeIt& i) const { |
---|
| 522 | graph->next(i); |
---|
| 523 | while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } |
---|
| 524 | return i; |
---|
| 525 | } |
---|
| 526 | OutEdgeIt& next(OutEdgeIt& i) const { |
---|
| 527 | graph->next(i); |
---|
| 528 | while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
---|
| 529 | return i; |
---|
| 530 | } |
---|
| 531 | InEdgeIt& next(InEdgeIt& i) const { |
---|
| 532 | graph->next(i); |
---|
| 533 | while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
---|
| 534 | return i; |
---|
| 535 | } |
---|
| 536 | EdgeIt& next(EdgeIt& i) const { |
---|
| 537 | graph->next(i); |
---|
| 538 | while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
---|
| 539 | return i; |
---|
| 540 | } |
---|
| 541 | |
---|
[263] | 542 | //template<typename I> I getNext(const I& i) const { |
---|
| 543 | // return gw.getNext(i); |
---|
| 544 | //} |
---|
[311] | 545 | // template<typename I> I& next(I &i) const { |
---|
| 546 | // graph->next(i); |
---|
| 547 | // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } |
---|
| 548 | // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
---|
| 549 | // return i; |
---|
| 550 | // } |
---|
[263] | 551 | |
---|
| 552 | template< typename It > It first() const { |
---|
| 553 | It e; this->first(e); return e; } |
---|
| 554 | |
---|
| 555 | template< typename It > It first(const Node& v) const { |
---|
| 556 | It e; this->first(e, v); return e; } |
---|
| 557 | }; |
---|
[155] | 558 | |
---|
[238] | 559 | // template<typename GraphWrapper> |
---|
[236] | 560 | // class UndirGraphWrapper { |
---|
| 561 | // protected: |
---|
[238] | 562 | // //Graph* graph; |
---|
| 563 | // GraphWrapper gw; |
---|
| 564 | |
---|
[236] | 565 | // public: |
---|
[303] | 566 | // typedef GraphWrapper ParentGraph; |
---|
[236] | 567 | |
---|
[238] | 568 | // typedef typename GraphWrapper::Node Node; |
---|
| 569 | // typedef typename GraphWrapper::NodeIt NodeIt; |
---|
[236] | 570 | |
---|
| 571 | // //typedef typename Graph::Edge Edge; |
---|
| 572 | // //typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 573 | // //typedef typename Graph::InEdgeIt InEdgeIt; |
---|
| 574 | // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 575 | // //typedef typename Graph::EdgeIt EdgeIt; |
---|
| 576 | |
---|
| 577 | // //private: |
---|
[238] | 578 | // typedef typename GraphWrapper::Edge GraphEdge; |
---|
| 579 | // typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt; |
---|
| 580 | // typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt; |
---|
[236] | 581 | // //public: |
---|
| 582 | |
---|
| 583 | // //UndirGraphWrapper() : graph(0) { } |
---|
[238] | 584 | // UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { } |
---|
[236] | 585 | |
---|
[238] | 586 | // //void setGraph(Graph& _graph) { graph = &_graph; } |
---|
| 587 | // //Graph& getGraph() const { return (*graph); } |
---|
[236] | 588 | |
---|
| 589 | // class Edge { |
---|
[238] | 590 | // friend class UndirGraphWrapper<GraphWrapper>; |
---|
[236] | 591 | // bool out_or_in; //true iff out |
---|
| 592 | // GraphOutEdgeIt out; |
---|
| 593 | // GraphInEdgeIt in; |
---|
| 594 | // public: |
---|
| 595 | // Edge() : out_or_in(), out(), in() { } |
---|
| 596 | // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
---|
| 597 | // operator GraphEdge() const { |
---|
| 598 | // if (out_or_in) return(out); else return(in); |
---|
| 599 | // } |
---|
| 600 | // friend bool operator==(const Edge& u, const Edge& v) { |
---|
| 601 | // if (v.out_or_in) |
---|
| 602 | // return (u.out_or_in && u.out==v.out); |
---|
| 603 | // else |
---|
| 604 | // return (!u.out_or_in && u.in==v.in); |
---|
| 605 | // } |
---|
| 606 | // friend bool operator!=(const Edge& u, const Edge& v) { |
---|
| 607 | // if (v.out_or_in) |
---|
| 608 | // return (!u.out_or_in || u.out!=v.out); |
---|
| 609 | // else |
---|
| 610 | // return (u.out_or_in || u.in!=v.in); |
---|
| 611 | // } |
---|
| 612 | // }; |
---|
| 613 | |
---|
| 614 | // class OutEdgeIt : public Edge { |
---|
[238] | 615 | // friend class UndirGraphWrapper<GraphWrapper>; |
---|
[236] | 616 | // public: |
---|
| 617 | // OutEdgeIt() : Edge() { } |
---|
| 618 | // OutEdgeIt(const Invalid& i) : Edge(i) { } |
---|
[238] | 619 | // OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n) |
---|
| 620 | // : Edge() { |
---|
[236] | 621 | // out_or_in=true; |
---|
[238] | 622 | // _G.gw.first(out, n); |
---|
| 623 | // if (!(_G.gw.valid(out))) { |
---|
[236] | 624 | // out_or_in=false; |
---|
[238] | 625 | // _G.gw.first(in, n); |
---|
[236] | 626 | // } |
---|
| 627 | // } |
---|
| 628 | // }; |
---|
| 629 | |
---|
| 630 | // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
---|
| 631 | // e.out_or_in=true; |
---|
[238] | 632 | // gw.first(e.out, n); |
---|
| 633 | // if (!(gw.valid(e.out))) { |
---|
[236] | 634 | // e.out_or_in=false; |
---|
[238] | 635 | // gw.first(e.in, n); |
---|
[236] | 636 | // } |
---|
| 637 | // return e; |
---|
| 638 | // } |
---|
| 639 | |
---|
| 640 | // OutEdgeIt& next(OutEdgeIt& e) const { |
---|
| 641 | // if (e.out_or_in) { |
---|
[238] | 642 | // Node n=gw.tail(e.out); |
---|
| 643 | // gw.next(e.out); |
---|
| 644 | // if (!gw.valid(e.out)) { |
---|
[236] | 645 | // e.out_or_in=false; |
---|
[238] | 646 | // gw.first(e.in, n); |
---|
[236] | 647 | // } |
---|
| 648 | // } else { |
---|
[238] | 649 | // gw.next(e.in); |
---|
[236] | 650 | // } |
---|
| 651 | // return e; |
---|
| 652 | // } |
---|
| 653 | |
---|
| 654 | // Node aNode(const OutEdgeIt& e) const { |
---|
[238] | 655 | // if (e.out_or_in) return gw.tail(e); else return gw.head(e); } |
---|
[236] | 656 | // Node bNode(const OutEdgeIt& e) const { |
---|
[238] | 657 | // if (e.out_or_in) return gw.head(e); else return gw.tail(e); } |
---|
[236] | 658 | |
---|
| 659 | // typedef OutEdgeIt InEdgeIt; |
---|
| 660 | |
---|
[238] | 661 | // template<typename I> I& first(I& i) const { return gw.first(i); } |
---|
[236] | 662 | // // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 663 | // // return graph->first(i, p); } |
---|
| 664 | |
---|
| 665 | // template<typename I> I getNext(const I& i) const { |
---|
[238] | 666 | // return gw.getNext(i); } |
---|
| 667 | // template<typename I> I& next(I &i) const { return gw.next(i); } |
---|
[236] | 668 | |
---|
| 669 | // template< typename It > It first() const { |
---|
| 670 | // It e; first(e); return e; } |
---|
| 671 | |
---|
| 672 | // template< typename It > It first(const Node& v) const { |
---|
| 673 | // It e; first(e, v); return e; } |
---|
| 674 | |
---|
[238] | 675 | // Node head(const Edge& e) const { return gw.head(e); } |
---|
| 676 | // Node tail(const Edge& e) const { return gw.tail(e); } |
---|
[236] | 677 | |
---|
| 678 | // template<typename I> bool valid(const I& i) const |
---|
[238] | 679 | // { return gw.valid(i); } |
---|
[236] | 680 | |
---|
| 681 | // //template<typename I> void setInvalid(const I &i); |
---|
| 682 | // //{ return graph->setInvalid(i); } |
---|
| 683 | |
---|
[238] | 684 | // int nodeNum() const { return gw.nodeNum(); } |
---|
| 685 | // int edgeNum() const { return gw.edgeNum(); } |
---|
[236] | 686 | |
---|
| 687 | // // template<typename I> Node aNode(const I& e) const { |
---|
| 688 | // // return graph->aNode(e); } |
---|
| 689 | // // template<typename I> Node bNode(const I& e) const { |
---|
| 690 | // // return graph->bNode(e); } |
---|
| 691 | |
---|
[238] | 692 | // Node addNode() const { return gw.addNode(); } |
---|
[236] | 693 | // // FIXME: ez igy nem jo, mert nem |
---|
| 694 | // // Edge addEdge(const Node& tail, const Node& head) const { |
---|
| 695 | // // return graph->addEdge(tail, head); } |
---|
| 696 | |
---|
[238] | 697 | // template<typename I> void erase(const I& i) const { gw.erase(i); } |
---|
[236] | 698 | |
---|
[238] | 699 | // void clear() const { gw.clear(); } |
---|
[236] | 700 | |
---|
[238] | 701 | // template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> { |
---|
[236] | 702 | // public: |
---|
[238] | 703 | // NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) : |
---|
| 704 | // GraphWrapper::NodeMap<T>(_G.gw) { } |
---|
| 705 | // NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) : |
---|
| 706 | // GraphWrapper::NodeMap<T>(_G.gw, a) { } |
---|
[236] | 707 | // }; |
---|
| 708 | |
---|
[238] | 709 | // template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> { |
---|
[236] | 710 | // public: |
---|
[238] | 711 | // EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) : |
---|
| 712 | // GraphWrapper::EdgeMap<T>(_G.gw) { } |
---|
| 713 | // EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) : |
---|
| 714 | // GraphWrapper::EdgeMap<T>(_G.gw, a) { } |
---|
[236] | 715 | // }; |
---|
| 716 | // }; |
---|
| 717 | |
---|
| 718 | |
---|
[303] | 719 | template<typename Graph> |
---|
| 720 | class UndirGraphWrapper : public GraphWrapper<Graph> { |
---|
[199] | 721 | protected: |
---|
[303] | 722 | typedef typename Graph::Edge GraphEdge; |
---|
| 723 | typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
---|
| 724 | typedef typename Graph::InEdgeIt GraphInEdgeIt; |
---|
| 725 | public: |
---|
| 726 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 727 | typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
---|
[236] | 728 | |
---|
[303] | 729 | // UndirGraphWrapper() : GraphWrapper<Graph>() { } |
---|
| 730 | UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
---|
[158] | 731 | |
---|
[174] | 732 | class Edge { |
---|
[303] | 733 | friend class UndirGraphWrapper<Graph>; |
---|
[279] | 734 | protected: |
---|
[158] | 735 | bool out_or_in; //true iff out |
---|
| 736 | GraphOutEdgeIt out; |
---|
| 737 | GraphInEdgeIt in; |
---|
| 738 | public: |
---|
[174] | 739 | Edge() : out_or_in(), out(), in() { } |
---|
| 740 | Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
---|
| 741 | operator GraphEdge() const { |
---|
[158] | 742 | if (out_or_in) return(out); else return(in); |
---|
| 743 | } |
---|
[239] | 744 | //FIXME |
---|
| 745 | //2 edges are equal if they "refer" to the same physical edge |
---|
| 746 | //is it good? |
---|
[174] | 747 | friend bool operator==(const Edge& u, const Edge& v) { |
---|
| 748 | if (v.out_or_in) |
---|
[239] | 749 | if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); |
---|
| 750 | //return (u.out_or_in && u.out==v.out); |
---|
[174] | 751 | else |
---|
[239] | 752 | if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); |
---|
| 753 | //return (!u.out_or_in && u.in==v.in); |
---|
[174] | 754 | } |
---|
| 755 | friend bool operator!=(const Edge& u, const Edge& v) { |
---|
| 756 | if (v.out_or_in) |
---|
[239] | 757 | if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); |
---|
| 758 | //return (!u.out_or_in || u.out!=v.out); |
---|
[174] | 759 | else |
---|
[239] | 760 | if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); |
---|
| 761 | //return (u.out_or_in || u.in!=v.in); |
---|
[174] | 762 | } |
---|
[158] | 763 | }; |
---|
| 764 | |
---|
[174] | 765 | class OutEdgeIt : public Edge { |
---|
[303] | 766 | friend class UndirGraphWrapper<Graph>; |
---|
[158] | 767 | public: |
---|
[174] | 768 | OutEdgeIt() : Edge() { } |
---|
| 769 | OutEdgeIt(const Invalid& i) : Edge(i) { } |
---|
[303] | 770 | OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) |
---|
[236] | 771 | : Edge() { |
---|
[303] | 772 | out_or_in=true; _G.graph->first(out, n); |
---|
| 773 | if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } |
---|
[158] | 774 | } |
---|
| 775 | }; |
---|
| 776 | |
---|
[238] | 777 | typedef OutEdgeIt InEdgeIt; |
---|
| 778 | |
---|
| 779 | class EdgeIt : public Edge { |
---|
[303] | 780 | friend class UndirGraphWrapper<Graph>; |
---|
[238] | 781 | protected: |
---|
| 782 | NodeIt v; |
---|
| 783 | public: |
---|
| 784 | EdgeIt() : Edge() { } |
---|
| 785 | EdgeIt(const Invalid& i) : Edge(i) { } |
---|
[303] | 786 | EdgeIt(const UndirGraphWrapper<Graph>& _G) |
---|
[238] | 787 | : Edge() { |
---|
| 788 | out_or_in=true; |
---|
| 789 | //Node v; |
---|
| 790 | _G.first(v); |
---|
[303] | 791 | if (_G.valid(v)) _G.graph->first(out); else out=INVALID; |
---|
| 792 | while (_G.valid(v) && !_G.graph->valid(out)) { |
---|
| 793 | _G.graph->next(v); |
---|
| 794 | if (_G.valid(v)) _G.graph->first(out); |
---|
[238] | 795 | } |
---|
| 796 | } |
---|
| 797 | }; |
---|
| 798 | |
---|
[212] | 799 | OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
---|
[303] | 800 | e.out_or_in=true; graph->first(e.out, n); |
---|
| 801 | if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } |
---|
[158] | 802 | return e; |
---|
| 803 | } |
---|
| 804 | |
---|
[238] | 805 | EdgeIt& first(EdgeIt& e) const { |
---|
| 806 | e.out_or_in=true; |
---|
| 807 | //NodeIt v; |
---|
| 808 | first(e.v); |
---|
[303] | 809 | if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; |
---|
| 810 | while (valid(e.v) && !graph->valid(e.out)) { |
---|
| 811 | graph->next(e.v); |
---|
| 812 | if (valid(e.v)) graph->first(e.out, e.v); |
---|
[238] | 813 | } |
---|
| 814 | return e; |
---|
| 815 | } |
---|
| 816 | |
---|
[303] | 817 | template<typename I> I& first(I& i) const { graph->first(i); return i; } |
---|
[238] | 818 | template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
[303] | 819 | graph->first(i, p); return i; } |
---|
[238] | 820 | |
---|
[158] | 821 | OutEdgeIt& next(OutEdgeIt& e) const { |
---|
| 822 | if (e.out_or_in) { |
---|
[303] | 823 | Node n=graph->tail(e.out); |
---|
| 824 | graph->next(e.out); |
---|
| 825 | if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } |
---|
[158] | 826 | } else { |
---|
[303] | 827 | graph->next(e.in); |
---|
[158] | 828 | } |
---|
| 829 | return e; |
---|
| 830 | } |
---|
| 831 | |
---|
[238] | 832 | EdgeIt& next(EdgeIt& e) const { |
---|
| 833 | //NodeIt v=tail(e); |
---|
[303] | 834 | graph->next(e.out); |
---|
| 835 | while (valid(e.v) && !graph->valid(e.out)) { |
---|
[238] | 836 | next(e.v); |
---|
[303] | 837 | if (valid(e.v)) graph->first(e.out, e.v); |
---|
[238] | 838 | } |
---|
| 839 | return e; |
---|
| 840 | } |
---|
[158] | 841 | |
---|
[305] | 842 | template<typename I> I& next(I &i) const { graph->next(i); return i; } |
---|
[265] | 843 | // template<typename I> I getNext(const I& i) const { return gw.getNext(i); } |
---|
[158] | 844 | |
---|
| 845 | template< typename It > It first() const { |
---|
[303] | 846 | It e; this->first(e); return e; } |
---|
[158] | 847 | |
---|
[174] | 848 | template< typename It > It first(const Node& v) const { |
---|
[303] | 849 | It e; this->first(e, v); return e; } |
---|
[158] | 850 | |
---|
[238] | 851 | // Node head(const Edge& e) const { return gw.head(e); } |
---|
| 852 | // Node tail(const Edge& e) const { return gw.tail(e); } |
---|
[158] | 853 | |
---|
[238] | 854 | // template<typename I> bool valid(const I& i) const |
---|
| 855 | // { return gw.valid(i); } |
---|
[158] | 856 | |
---|
[238] | 857 | // int nodeNum() const { return gw.nodeNum(); } |
---|
| 858 | // int edgeNum() const { return gw.edgeNum(); } |
---|
[158] | 859 | |
---|
[174] | 860 | // template<typename I> Node aNode(const I& e) const { |
---|
[158] | 861 | // return graph->aNode(e); } |
---|
[174] | 862 | // template<typename I> Node bNode(const I& e) const { |
---|
[158] | 863 | // return graph->bNode(e); } |
---|
[238] | 864 | |
---|
| 865 | Node aNode(const OutEdgeIt& e) const { |
---|
[303] | 866 | if (e.out_or_in) return graph->tail(e); else return graph->head(e); } |
---|
[238] | 867 | Node bNode(const OutEdgeIt& e) const { |
---|
[303] | 868 | if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
---|
[158] | 869 | |
---|
[238] | 870 | // Node addNode() const { return gw.addNode(); } |
---|
| 871 | |
---|
[231] | 872 | // FIXME: ez igy nem jo, mert nem |
---|
| 873 | // Edge addEdge(const Node& tail, const Node& head) const { |
---|
| 874 | // return graph->addEdge(tail, head); } |
---|
[158] | 875 | |
---|
[238] | 876 | // template<typename I> void erase(const I& i) const { gw.erase(i); } |
---|
[158] | 877 | |
---|
[238] | 878 | // void clear() const { gw.clear(); } |
---|
[158] | 879 | |
---|
[303] | 880 | // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
[238] | 881 | // public: |
---|
[303] | 882 | // NodeMap(const UndirGraphWrapper<Graph>& _G) : |
---|
| 883 | // Graph::NodeMap<T>(_G.gw) { } |
---|
| 884 | // NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : |
---|
| 885 | // Graph::NodeMap<T>(_G.gw, a) { } |
---|
[238] | 886 | // }; |
---|
[168] | 887 | |
---|
[238] | 888 | // template<typename T> class EdgeMap : |
---|
[303] | 889 | // public GraphWrapperSkeleton<Graph>::EdgeMap<T> { |
---|
[238] | 890 | // public: |
---|
[303] | 891 | // EdgeMap(const UndirGraphWrapper<Graph>& _G) : |
---|
| 892 | // GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { } |
---|
| 893 | // EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : |
---|
| 894 | // Graph::EdgeMap<T>(_G.gw, a) { } |
---|
[238] | 895 | // }; |
---|
| 896 | }; |
---|
[158] | 897 | |
---|
| 898 | |
---|
| 899 | |
---|
[236] | 900 | |
---|
| 901 | |
---|
[155] | 902 | // template<typename Graph> |
---|
| 903 | // class SymGraphWrapper |
---|
| 904 | // { |
---|
| 905 | // Graph* graph; |
---|
[76] | 906 | |
---|
[155] | 907 | // public: |
---|
[303] | 908 | // typedef Graph ParentGraph; |
---|
[155] | 909 | |
---|
[174] | 910 | // typedef typename Graph::Node Node; |
---|
| 911 | // typedef typename Graph::Edge Edge; |
---|
| 912 | |
---|
[155] | 913 | // typedef typename Graph::NodeIt NodeIt; |
---|
| 914 | |
---|
| 915 | // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon |
---|
| 916 | // //iranyitatlant, ami van |
---|
| 917 | // //mert csak 1 dolgot lehet be typedef-elni |
---|
| 918 | // typedef typename Graph::OutEdgeIt SymEdgeIt; |
---|
| 919 | // //typedef typename Graph::InEdgeIt SymEdgeIt; |
---|
| 920 | // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
[174] | 921 | // typedef typename Graph::EdgeIt EdgeIt; |
---|
[155] | 922 | |
---|
| 923 | // int nodeNum() const { return graph->nodeNum(); } |
---|
| 924 | // int edgeNum() const { return graph->edgeNum(); } |
---|
| 925 | |
---|
[212] | 926 | // template<typename I> I& first(I& i) const { return graph->first(i); } |
---|
| 927 | // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 928 | // return graph->first(i, p); } |
---|
[155] | 929 | // //template<typename I> I next(const I i); { return graph->goNext(i); } |
---|
| 930 | // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
---|
| 931 | |
---|
| 932 | // template< typename It > It first() const { |
---|
[212] | 933 | // It e; first(e); return e; } |
---|
[155] | 934 | |
---|
[174] | 935 | // template< typename It > It first(Node v) const { |
---|
[212] | 936 | // It e; first(e, v); return e; } |
---|
[155] | 937 | |
---|
[174] | 938 | // Node head(const Edge& e) const { return graph->head(e); } |
---|
| 939 | // Node tail(const Edge& e) const { return graph->tail(e); } |
---|
[155] | 940 | |
---|
[174] | 941 | // template<typename I> Node aNode(const I& e) const { |
---|
[155] | 942 | // return graph->aNode(e); } |
---|
[174] | 943 | // template<typename I> Node bNode(const I& e) const { |
---|
[155] | 944 | // return graph->bNode(e); } |
---|
| 945 | |
---|
| 946 | // //template<typename I> bool valid(const I i); |
---|
| 947 | // //{ return graph->valid(i); } |
---|
| 948 | |
---|
| 949 | // //template<typename I> void setInvalid(const I &i); |
---|
| 950 | // //{ return graph->setInvalid(i); } |
---|
| 951 | |
---|
[174] | 952 | // Node addNode() { return graph->addNode(); } |
---|
| 953 | // Edge addEdge(const Node& tail, const Node& head) { |
---|
[155] | 954 | // return graph->addEdge(tail, head); } |
---|
| 955 | |
---|
| 956 | // template<typename I> void erase(const I& i) { graph->erase(i); } |
---|
| 957 | |
---|
| 958 | // void clear() { graph->clear(); } |
---|
| 959 | |
---|
| 960 | // template<typename T> class NodeMap : public Graph::NodeMap<T> { }; |
---|
| 961 | // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; |
---|
| 962 | |
---|
| 963 | // void setGraph(Graph& _graph) { graph = &_graph; } |
---|
| 964 | // Graph& getGraph() { return (*graph); } |
---|
| 965 | |
---|
| 966 | // //SymGraphWrapper() : graph(0) { } |
---|
| 967 | // SymGraphWrapper(Graph& _graph) : graph(&_graph) { } |
---|
| 968 | // }; |
---|
| 969 | |
---|
| 970 | |
---|
[303] | 971 | template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
---|
[311] | 972 | class ResGraphWrapper : public GraphWrapper<Graph> { |
---|
[199] | 973 | protected: |
---|
[303] | 974 | typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
---|
| 975 | typedef typename Graph::InEdgeIt GraphInEdgeIt; |
---|
| 976 | typedef typename Graph::Edge GraphEdge; |
---|
[155] | 977 | FlowMap* flow; |
---|
| 978 | const CapacityMap* capacity; |
---|
| 979 | public: |
---|
[168] | 980 | |
---|
[303] | 981 | ResGraphWrapper(Graph& _graph, FlowMap& _flow, |
---|
[266] | 982 | const CapacityMap& _capacity) : |
---|
[303] | 983 | GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { } |
---|
[168] | 984 | |
---|
[174] | 985 | class Edge; |
---|
[155] | 986 | class OutEdgeIt; |
---|
[174] | 987 | friend class Edge; |
---|
[155] | 988 | friend class OutEdgeIt; |
---|
[76] | 989 | |
---|
[311] | 990 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 991 | typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
---|
[174] | 992 | class Edge { |
---|
[303] | 993 | friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
---|
[155] | 994 | protected: |
---|
[168] | 995 | bool out_or_in; //true, iff out |
---|
[303] | 996 | GraphOutEdgeIt out; |
---|
| 997 | GraphInEdgeIt in; |
---|
[155] | 998 | public: |
---|
[174] | 999 | Edge() : out_or_in(true) { } |
---|
| 1000 | Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
---|
[168] | 1001 | // bool valid() const { |
---|
| 1002 | // return out_or_in && out.valid() || in.valid(); } |
---|
[174] | 1003 | friend bool operator==(const Edge& u, const Edge& v) { |
---|
| 1004 | if (v.out_or_in) |
---|
| 1005 | return (u.out_or_in && u.out==v.out); |
---|
| 1006 | else |
---|
| 1007 | return (!u.out_or_in && u.in==v.in); |
---|
| 1008 | } |
---|
| 1009 | friend bool operator!=(const Edge& u, const Edge& v) { |
---|
| 1010 | if (v.out_or_in) |
---|
| 1011 | return (!u.out_or_in || u.out!=v.out); |
---|
| 1012 | else |
---|
| 1013 | return (u.out_or_in || u.in!=v.in); |
---|
| 1014 | } |
---|
[303] | 1015 | operator GraphEdge() const { |
---|
| 1016 | if (out_or_in) return(out); else return(in); |
---|
| 1017 | } |
---|
[155] | 1018 | }; |
---|
[174] | 1019 | class OutEdgeIt : public Edge { |
---|
[303] | 1020 | friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
---|
[155] | 1021 | public: |
---|
| 1022 | OutEdgeIt() { } |
---|
[168] | 1023 | //FIXME |
---|
[174] | 1024 | OutEdgeIt(const Edge& e) : Edge(e) { } |
---|
| 1025 | OutEdgeIt(const Invalid& i) : Edge(i) { } |
---|
[303] | 1026 | OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
---|
| 1027 | resG.graph->first(out, v); |
---|
| 1028 | while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
---|
| 1029 | if (!resG.graph->valid(out)) { |
---|
[155] | 1030 | out_or_in=0; |
---|
[303] | 1031 | resG.graph->first(in, v); |
---|
| 1032 | while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
---|
[155] | 1033 | } |
---|
| 1034 | } |
---|
[168] | 1035 | // public: |
---|
| 1036 | // OutEdgeIt& operator++() { |
---|
| 1037 | // if (out_or_in) { |
---|
[174] | 1038 | // Node v=/*resG->*/G->aNode(out); |
---|
[168] | 1039 | // ++out; |
---|
[269] | 1040 | // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } |
---|
[168] | 1041 | // if (!out.valid()) { |
---|
| 1042 | // out_or_in=0; |
---|
[212] | 1043 | // G->first(in, v); |
---|
[269] | 1044 | // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } |
---|
[168] | 1045 | // } |
---|
| 1046 | // } else { |
---|
| 1047 | // ++in; |
---|
[269] | 1048 | // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } |
---|
[168] | 1049 | // } |
---|
| 1050 | // return *this; |
---|
| 1051 | // } |
---|
[155] | 1052 | }; |
---|
| 1053 | |
---|
[263] | 1054 | //FIXME This is just for having InEdgeIt |
---|
[311] | 1055 | // class InEdgeIt : public Edge { }; |
---|
[263] | 1056 | |
---|
[174] | 1057 | class EdgeIt : public Edge { |
---|
[303] | 1058 | friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
---|
[265] | 1059 | NodeIt v; |
---|
[155] | 1060 | public: |
---|
[174] | 1061 | EdgeIt() { } |
---|
| 1062 | //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
---|
| 1063 | EdgeIt(const Invalid& i) : Edge(i) { } |
---|
[303] | 1064 | EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
---|
| 1065 | resG.graph->first(v); |
---|
| 1066 | if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; |
---|
| 1067 | while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
---|
| 1068 | while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
---|
| 1069 | resG.graph->next(v); |
---|
| 1070 | if (resG.graph->valid(v)) resG.graph->first(out, v); |
---|
| 1071 | while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
---|
[155] | 1072 | } |
---|
[303] | 1073 | if (!resG.graph->valid(out)) { |
---|
[155] | 1074 | out_or_in=0; |
---|
[303] | 1075 | resG.graph->first(v); |
---|
| 1076 | if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; |
---|
| 1077 | while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
---|
| 1078 | while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
---|
| 1079 | resG.graph->next(v); |
---|
| 1080 | if (resG.graph->valid(v)) resG.graph->first(in, v); |
---|
| 1081 | while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
---|
[155] | 1082 | } |
---|
| 1083 | } |
---|
| 1084 | } |
---|
[174] | 1085 | // EdgeIt& operator++() { |
---|
[168] | 1086 | // if (out_or_in) { |
---|
| 1087 | // ++out; |
---|
[269] | 1088 | // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
---|
[168] | 1089 | // while (v.valid() && !out.valid()) { |
---|
| 1090 | // ++v; |
---|
[212] | 1091 | // if (v.valid()) G->first(out, v); |
---|
[269] | 1092 | // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
---|
[168] | 1093 | // } |
---|
| 1094 | // if (!out.valid()) { |
---|
| 1095 | // out_or_in=0; |
---|
[212] | 1096 | // G->first(v); |
---|
[303] | 1097 | // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); |
---|
[269] | 1098 | // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
---|
[168] | 1099 | // while (v.valid() && !in.valid()) { |
---|
| 1100 | // ++v; |
---|
[212] | 1101 | // if (v.valid()) G->first(in, v); |
---|
[269] | 1102 | // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
---|
[168] | 1103 | // } |
---|
| 1104 | // } |
---|
| 1105 | // } else { |
---|
| 1106 | // ++in; |
---|
[269] | 1107 | // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
---|
[168] | 1108 | // while (v.valid() && !in.valid()) { |
---|
| 1109 | // ++v; |
---|
[212] | 1110 | // if (v.valid()) G->first(in, v); |
---|
[269] | 1111 | // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
---|
[168] | 1112 | // } |
---|
| 1113 | // } |
---|
| 1114 | // return *this; |
---|
| 1115 | // } |
---|
[155] | 1116 | }; |
---|
| 1117 | |
---|
[311] | 1118 | NodeIt& first(NodeIt& i) const { |
---|
| 1119 | i=NodeIt(*this); |
---|
| 1120 | return i; |
---|
[155] | 1121 | } |
---|
[311] | 1122 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 1123 | i=OutEdgeIt(*this, p); |
---|
| 1124 | return i; |
---|
| 1125 | } |
---|
| 1126 | //FIXME Not yet implemented |
---|
| 1127 | //InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 1128 | //i=InEdgeIt(*this, p); |
---|
| 1129 | // return i; |
---|
| 1130 | //} |
---|
[212] | 1131 | EdgeIt& first(EdgeIt& e) const { |
---|
[174] | 1132 | e=EdgeIt(*this); |
---|
| 1133 | return e; |
---|
[155] | 1134 | } |
---|
| 1135 | |
---|
[305] | 1136 | NodeIt& next(NodeIt& n) const { graph->next(n); return n; } |
---|
[155] | 1137 | OutEdgeIt& next(OutEdgeIt& e) const { |
---|
| 1138 | if (e.out_or_in) { |
---|
[303] | 1139 | Node v=graph->aNode(e.out); |
---|
| 1140 | graph->next(e.out); |
---|
| 1141 | while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
---|
| 1142 | if (!graph->valid(e.out)) { |
---|
[155] | 1143 | e.out_or_in=0; |
---|
[303] | 1144 | graph->first(e.in, v); |
---|
| 1145 | while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
---|
[155] | 1146 | } |
---|
| 1147 | } else { |
---|
[303] | 1148 | graph->next(e.in); |
---|
| 1149 | while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
---|
[155] | 1150 | } |
---|
| 1151 | return e; |
---|
| 1152 | } |
---|
[311] | 1153 | //FIXME Not yet implemented |
---|
| 1154 | //InEdgeIt& next(InEdgeIt& e) const { |
---|
| 1155 | // return e; |
---|
| 1156 | //} |
---|
[174] | 1157 | EdgeIt& next(EdgeIt& e) const { |
---|
[155] | 1158 | if (e.out_or_in) { |
---|
[303] | 1159 | graph->next(e.out); |
---|
| 1160 | while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
---|
| 1161 | while (graph->valid(e.v) && !graph->valid(e.out)) { |
---|
| 1162 | graph->next(e.v); |
---|
| 1163 | if (graph->valid(e.v)) graph->first(e.out, e.v); |
---|
| 1164 | while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
---|
[155] | 1165 | } |
---|
[303] | 1166 | if (!graph->valid(e.out)) { |
---|
[155] | 1167 | e.out_or_in=0; |
---|
[303] | 1168 | graph->first(e.v); |
---|
| 1169 | if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; |
---|
| 1170 | while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
---|
| 1171 | while (graph->valid(e.v) && !graph->valid(e.in)) { |
---|
| 1172 | graph->next(e.v); |
---|
| 1173 | if (graph->valid(e.v)) graph->first(e.in, e.v); |
---|
| 1174 | while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
---|
[155] | 1175 | } |
---|
| 1176 | } |
---|
| 1177 | } else { |
---|
[303] | 1178 | graph->next(e.in); |
---|
| 1179 | while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
---|
| 1180 | while (graph->valid(e.v) && !graph->valid(e.in)) { |
---|
| 1181 | graph->next(e.v); |
---|
| 1182 | if (graph->valid(e.v)) graph->first(e.in, e.v); |
---|
| 1183 | while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
---|
[155] | 1184 | } |
---|
| 1185 | } |
---|
| 1186 | return e; |
---|
| 1187 | } |
---|
[76] | 1188 | |
---|
| 1189 | |
---|
[155] | 1190 | template< typename It > |
---|
| 1191 | It first() const { |
---|
| 1192 | It e; |
---|
[212] | 1193 | first(e); |
---|
[155] | 1194 | return e; |
---|
| 1195 | } |
---|
[76] | 1196 | |
---|
[155] | 1197 | template< typename It > |
---|
[174] | 1198 | It first(Node v) const { |
---|
[155] | 1199 | It e; |
---|
[212] | 1200 | first(e, v); |
---|
[155] | 1201 | return e; |
---|
| 1202 | } |
---|
[76] | 1203 | |
---|
[174] | 1204 | Node tail(Edge e) const { |
---|
[303] | 1205 | return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
---|
[174] | 1206 | Node head(Edge e) const { |
---|
[303] | 1207 | return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
---|
[76] | 1208 | |
---|
[174] | 1209 | Node aNode(OutEdgeIt e) const { |
---|
[303] | 1210 | return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
---|
[174] | 1211 | Node bNode(OutEdgeIt e) const { |
---|
[303] | 1212 | return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
---|
[76] | 1213 | |
---|
[303] | 1214 | int nodeNum() const { return graph->nodeNum(); } |
---|
[263] | 1215 | //FIXME |
---|
[303] | 1216 | //int edgeNum() const { return graph->edgeNum(); } |
---|
[263] | 1217 | |
---|
| 1218 | |
---|
[303] | 1219 | int id(Node v) const { return graph->id(v); } |
---|
[155] | 1220 | |
---|
[303] | 1221 | bool valid(Node n) const { return graph->valid(n); } |
---|
[174] | 1222 | bool valid(Edge e) const { |
---|
[303] | 1223 | return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } |
---|
[155] | 1224 | |
---|
[174] | 1225 | void augment(const Edge& e, Number a) const { |
---|
[168] | 1226 | if (e.out_or_in) |
---|
[303] | 1227 | // flow->set(e.out, flow->get(e.out)+a); |
---|
| 1228 | flow->set(e.out, (*flow)[e.out]+a); |
---|
[168] | 1229 | else |
---|
[303] | 1230 | // flow->set(e.in, flow->get(e.in)-a); |
---|
| 1231 | flow->set(e.in, (*flow)[e.in]-a); |
---|
[168] | 1232 | } |
---|
| 1233 | |
---|
[269] | 1234 | Number resCap(const Edge& e) const { |
---|
[168] | 1235 | if (e.out_or_in) |
---|
[303] | 1236 | // return (capacity->get(e.out)-flow->get(e.out)); |
---|
| 1237 | return ((*capacity)[e.out]-(*flow)[e.out]); |
---|
[168] | 1238 | else |
---|
[303] | 1239 | // return (flow->get(e.in)); |
---|
| 1240 | return ((*flow)[e.in]); |
---|
[168] | 1241 | } |
---|
| 1242 | |
---|
[303] | 1243 | Number resCap(GraphOutEdgeIt out) const { |
---|
| 1244 | // return (capacity->get(out)-flow->get(out)); |
---|
| 1245 | return ((*capacity)[out]-(*flow)[out]); |
---|
[168] | 1246 | } |
---|
| 1247 | |
---|
[303] | 1248 | Number resCap(GraphInEdgeIt in) const { |
---|
| 1249 | // return (flow->get(in)); |
---|
| 1250 | return ((*flow)[in]); |
---|
[168] | 1251 | } |
---|
| 1252 | |
---|
[303] | 1253 | // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
[266] | 1254 | // public: |
---|
[303] | 1255 | // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) |
---|
| 1256 | // : Graph::NodeMap<T>(_G.gw) { } |
---|
| 1257 | // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, |
---|
| 1258 | // T a) : Graph::NodeMap<T>(_G.gw, a) { } |
---|
[266] | 1259 | // }; |
---|
[155] | 1260 | |
---|
| 1261 | // template <typename T> |
---|
| 1262 | // class NodeMap { |
---|
| 1263 | // typename Graph::NodeMap<T> node_map; |
---|
| 1264 | // public: |
---|
[174] | 1265 | // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { } |
---|
| 1266 | // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { } |
---|
| 1267 | // void set(Node nit, T a) { node_map.set(nit, a); } |
---|
| 1268 | // T get(Node nit) const { return node_map.get(nit); } |
---|
[155] | 1269 | // }; |
---|
| 1270 | |
---|
| 1271 | template <typename T> |
---|
| 1272 | class EdgeMap { |
---|
[303] | 1273 | typename Graph::EdgeMap<T> forward_map, backward_map; |
---|
[155] | 1274 | public: |
---|
[303] | 1275 | EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
---|
| 1276 | EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
---|
[174] | 1277 | void set(Edge e, T a) { |
---|
[155] | 1278 | if (e.out_or_in) |
---|
| 1279 | forward_map.set(e.out, a); |
---|
| 1280 | else |
---|
| 1281 | backward_map.set(e.in, a); |
---|
| 1282 | } |
---|
[303] | 1283 | T operator[](Edge e) const { |
---|
[155] | 1284 | if (e.out_or_in) |
---|
[303] | 1285 | return forward_map[e.out]; |
---|
[155] | 1286 | else |
---|
[303] | 1287 | return backward_map[e.in]; |
---|
[155] | 1288 | } |
---|
[303] | 1289 | // T get(Edge e) const { |
---|
| 1290 | // if (e.out_or_in) |
---|
| 1291 | // return forward_map.get(e.out); |
---|
| 1292 | // else |
---|
| 1293 | // return backward_map.get(e.in); |
---|
| 1294 | // } |
---|
[155] | 1295 | }; |
---|
[168] | 1296 | }; |
---|
| 1297 | |
---|
[303] | 1298 | //ErasingFirstGraphWrapper for blocking flows |
---|
| 1299 | template<typename Graph, typename FirstOutEdgesMap> |
---|
| 1300 | class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
---|
[269] | 1301 | protected: |
---|
| 1302 | FirstOutEdgesMap* first_out_edges; |
---|
| 1303 | public: |
---|
[303] | 1304 | ErasingFirstGraphWrapper(Graph& _graph, |
---|
| 1305 | FirstOutEdgesMap& _first_out_edges) : |
---|
| 1306 | GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
---|
[269] | 1307 | |
---|
[311] | 1308 | typedef typename Graph::Node Node; |
---|
| 1309 | class NodeIt : public Graph::NodeIt { |
---|
| 1310 | public: |
---|
| 1311 | NodeIt() { } |
---|
| 1312 | NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
---|
| 1313 | NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
---|
| 1314 | NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
---|
| 1315 | Graph::NodeIt(*(_G.graph)) { } |
---|
| 1316 | }; |
---|
| 1317 | typedef typename Graph::Edge Edge; |
---|
| 1318 | class OutEdgeIt : public Graph::OutEdgeIt { |
---|
| 1319 | public: |
---|
| 1320 | OutEdgeIt() { } |
---|
| 1321 | OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
---|
| 1322 | OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
---|
| 1323 | OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
---|
| 1324 | const Node& n) : |
---|
| 1325 | Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } |
---|
| 1326 | }; |
---|
| 1327 | class InEdgeIt : public Graph::InEdgeIt { |
---|
| 1328 | public: |
---|
| 1329 | InEdgeIt() { } |
---|
| 1330 | InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
---|
| 1331 | InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
---|
| 1332 | InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
---|
| 1333 | const Node& n) : |
---|
| 1334 | Graph::InEdgeIt(*(_G.graph), n) { } |
---|
| 1335 | }; |
---|
| 1336 | //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 1337 | class EdgeIt : public Graph::EdgeIt { |
---|
| 1338 | public: |
---|
| 1339 | EdgeIt() { } |
---|
| 1340 | EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
---|
| 1341 | EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
---|
| 1342 | EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
---|
| 1343 | Graph::EdgeIt(*(_G.graph)) { } |
---|
| 1344 | }; |
---|
| 1345 | |
---|
| 1346 | NodeIt& first(NodeIt& i) const { |
---|
| 1347 | i=NodeIt(*this); |
---|
[269] | 1348 | return i; |
---|
| 1349 | } |
---|
[311] | 1350 | OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { |
---|
| 1351 | i=OutEdgeIt(*this, n); |
---|
| 1352 | // i=(*first_out_edges)[n]; |
---|
[269] | 1353 | return i; |
---|
| 1354 | } |
---|
[311] | 1355 | InEdgeIt& first(InEdgeIt& i, const Node& n) const { |
---|
| 1356 | i=InEdgeIt(*this, n); |
---|
| 1357 | return i; |
---|
| 1358 | } |
---|
| 1359 | EdgeIt& first(EdgeIt& i) const { |
---|
| 1360 | i=EdgeIt(*this); |
---|
| 1361 | return i; |
---|
| 1362 | } |
---|
| 1363 | |
---|
| 1364 | // template<typename I> I& first(I& i) const { |
---|
| 1365 | // graph->first(i); |
---|
| 1366 | // return i; |
---|
| 1367 | // } |
---|
| 1368 | // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
---|
| 1369 | // // e=first_out_edges->get(n); |
---|
| 1370 | // e=(*first_out_edges)[n]; |
---|
| 1371 | // return e; |
---|
| 1372 | // } |
---|
| 1373 | // template<typename I, typename P> I& first(I& i, const P& p) const { |
---|
| 1374 | // graph->first(i, p); |
---|
| 1375 | // return i; |
---|
| 1376 | // } |
---|
[269] | 1377 | |
---|
| 1378 | //template<typename I> I getNext(const I& i) const { |
---|
| 1379 | // return gw.getNext(i); |
---|
| 1380 | //} |
---|
[311] | 1381 | |
---|
| 1382 | |
---|
| 1383 | NodeIt& next(NodeIt& i) const { |
---|
[303] | 1384 | graph->next(i); |
---|
[269] | 1385 | return i; |
---|
| 1386 | } |
---|
[311] | 1387 | OutEdgeIt& next(OutEdgeIt& i) const { |
---|
| 1388 | graph->next(i); |
---|
| 1389 | return i; |
---|
| 1390 | } |
---|
| 1391 | InEdgeIt& next(InEdgeIt& i) const { |
---|
| 1392 | graph->next(i); |
---|
| 1393 | return i; |
---|
| 1394 | } |
---|
| 1395 | EdgeIt& next(EdgeIt& i) const { |
---|
| 1396 | graph->next(i); |
---|
| 1397 | return i; |
---|
| 1398 | } |
---|
| 1399 | |
---|
| 1400 | // template<typename I> I& next(I &i) const { |
---|
| 1401 | // graph->next(i); |
---|
| 1402 | // return i; |
---|
| 1403 | // } |
---|
[269] | 1404 | |
---|
| 1405 | template< typename It > It first() const { |
---|
| 1406 | It e; this->first(e); return e; } |
---|
| 1407 | |
---|
| 1408 | template< typename It > It first(const Node& v) const { |
---|
| 1409 | It e; this->first(e, v); return e; } |
---|
| 1410 | |
---|
| 1411 | void erase(const OutEdgeIt& e) const { |
---|
| 1412 | OutEdgeIt f=e; |
---|
| 1413 | this->next(f); |
---|
| 1414 | first_out_edges->set(this->tail(e), f); |
---|
| 1415 | } |
---|
| 1416 | }; |
---|
| 1417 | |
---|
[148] | 1418 | // // FIXME: comparison should be made better!!! |
---|
| 1419 | // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap> |
---|
| 1420 | // class ResGraphWrapper |
---|
| 1421 | // { |
---|
| 1422 | // Graph* graph; |
---|
[76] | 1423 | |
---|
[148] | 1424 | // public: |
---|
[303] | 1425 | // typedef Graph ParentGraph; |
---|
[76] | 1426 | |
---|
[174] | 1427 | // typedef typename Graph::Node Node; |
---|
| 1428 | // typedef typename Graph::Edge Edge; |
---|
| 1429 | |
---|
[148] | 1430 | // typedef typename Graph::NodeIt NodeIt; |
---|
[76] | 1431 | |
---|
[148] | 1432 | // class OutEdgeIt { |
---|
| 1433 | // public: |
---|
[174] | 1434 | // //Graph::Node n; |
---|
[148] | 1435 | // bool out_or_in; |
---|
| 1436 | // typename Graph::OutEdgeIt o; |
---|
| 1437 | // typename Graph::InEdgeIt i; |
---|
| 1438 | // }; |
---|
| 1439 | // class InEdgeIt { |
---|
| 1440 | // public: |
---|
[174] | 1441 | // //Graph::Node n; |
---|
[148] | 1442 | // bool out_or_in; |
---|
| 1443 | // typename Graph::OutEdgeIt o; |
---|
| 1444 | // typename Graph::InEdgeIt i; |
---|
| 1445 | // }; |
---|
| 1446 | // typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
[174] | 1447 | // typedef typename Graph::EdgeIt EdgeIt; |
---|
[76] | 1448 | |
---|
[259] | 1449 | // int nodeNum() const { return gw.nodeNum(); } |
---|
| 1450 | // int edgeNum() const { return gw.edgeNum(); } |
---|
[76] | 1451 | |
---|
[259] | 1452 | // Node& first(Node& n) const { return gw.first(n); } |
---|
[76] | 1453 | |
---|
[174] | 1454 | // // Edge and SymEdge is missing!!!! |
---|
| 1455 | // // Edge <-> In/OutEdgeIt conversion is missing!!!! |
---|
[76] | 1456 | |
---|
[148] | 1457 | // //FIXME |
---|
[212] | 1458 | // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const |
---|
[148] | 1459 | // { |
---|
| 1460 | // e.n=n; |
---|
[259] | 1461 | // gw.first(e.o,n); |
---|
| 1462 | // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
---|
| 1463 | // gw.goNext(e.o); |
---|
| 1464 | // if(!gw.valid(e.o)) { |
---|
| 1465 | // gw.first(e.i,n); |
---|
| 1466 | // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
---|
| 1467 | // gw.goNext(e.i); |
---|
[148] | 1468 | // } |
---|
| 1469 | // return e; |
---|
| 1470 | // } |
---|
| 1471 | // /* |
---|
| 1472 | // OutEdgeIt &goNext(OutEdgeIt &e) |
---|
| 1473 | // { |
---|
[259] | 1474 | // if(gw.valid(e.o)) { |
---|
| 1475 | // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
---|
| 1476 | // gw.goNext(e.o); |
---|
| 1477 | // if(gw.valid(e.o)) return e; |
---|
| 1478 | // else gw.first(e.i,e.n); |
---|
[148] | 1479 | // } |
---|
| 1480 | // else { |
---|
[259] | 1481 | // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
---|
| 1482 | // gw.goNext(e.i); |
---|
[148] | 1483 | // return e; |
---|
| 1484 | // } |
---|
| 1485 | // } |
---|
| 1486 | // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} |
---|
| 1487 | // */ |
---|
[259] | 1488 | // //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);} |
---|
[76] | 1489 | |
---|
[148] | 1490 | // //FIXME |
---|
[212] | 1491 | // InEdgeIt& first(InEdgeIt& e, const Node& n) const |
---|
[148] | 1492 | // { |
---|
| 1493 | // e.n=n; |
---|
[259] | 1494 | // gw.first(e.i,n); |
---|
| 1495 | // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
---|
| 1496 | // gw.goNext(e.i); |
---|
| 1497 | // if(!gw.valid(e.i)) { |
---|
| 1498 | // gw.first(e.o,n); |
---|
| 1499 | // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
---|
| 1500 | // gw.goNext(e.o); |
---|
[148] | 1501 | // } |
---|
| 1502 | // return e; |
---|
| 1503 | // } |
---|
| 1504 | // /* |
---|
| 1505 | // InEdgeIt &goNext(InEdgeIt &e) |
---|
| 1506 | // { |
---|
[259] | 1507 | // if(gw.valid(e.i)) { |
---|
| 1508 | // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
---|
| 1509 | // gw.goNext(e.i); |
---|
| 1510 | // if(gw.valid(e.i)) return e; |
---|
| 1511 | // else gw.first(e.o,e.n); |
---|
[148] | 1512 | // } |
---|
| 1513 | // else { |
---|
[259] | 1514 | // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
---|
| 1515 | // gw.goNext(e.o); |
---|
[148] | 1516 | // return e; |
---|
| 1517 | // } |
---|
| 1518 | // } |
---|
| 1519 | // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} |
---|
| 1520 | // */ |
---|
[259] | 1521 | // //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);} |
---|
[76] | 1522 | |
---|
[259] | 1523 | // //template<typename I> I &goNext(I &i); { return gw.goNext(i); } |
---|
| 1524 | // //template<typename I> I next(const I i); { return gw.goNext(i); } |
---|
[76] | 1525 | |
---|
[148] | 1526 | // template< typename It > It first() const { |
---|
[212] | 1527 | // It e; first(e); return e; } |
---|
[76] | 1528 | |
---|
[174] | 1529 | // template< typename It > It first(Node v) const { |
---|
[212] | 1530 | // It e; first(e, v); return e; } |
---|
[76] | 1531 | |
---|
[259] | 1532 | // Node head(const Edge& e) const { return gw.head(e); } |
---|
| 1533 | // Node tail(const Edge& e) const { return gw.tail(e); } |
---|
[76] | 1534 | |
---|
[174] | 1535 | // template<typename I> Node aNode(const I& e) const { |
---|
[259] | 1536 | // return gw.aNode(e); } |
---|
[174] | 1537 | // template<typename I> Node bNode(const I& e) const { |
---|
[259] | 1538 | // return gw.bNode(e); } |
---|
[76] | 1539 | |
---|
[148] | 1540 | // //template<typename I> bool valid(const I i); |
---|
[259] | 1541 | // //{ return gw.valid(i); } |
---|
[76] | 1542 | |
---|
[148] | 1543 | // //template<typename I> void setInvalid(const I &i); |
---|
[259] | 1544 | // //{ return gw.setInvalid(i); } |
---|
[76] | 1545 | |
---|
[259] | 1546 | // Node addNode() { return gw.addNode(); } |
---|
[174] | 1547 | // Edge addEdge(const Node& tail, const Node& head) { |
---|
[259] | 1548 | // return gw.addEdge(tail, head); } |
---|
[76] | 1549 | |
---|
[259] | 1550 | // template<typename I> void erase(const I& i) { gw.erase(i); } |
---|
[76] | 1551 | |
---|
[259] | 1552 | // void clear() { gw.clear(); } |
---|
[76] | 1553 | |
---|
[148] | 1554 | // template<typename S> class NodeMap : public Graph::NodeMap<S> { }; |
---|
| 1555 | // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { }; |
---|
[76] | 1556 | |
---|
[148] | 1557 | // void setGraph(Graph& _graph) { graph = &_graph; } |
---|
| 1558 | // Graph& getGraph() { return (*graph); } |
---|
[76] | 1559 | |
---|
[148] | 1560 | // //ResGraphWrapper() : graph(0) { } |
---|
| 1561 | // ResGraphWrapper(Graph& _graph) : graph(&_graph) { } |
---|
| 1562 | // }; |
---|
[76] | 1563 | |
---|
[105] | 1564 | } //namespace hugo |
---|
[76] | 1565 | |
---|
[259] | 1566 | #endif //HUGO_GRAPH_WRAPPER_H |
---|
[76] | 1567 | |
---|