[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 | |
---|
[335] | 9 | /// Graph wrappers |
---|
| 10 | |
---|
[344] | 11 | /// A main parts of HUGOlib are the different graph structures, |
---|
[335] | 12 | /// generic graph algorithms, graph concepts which couple these, and |
---|
| 13 | /// graph wrappers. While the previous ones are more or less clear, the |
---|
| 14 | /// latter notion needs further explanation. |
---|
| 15 | /// Graph wrappers are graph classes which serve for considering graph |
---|
[344] | 16 | /// structures in different ways. A short example makes the notion much |
---|
| 17 | /// clearer. |
---|
| 18 | /// Suppose that we have an instance \c g of a directed graph |
---|
| 19 | /// type say \c ListGraph and an algorithm |
---|
[335] | 20 | /// \code template<typename Graph> int algorithm(const Graph&); \endcode |
---|
[344] | 21 | /// is needed to run on the reversely oriented graph. |
---|
| 22 | /// It may be expensive (in time or in memory usage) to copy |
---|
| 23 | /// \c g with the reverse orientation. |
---|
[335] | 24 | /// Thus, a wrapper class |
---|
| 25 | /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
---|
| 26 | /// The code looks as follows |
---|
| 27 | /// \code |
---|
| 28 | /// ListGraph g; |
---|
| 29 | /// RevGraphWrapper<ListGraph> rgw(g); |
---|
| 30 | /// int result=algorithm(rgw); |
---|
| 31 | /// \endcode |
---|
[344] | 32 | /// After running the algorithm, the original graph \c g |
---|
| 33 | /// remains untouched. Thus the graph wrapper used above is to consider the |
---|
| 34 | /// original graph with reverse orientation. |
---|
[335] | 35 | /// This techniques gives rise to an elegant code, and |
---|
| 36 | /// based on stable graph wrappers, complex algorithms can be |
---|
| 37 | /// implemented easily. |
---|
| 38 | /// In flow, circulation and bipartite matching problems, the residual |
---|
[344] | 39 | /// graph is of particular importance. Combining a wrapper implementing |
---|
| 40 | /// this, shortest path algorithms and minimum mean cycle algorithms, |
---|
[335] | 41 | /// a range of weighted and cardinality optimization algorithms can be |
---|
| 42 | /// obtained. For lack of space, for other examples, |
---|
[344] | 43 | /// the interested user is referred to the detailed documentation of graph |
---|
[335] | 44 | /// wrappers. |
---|
[344] | 45 | /// The behavior of graph wrappers can be very different. Some of them keep |
---|
[335] | 46 | /// capabilities of the original graph while in other cases this would be |
---|
[344] | 47 | /// meaningless. This means that the concepts that they are a model of depend |
---|
[335] | 48 | /// on the graph wrapper, and the wrapped graph(s). |
---|
[344] | 49 | /// If an edge of \c rgw is deleted, this is carried out by |
---|
| 50 | /// deleting the corresponding edge of \c g. But for a residual |
---|
[335] | 51 | /// graph, this operation has no sense. |
---|
| 52 | /// Let we stand one more example here to simplify your work. |
---|
| 53 | /// wrapper class |
---|
| 54 | /// \code template<typename Graph> class RevGraphWrapper; \endcode |
---|
| 55 | /// has constructor |
---|
[344] | 56 | /// <tt> RevGraphWrapper(Graph& _g)</tt>. |
---|
[335] | 57 | /// This means that in a situation, |
---|
[344] | 58 | /// when a <tt> const ListGraph& </tt> reference to a graph is given, |
---|
| 59 | /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
---|
[335] | 60 | /// \code |
---|
| 61 | /// int algorithm1(const ListGraph& g) { |
---|
| 62 | /// RevGraphWrapper<const ListGraph> rgw(g); |
---|
| 63 | /// return algorithm2(rgw); |
---|
| 64 | /// } |
---|
| 65 | /// \endcode |
---|
[303] | 66 | template<typename Graph> |
---|
| 67 | class GraphWrapper { |
---|
[212] | 68 | protected: |
---|
[303] | 69 | Graph* graph; |
---|
[212] | 70 | |
---|
| 71 | public: |
---|
[311] | 72 | typedef Graph BaseGraph; |
---|
[303] | 73 | typedef Graph ParentGraph; |
---|
[212] | 74 | |
---|
[303] | 75 | // GraphWrapper() : graph(0) { } |
---|
| 76 | GraphWrapper(Graph& _graph) : graph(&_graph) { } |
---|
| 77 | // void setGraph(Graph& _graph) { graph=&_graph; } |
---|
| 78 | // Graph& getGraph() const { return *graph; } |
---|
| 79 | |
---|
[317] | 80 | // typedef typename Graph::Node Node; |
---|
| 81 | class Node : public Graph::Node { |
---|
| 82 | friend class GraphWrapper<Graph>; |
---|
[265] | 83 | public: |
---|
[317] | 84 | Node() { } |
---|
| 85 | Node(const typename Graph::Node& _n) : Graph::Node(_n) { } |
---|
| 86 | Node(const Invalid& i) : Graph::Node(i) { } |
---|
| 87 | }; |
---|
| 88 | class NodeIt { |
---|
| 89 | friend class GraphWrapper<Graph>; |
---|
| 90 | typename Graph::NodeIt n; |
---|
| 91 | public: |
---|
[265] | 92 | NodeIt() { } |
---|
[317] | 93 | NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
---|
| 94 | NodeIt(const Invalid& i) : n(i) { } |
---|
| 95 | NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { } |
---|
| 96 | operator Node() const { return Node(typename Graph::Node(n)); } |
---|
[265] | 97 | }; |
---|
[317] | 98 | // typedef typename Graph::Edge Edge; |
---|
| 99 | class Edge : public Graph::Edge { |
---|
| 100 | friend class GraphWrapper<Graph>; |
---|
| 101 | public: |
---|
| 102 | Edge() { } |
---|
| 103 | Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } |
---|
| 104 | Edge(const Invalid& i) : Graph::Edge(i) { } |
---|
| 105 | }; |
---|
| 106 | class OutEdgeIt { |
---|
| 107 | friend class GraphWrapper<Graph>; |
---|
| 108 | typename Graph::OutEdgeIt e; |
---|
[265] | 109 | public: |
---|
| 110 | OutEdgeIt() { } |
---|
[317] | 111 | OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
---|
| 112 | OutEdgeIt(const Invalid& i) : e(i) { } |
---|
| 113 | OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : |
---|
| 114 | e(*(_G.graph), typename Graph::Node(_n)) { } |
---|
| 115 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[265] | 116 | }; |
---|
[317] | 117 | class InEdgeIt { |
---|
| 118 | friend class GraphWrapper<Graph>; |
---|
| 119 | typename Graph::InEdgeIt e; |
---|
[265] | 120 | public: |
---|
| 121 | InEdgeIt() { } |
---|
[317] | 122 | InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
---|
| 123 | InEdgeIt(const Invalid& i) : e(i) { } |
---|
| 124 | InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : |
---|
| 125 | e(*(_G.graph), typename Graph::Node(_n)) { } |
---|
| 126 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[265] | 127 | }; |
---|
[303] | 128 | //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
[317] | 129 | class EdgeIt { |
---|
| 130 | friend class GraphWrapper<Graph>; |
---|
| 131 | typename Graph::EdgeIt e; |
---|
[265] | 132 | public: |
---|
| 133 | EdgeIt() { } |
---|
[317] | 134 | EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
---|
| 135 | EdgeIt(const Invalid& i) : e(i) { } |
---|
| 136 | EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { } |
---|
| 137 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[265] | 138 | }; |
---|
[303] | 139 | |
---|
| 140 | NodeIt& first(NodeIt& i) const { |
---|
[317] | 141 | i=NodeIt(*this); return i; |
---|
[265] | 142 | } |
---|
[303] | 143 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
[317] | 144 | i=OutEdgeIt(*this, p); return i; |
---|
[303] | 145 | } |
---|
| 146 | InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
[317] | 147 | i=InEdgeIt(*this, p); return i; |
---|
[303] | 148 | } |
---|
[311] | 149 | EdgeIt& first(EdgeIt& i) const { |
---|
[317] | 150 | i=EdgeIt(*this); return i; |
---|
[311] | 151 | } |
---|
[338] | 152 | |
---|
[317] | 153 | NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
---|
| 154 | OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 155 | InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 156 | EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
---|
[212] | 157 | |
---|
[317] | 158 | Node head(const Edge& e) const { |
---|
| 159 | return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
---|
| 160 | Node tail(const Edge& e) const { |
---|
| 161 | return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
---|
[212] | 162 | |
---|
[317] | 163 | bool valid(const Node& n) const { |
---|
| 164 | return graph->valid(static_cast<typename Graph::Node>(n)); } |
---|
| 165 | bool valid(const Edge& e) const { |
---|
| 166 | return graph->valid(static_cast<typename Graph::Edge>(e)); } |
---|
[212] | 167 | |
---|
[303] | 168 | int nodeNum() const { return graph->nodeNum(); } |
---|
| 169 | int edgeNum() const { return graph->edgeNum(); } |
---|
[212] | 170 | |
---|
[317] | 171 | Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 172 | Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 173 | Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 174 | Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
[212] | 175 | |
---|
[317] | 176 | Node addNode() const { return Node(graph->addNode()); } |
---|
[212] | 177 | Edge addEdge(const Node& tail, const Node& head) const { |
---|
[317] | 178 | return Edge(graph->addEdge(tail, head)); } |
---|
| 179 | |
---|
| 180 | void erase(const Node& i) const { graph->erase(i); } |
---|
| 181 | void erase(const Edge& i) const { graph->erase(i); } |
---|
[212] | 182 | |
---|
[303] | 183 | void clear() const { graph->clear(); } |
---|
[212] | 184 | |
---|
[303] | 185 | template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
[212] | 186 | public: |
---|
[303] | 187 | NodeMap(const GraphWrapper<Graph>& _G) : |
---|
| 188 | Graph::NodeMap<T>(*(_G.graph)) { } |
---|
| 189 | NodeMap(const GraphWrapper<Graph>& _G, T a) : |
---|
| 190 | Graph::NodeMap<T>(*(_G.graph), a) { } |
---|
[212] | 191 | }; |
---|
| 192 | |
---|
[303] | 193 | template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
---|
[212] | 194 | public: |
---|
[303] | 195 | EdgeMap(const GraphWrapper<Graph>& _G) : |
---|
| 196 | Graph::EdgeMap<T>(*(_G.graph)) { } |
---|
| 197 | EdgeMap(const GraphWrapper<Graph>& _G, T a) : |
---|
| 198 | Graph::EdgeMap<T>(*(_G.graph), a) { } |
---|
[212] | 199 | }; |
---|
| 200 | }; |
---|
| 201 | |
---|
[338] | 202 | /// A graph wrapper which reverses the orientation of the edges. |
---|
[303] | 203 | |
---|
[338] | 204 | /// A graph wrapper which reverses the orientation of the edges. |
---|
[303] | 205 | template<typename Graph> |
---|
| 206 | class RevGraphWrapper : public GraphWrapper<Graph> { |
---|
[230] | 207 | public: |
---|
[338] | 208 | |
---|
| 209 | RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
---|
| 210 | |
---|
[303] | 211 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 212 | typedef typename GraphWrapper<Graph>::Edge Edge; |
---|
| 213 | //If Graph::OutEdgeIt is not defined |
---|
[279] | 214 | //and we do not want to use RevGraphWrapper::InEdgeIt, |
---|
[338] | 215 | //the typdef techinque does not work. |
---|
| 216 | //Unfortunately all the typedefs are instantiated in templates. |
---|
| 217 | //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; |
---|
| 218 | //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; |
---|
[237] | 219 | |
---|
[338] | 220 | class OutEdgeIt { |
---|
| 221 | friend class GraphWrapper<Graph>; |
---|
| 222 | friend class RevGraphWrapper<Graph>; |
---|
| 223 | typename Graph::OutEdgeIt e; |
---|
| 224 | public: |
---|
| 225 | OutEdgeIt() { } |
---|
| 226 | OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
---|
| 227 | OutEdgeIt(const Invalid& i) : e(i) { } |
---|
| 228 | OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : |
---|
| 229 | e(*(_G.graph), typename Graph::Node(_n)) { } |
---|
| 230 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
| 231 | }; |
---|
| 232 | class InEdgeIt { |
---|
| 233 | friend class GraphWrapper<Graph>; |
---|
| 234 | friend class RevGraphWrapper<Graph>; |
---|
| 235 | typename Graph::InEdgeIt e; |
---|
| 236 | public: |
---|
| 237 | InEdgeIt() { } |
---|
| 238 | InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
---|
| 239 | InEdgeIt(const Invalid& i) : e(i) { } |
---|
| 240 | InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : |
---|
| 241 | e(*(_G.graph), typename Graph::Node(_n)) { } |
---|
| 242 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
| 243 | }; |
---|
[238] | 244 | |
---|
[338] | 245 | using GraphWrapper<Graph>::first; |
---|
| 246 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 247 | i=OutEdgeIt(*this, p); return i; |
---|
| 248 | } |
---|
| 249 | InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 250 | i=InEdgeIt(*this, p); return i; |
---|
| 251 | } |
---|
| 252 | |
---|
| 253 | using GraphWrapper<Graph>::next; |
---|
| 254 | OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 255 | InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 256 | |
---|
| 257 | Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 258 | Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 259 | Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 260 | Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
[76] | 261 | }; |
---|
| 262 | |
---|
[335] | 263 | /// Wrapper for hiding nodes and edges from a graph. |
---|
| 264 | |
---|
| 265 | /// This wrapper shows a graph with filtered node-set and |
---|
| 266 | /// edge-set. The quick brown fox iterators jumps over |
---|
| 267 | /// the lazy dog nodes or edges if the values for them are false |
---|
| 268 | /// in the bool maps. |
---|
[311] | 269 | template<typename Graph, typename NodeFilterMap, |
---|
| 270 | typename EdgeFilterMap> |
---|
[303] | 271 | class SubGraphWrapper : public GraphWrapper<Graph> { |
---|
[263] | 272 | protected: |
---|
[311] | 273 | NodeFilterMap* node_filter_map; |
---|
| 274 | EdgeFilterMap* edge_filter_map; |
---|
[263] | 275 | public: |
---|
[338] | 276 | |
---|
[311] | 277 | SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, |
---|
| 278 | EdgeFilterMap& _edge_filter_map) : |
---|
| 279 | GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), |
---|
| 280 | edge_filter_map(&_edge_filter_map) { } |
---|
[263] | 281 | |
---|
[317] | 282 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 283 | class NodeIt { |
---|
| 284 | friend class GraphWrapper<Graph>; |
---|
| 285 | friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
---|
| 286 | typename Graph::NodeIt n; |
---|
| 287 | public: |
---|
[311] | 288 | NodeIt() { } |
---|
[317] | 289 | NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
---|
| 290 | NodeIt(const Invalid& i) : n(i) { } |
---|
[311] | 291 | NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
---|
[317] | 292 | n(*(_G.graph)) { |
---|
| 293 | while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) |
---|
| 294 | _G.graph->next(n); |
---|
[311] | 295 | } |
---|
[317] | 296 | operator Node() const { return Node(typename Graph::Node(n)); } |
---|
[311] | 297 | }; |
---|
[317] | 298 | typedef typename GraphWrapper<Graph>::Edge Edge; |
---|
| 299 | class OutEdgeIt { |
---|
| 300 | friend class GraphWrapper<Graph>; |
---|
| 301 | friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
---|
| 302 | typename Graph::OutEdgeIt e; |
---|
[311] | 303 | public: |
---|
| 304 | OutEdgeIt() { } |
---|
[317] | 305 | OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
---|
| 306 | OutEdgeIt(const Invalid& i) : e(i) { } |
---|
| 307 | OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, |
---|
| 308 | const Node& _n) : |
---|
| 309 | e(*(_G.graph), typename Graph::Node(_n)) { |
---|
| 310 | while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) |
---|
| 311 | _G.graph->next(e); |
---|
[311] | 312 | } |
---|
[317] | 313 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[311] | 314 | }; |
---|
[317] | 315 | class InEdgeIt { |
---|
| 316 | friend class GraphWrapper<Graph>; |
---|
| 317 | friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
---|
| 318 | typename Graph::InEdgeIt e; |
---|
[311] | 319 | public: |
---|
| 320 | InEdgeIt() { } |
---|
[317] | 321 | InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
---|
| 322 | InEdgeIt(const Invalid& i) : e(i) { } |
---|
[311] | 323 | InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, |
---|
[317] | 324 | const Node& _n) : |
---|
| 325 | e(*(_G.graph), typename Graph::Node(_n)) { |
---|
| 326 | while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) |
---|
| 327 | _G.graph->next(e); |
---|
[311] | 328 | } |
---|
[317] | 329 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[311] | 330 | }; |
---|
[317] | 331 | //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 332 | class EdgeIt { |
---|
| 333 | friend class GraphWrapper<Graph>; |
---|
| 334 | friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
---|
| 335 | typename Graph::EdgeIt e; |
---|
[311] | 336 | public: |
---|
| 337 | EdgeIt() { } |
---|
[317] | 338 | EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
---|
| 339 | EdgeIt(const Invalid& i) : e(i) { } |
---|
[311] | 340 | EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
---|
[317] | 341 | e(*(_G.graph)) { |
---|
| 342 | while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) |
---|
| 343 | _G.graph->next(e); |
---|
[311] | 344 | } |
---|
[317] | 345 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[311] | 346 | }; |
---|
[317] | 347 | |
---|
| 348 | NodeIt& first(NodeIt& i) const { |
---|
| 349 | i=NodeIt(*this); return i; |
---|
[263] | 350 | } |
---|
[317] | 351 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 352 | i=OutEdgeIt(*this, p); return i; |
---|
[311] | 353 | } |
---|
[317] | 354 | InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 355 | i=InEdgeIt(*this, p); return i; |
---|
[311] | 356 | } |
---|
[317] | 357 | EdgeIt& first(EdgeIt& i) const { |
---|
| 358 | i=EdgeIt(*this); return i; |
---|
[263] | 359 | } |
---|
| 360 | |
---|
[311] | 361 | NodeIt& next(NodeIt& i) const { |
---|
[317] | 362 | graph->next(i.n); |
---|
| 363 | while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); } |
---|
[311] | 364 | return i; |
---|
| 365 | } |
---|
| 366 | OutEdgeIt& next(OutEdgeIt& i) const { |
---|
[317] | 367 | graph->next(i.e); |
---|
| 368 | while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } |
---|
[311] | 369 | return i; |
---|
| 370 | } |
---|
| 371 | InEdgeIt& next(InEdgeIt& i) const { |
---|
[317] | 372 | graph->next(i.e); |
---|
| 373 | while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } |
---|
[311] | 374 | return i; |
---|
| 375 | } |
---|
| 376 | EdgeIt& next(EdgeIt& i) const { |
---|
[317] | 377 | graph->next(i.e); |
---|
| 378 | while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } |
---|
[311] | 379 | return i; |
---|
| 380 | } |
---|
| 381 | |
---|
[323] | 382 | Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 383 | Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 384 | Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 385 | Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 386 | |
---|
| 387 | void hide(const Node& n) const { node_filter_map->set(n, false); } |
---|
| 388 | void hide(const Edge& e) const { edge_filter_map->set(e, false); } |
---|
| 389 | |
---|
| 390 | void unHide(const Node& n) const { node_filter_map->set(n, true); } |
---|
| 391 | void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
---|
| 392 | |
---|
| 393 | bool hidden(const Node& n) const { return (*node_filter_map)[n]; } |
---|
| 394 | bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } |
---|
[263] | 395 | }; |
---|
[155] | 396 | |
---|
[338] | 397 | /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one. |
---|
[317] | 398 | |
---|
[338] | 399 | /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one. |
---|
[303] | 400 | template<typename Graph> |
---|
| 401 | class UndirGraphWrapper : public GraphWrapper<Graph> { |
---|
| 402 | public: |
---|
| 403 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 404 | typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
---|
[317] | 405 | typedef typename GraphWrapper<Graph>::Edge Edge; |
---|
| 406 | typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; |
---|
[236] | 407 | |
---|
[303] | 408 | UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
---|
[158] | 409 | |
---|
[317] | 410 | class OutEdgeIt { |
---|
[303] | 411 | friend class UndirGraphWrapper<Graph>; |
---|
[158] | 412 | bool out_or_in; //true iff out |
---|
[317] | 413 | typename Graph::OutEdgeIt out; |
---|
| 414 | typename Graph::InEdgeIt in; |
---|
[158] | 415 | public: |
---|
[317] | 416 | OutEdgeIt() { } |
---|
| 417 | OutEdgeIt(const Invalid& i) : Edge(i) { } |
---|
| 418 | OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) { |
---|
| 419 | out_or_in=true; _G.graph->first(out, _n); |
---|
| 420 | if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } |
---|
[174] | 421 | } |
---|
[317] | 422 | operator Edge() const { |
---|
| 423 | if (out_or_in) return Edge(out); else return Edge(in); |
---|
[158] | 424 | } |
---|
| 425 | }; |
---|
| 426 | |
---|
[317] | 427 | //FIXME InEdgeIt |
---|
[238] | 428 | typedef OutEdgeIt InEdgeIt; |
---|
| 429 | |
---|
[338] | 430 | using GraphWrapper<Graph>::first; |
---|
| 431 | // NodeIt& first(NodeIt& i) const { |
---|
| 432 | // i=NodeIt(*this); return i; |
---|
| 433 | // } |
---|
[317] | 434 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 435 | i=OutEdgeIt(*this, p); return i; |
---|
| 436 | } |
---|
| 437 | //FIXME |
---|
| 438 | // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 439 | // i=InEdgeIt(*this, p); return i; |
---|
| 440 | // } |
---|
[338] | 441 | // EdgeIt& first(EdgeIt& i) const { |
---|
| 442 | // i=EdgeIt(*this); return i; |
---|
| 443 | // } |
---|
[238] | 444 | |
---|
[338] | 445 | using GraphWrapper<Graph>::next; |
---|
| 446 | // NodeIt& next(NodeIt& n) const { |
---|
| 447 | // GraphWrapper<Graph>::next(n); |
---|
| 448 | // return n; |
---|
| 449 | // } |
---|
[158] | 450 | OutEdgeIt& next(OutEdgeIt& e) const { |
---|
| 451 | if (e.out_or_in) { |
---|
[317] | 452 | typename Graph::Node n=graph->tail(e.out); |
---|
[303] | 453 | graph->next(e.out); |
---|
| 454 | if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } |
---|
[158] | 455 | } else { |
---|
[303] | 456 | graph->next(e.in); |
---|
[158] | 457 | } |
---|
| 458 | return e; |
---|
| 459 | } |
---|
[317] | 460 | //FIXME InEdgeIt |
---|
[338] | 461 | // EdgeIt& next(EdgeIt& e) const { |
---|
| 462 | // GraphWrapper<Graph>::next(n); |
---|
| 463 | // // graph->next(e.e); |
---|
| 464 | // return e; |
---|
| 465 | // } |
---|
[238] | 466 | |
---|
| 467 | Node aNode(const OutEdgeIt& e) const { |
---|
[303] | 468 | if (e.out_or_in) return graph->tail(e); else return graph->head(e); } |
---|
[238] | 469 | Node bNode(const OutEdgeIt& e) const { |
---|
[303] | 470 | if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
---|
[338] | 471 | }; |
---|
[158] | 472 | |
---|
[338] | 473 | /// A wrapper for composing the residual graph for directed flow and circulation problems. |
---|
[238] | 474 | |
---|
[338] | 475 | /// A wrapper for composing the residual graph for directed flow and circulation problems. |
---|
[330] | 476 | template<typename Graph, typename Number, |
---|
| 477 | typename CapacityMap, typename FlowMap> |
---|
[311] | 478 | class ResGraphWrapper : public GraphWrapper<Graph> { |
---|
[199] | 479 | protected: |
---|
[330] | 480 | const CapacityMap* capacity; |
---|
[155] | 481 | FlowMap* flow; |
---|
| 482 | public: |
---|
[168] | 483 | |
---|
[330] | 484 | ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
---|
| 485 | FlowMap& _flow) : |
---|
| 486 | GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } |
---|
[168] | 487 | |
---|
[174] | 488 | class Edge; |
---|
[155] | 489 | class OutEdgeIt; |
---|
[174] | 490 | friend class Edge; |
---|
[155] | 491 | friend class OutEdgeIt; |
---|
[76] | 492 | |
---|
[311] | 493 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
| 494 | typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
---|
[317] | 495 | class Edge : public Graph::Edge { |
---|
[330] | 496 | friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
---|
[155] | 497 | protected: |
---|
[317] | 498 | bool forward; //true, iff forward |
---|
| 499 | // typename Graph::Edge e; |
---|
[155] | 500 | public: |
---|
[317] | 501 | Edge() { } |
---|
| 502 | Edge(const typename Graph::Edge& _e, bool _forward) : |
---|
| 503 | Graph::Edge(_e), forward(_forward) { } |
---|
| 504 | Edge(const Invalid& i) : Graph::Edge(i), forward(false) { } |
---|
| 505 | //the unique invalid iterator |
---|
[174] | 506 | friend bool operator==(const Edge& u, const Edge& v) { |
---|
[317] | 507 | return (v.forward==u.forward && |
---|
| 508 | static_cast<typename Graph::Edge>(u)== |
---|
| 509 | static_cast<typename Graph::Edge>(v)); |
---|
[174] | 510 | } |
---|
| 511 | friend bool operator!=(const Edge& u, const Edge& v) { |
---|
[317] | 512 | return (v.forward!=u.forward || |
---|
| 513 | static_cast<typename Graph::Edge>(u)!= |
---|
| 514 | static_cast<typename Graph::Edge>(v)); |
---|
[174] | 515 | } |
---|
[155] | 516 | }; |
---|
[338] | 517 | |
---|
[317] | 518 | class OutEdgeIt { |
---|
[330] | 519 | friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
---|
[317] | 520 | protected: |
---|
| 521 | typename Graph::OutEdgeIt out; |
---|
| 522 | typename Graph::InEdgeIt in; |
---|
| 523 | bool forward; |
---|
[155] | 524 | public: |
---|
| 525 | OutEdgeIt() { } |
---|
[168] | 526 | //FIXME |
---|
[317] | 527 | // OutEdgeIt(const Edge& e) : Edge(e) { } |
---|
| 528 | OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
---|
| 529 | //the unique invalid iterator |
---|
[330] | 530 | OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { |
---|
[317] | 531 | forward=true; |
---|
[303] | 532 | resG.graph->first(out, v); |
---|
[317] | 533 | while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } |
---|
[303] | 534 | if (!resG.graph->valid(out)) { |
---|
[317] | 535 | forward=false; |
---|
[303] | 536 | resG.graph->first(in, v); |
---|
[317] | 537 | while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } |
---|
[155] | 538 | } |
---|
| 539 | } |
---|
[317] | 540 | operator Edge() const { |
---|
| 541 | // Edge e; |
---|
| 542 | // e.forward=this->forward; |
---|
| 543 | // if (this->forward) e=out; else e=in; |
---|
| 544 | // return e; |
---|
| 545 | if (this->forward) |
---|
| 546 | return Edge(out, this->forward); |
---|
| 547 | else |
---|
| 548 | return Edge(in, this->forward); |
---|
| 549 | } |
---|
| 550 | }; |
---|
[263] | 551 | |
---|
[317] | 552 | class InEdgeIt { |
---|
[330] | 553 | friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
---|
[317] | 554 | protected: |
---|
| 555 | typename Graph::OutEdgeIt out; |
---|
| 556 | typename Graph::InEdgeIt in; |
---|
| 557 | bool forward; |
---|
| 558 | public: |
---|
| 559 | InEdgeIt() { } |
---|
| 560 | //FIXME |
---|
| 561 | // OutEdgeIt(const Edge& e) : Edge(e) { } |
---|
| 562 | InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
---|
| 563 | //the unique invalid iterator |
---|
[330] | 564 | InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { |
---|
[317] | 565 | forward=true; |
---|
| 566 | resG.graph->first(in, v); |
---|
| 567 | while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } |
---|
| 568 | if (!resG.graph->valid(in)) { |
---|
| 569 | forward=false; |
---|
| 570 | resG.graph->first(out, v); |
---|
| 571 | while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } |
---|
| 572 | } |
---|
| 573 | } |
---|
| 574 | operator Edge() const { |
---|
| 575 | // Edge e; |
---|
| 576 | // e.forward=this->forward; |
---|
| 577 | // if (this->forward) e=out; else e=in; |
---|
| 578 | // return e; |
---|
| 579 | if (this->forward) |
---|
| 580 | return Edge(in, this->forward); |
---|
| 581 | else |
---|
| 582 | return Edge(out, this->forward); |
---|
| 583 | } |
---|
| 584 | }; |
---|
| 585 | |
---|
| 586 | class EdgeIt { |
---|
[330] | 587 | friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
---|
[317] | 588 | protected: |
---|
| 589 | typename Graph::EdgeIt e; |
---|
| 590 | bool forward; |
---|
[155] | 591 | public: |
---|
[174] | 592 | EdgeIt() { } |
---|
[317] | 593 | EdgeIt(const Invalid& i) : e(i), forward(false) { } |
---|
[330] | 594 | EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { |
---|
[317] | 595 | forward=true; |
---|
| 596 | resG.graph->first(e); |
---|
| 597 | while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
---|
| 598 | if (!resG.graph->valid(e)) { |
---|
| 599 | forward=false; |
---|
| 600 | resG.graph->first(e); |
---|
| 601 | while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
---|
[155] | 602 | } |
---|
| 603 | } |
---|
[317] | 604 | operator Edge() const { |
---|
| 605 | return Edge(e, this->forward); |
---|
| 606 | } |
---|
| 607 | }; |
---|
[155] | 608 | |
---|
[338] | 609 | using GraphWrapper<Graph>::first; |
---|
| 610 | // NodeIt& first(NodeIt& i) const { |
---|
| 611 | // i=NodeIt(*this); return i; |
---|
| 612 | // } |
---|
[311] | 613 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
[317] | 614 | i=OutEdgeIt(*this, p); return i; |
---|
[311] | 615 | } |
---|
[317] | 616 | // FIXME not tested |
---|
| 617 | InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 618 | i=InEdgeIt(*this, p); return i; |
---|
| 619 | } |
---|
| 620 | EdgeIt& first(EdgeIt& i) const { |
---|
| 621 | i=EdgeIt(*this); return i; |
---|
[155] | 622 | } |
---|
[338] | 623 | |
---|
| 624 | using GraphWrapper<Graph>::next; |
---|
| 625 | // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
---|
[155] | 626 | OutEdgeIt& next(OutEdgeIt& e) const { |
---|
[317] | 627 | if (e.forward) { |
---|
[303] | 628 | Node v=graph->aNode(e.out); |
---|
| 629 | graph->next(e.out); |
---|
[317] | 630 | while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } |
---|
[303] | 631 | if (!graph->valid(e.out)) { |
---|
[317] | 632 | e.forward=false; |
---|
[303] | 633 | graph->first(e.in, v); |
---|
[317] | 634 | while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } |
---|
[155] | 635 | } |
---|
| 636 | } else { |
---|
[303] | 637 | graph->next(e.in); |
---|
[317] | 638 | while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } |
---|
[155] | 639 | } |
---|
| 640 | return e; |
---|
| 641 | } |
---|
[317] | 642 | // FIXME Not tested |
---|
| 643 | InEdgeIt& next(InEdgeIt& e) const { |
---|
| 644 | if (e.forward) { |
---|
| 645 | Node v=graph->aNode(e.in); |
---|
| 646 | graph->next(e.in); |
---|
| 647 | while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } |
---|
| 648 | if (!graph->valid(e.in)) { |
---|
| 649 | e.forward=false; |
---|
| 650 | graph->first(e.out, v); |
---|
| 651 | while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } |
---|
| 652 | } |
---|
| 653 | } else { |
---|
[303] | 654 | graph->next(e.out); |
---|
[317] | 655 | while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } |
---|
| 656 | } |
---|
| 657 | return e; |
---|
| 658 | } |
---|
| 659 | EdgeIt& next(EdgeIt& e) const { |
---|
| 660 | if (e.forward) { |
---|
| 661 | graph->next(e.e); |
---|
| 662 | while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } |
---|
| 663 | if (!graph->valid(e.e)) { |
---|
| 664 | e.forward=false; |
---|
| 665 | graph->first(e.e); |
---|
| 666 | while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } |
---|
[155] | 667 | } |
---|
[317] | 668 | } else { |
---|
| 669 | graph->next(e.e); |
---|
| 670 | while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } |
---|
[155] | 671 | } |
---|
[317] | 672 | return e; |
---|
| 673 | } |
---|
[76] | 674 | |
---|
[174] | 675 | Node tail(Edge e) const { |
---|
[317] | 676 | return ((e.forward) ? graph->tail(e) : graph->head(e)); } |
---|
[174] | 677 | Node head(Edge e) const { |
---|
[317] | 678 | return ((e.forward) ? graph->head(e) : graph->tail(e)); } |
---|
[76] | 679 | |
---|
[174] | 680 | Node aNode(OutEdgeIt e) const { |
---|
[317] | 681 | return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
---|
[174] | 682 | Node bNode(OutEdgeIt e) const { |
---|
[317] | 683 | return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
---|
[76] | 684 | |
---|
[338] | 685 | // int nodeNum() const { return graph->nodeNum(); } |
---|
[263] | 686 | //FIXME |
---|
[338] | 687 | void edgeNum() const { } |
---|
[303] | 688 | //int edgeNum() const { return graph->edgeNum(); } |
---|
[263] | 689 | |
---|
| 690 | |
---|
[317] | 691 | // int id(Node v) const { return graph->id(v); } |
---|
[155] | 692 | |
---|
[317] | 693 | bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } |
---|
[174] | 694 | bool valid(Edge e) const { |
---|
[317] | 695 | return graph->valid(e); |
---|
| 696 | //return e.forward ? graph->valid(e.out) : graph->valid(e.in); |
---|
| 697 | } |
---|
[155] | 698 | |
---|
[174] | 699 | void augment(const Edge& e, Number a) const { |
---|
[317] | 700 | if (e.forward) |
---|
[303] | 701 | // flow->set(e.out, flow->get(e.out)+a); |
---|
[317] | 702 | flow->set(e, (*flow)[e]+a); |
---|
[168] | 703 | else |
---|
[303] | 704 | // flow->set(e.in, flow->get(e.in)-a); |
---|
[317] | 705 | flow->set(e, (*flow)[e]-a); |
---|
[168] | 706 | } |
---|
| 707 | |
---|
[269] | 708 | Number resCap(const Edge& e) const { |
---|
[317] | 709 | if (e.forward) |
---|
[303] | 710 | // return (capacity->get(e.out)-flow->get(e.out)); |
---|
[317] | 711 | return ((*capacity)[e]-(*flow)[e]); |
---|
[168] | 712 | else |
---|
[303] | 713 | // return (flow->get(e.in)); |
---|
[317] | 714 | return ((*flow)[e]); |
---|
[168] | 715 | } |
---|
| 716 | |
---|
[317] | 717 | // Number resCap(typename Graph::OutEdgeIt out) const { |
---|
| 718 | // // return (capacity->get(out)-flow->get(out)); |
---|
| 719 | // return ((*capacity)[out]-(*flow)[out]); |
---|
| 720 | // } |
---|
[168] | 721 | |
---|
[317] | 722 | // Number resCap(typename Graph::InEdgeIt in) const { |
---|
| 723 | // // return (flow->get(in)); |
---|
| 724 | // return ((*flow)[in]); |
---|
| 725 | // } |
---|
[168] | 726 | |
---|
[155] | 727 | template <typename T> |
---|
| 728 | class EdgeMap { |
---|
[303] | 729 | typename Graph::EdgeMap<T> forward_map, backward_map; |
---|
[155] | 730 | public: |
---|
[330] | 731 | EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
---|
| 732 | EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
---|
[174] | 733 | void set(Edge e, T a) { |
---|
[317] | 734 | if (e.forward) |
---|
[155] | 735 | forward_map.set(e.out, a); |
---|
| 736 | else |
---|
| 737 | backward_map.set(e.in, a); |
---|
| 738 | } |
---|
[303] | 739 | T operator[](Edge e) const { |
---|
[317] | 740 | if (e.forward) |
---|
[303] | 741 | return forward_map[e.out]; |
---|
[155] | 742 | else |
---|
[303] | 743 | return backward_map[e.in]; |
---|
[155] | 744 | } |
---|
[303] | 745 | // T get(Edge e) const { |
---|
| 746 | // if (e.out_or_in) |
---|
| 747 | // return forward_map.get(e.out); |
---|
| 748 | // else |
---|
| 749 | // return backward_map.get(e.in); |
---|
| 750 | // } |
---|
[155] | 751 | }; |
---|
[168] | 752 | }; |
---|
| 753 | |
---|
[338] | 754 | /// ErasingFirstGraphWrapper for blocking flows. |
---|
[317] | 755 | |
---|
[338] | 756 | /// ErasingFirstGraphWrapper for blocking flows. |
---|
[303] | 757 | template<typename Graph, typename FirstOutEdgesMap> |
---|
| 758 | class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
---|
[269] | 759 | protected: |
---|
| 760 | FirstOutEdgesMap* first_out_edges; |
---|
| 761 | public: |
---|
[303] | 762 | ErasingFirstGraphWrapper(Graph& _graph, |
---|
| 763 | FirstOutEdgesMap& _first_out_edges) : |
---|
| 764 | GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
---|
[269] | 765 | |
---|
[317] | 766 | typedef typename GraphWrapper<Graph>::Node Node; |
---|
[338] | 767 | // class NodeIt { |
---|
| 768 | // friend class GraphWrapper<Graph>; |
---|
| 769 | // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
---|
| 770 | // typename Graph::NodeIt n; |
---|
| 771 | // public: |
---|
| 772 | // NodeIt() { } |
---|
| 773 | // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
---|
| 774 | // NodeIt(const Invalid& i) : n(i) { } |
---|
| 775 | // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
---|
| 776 | // n(*(_G.graph)) { } |
---|
| 777 | // operator Node() const { return Node(typename Graph::Node(n)); } |
---|
| 778 | // }; |
---|
[317] | 779 | typedef typename GraphWrapper<Graph>::Edge Edge; |
---|
| 780 | class OutEdgeIt { |
---|
| 781 | friend class GraphWrapper<Graph>; |
---|
| 782 | friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
---|
| 783 | // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
---|
| 784 | typename Graph::OutEdgeIt e; |
---|
[311] | 785 | public: |
---|
| 786 | OutEdgeIt() { } |
---|
[317] | 787 | OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
---|
| 788 | OutEdgeIt(const Invalid& i) : e(i) { } |
---|
[311] | 789 | OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
---|
[317] | 790 | const Node& _n) : |
---|
| 791 | e((*_G.first_out_edges)[_n]) { } |
---|
| 792 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[311] | 793 | }; |
---|
[317] | 794 | class InEdgeIt { |
---|
| 795 | friend class GraphWrapper<Graph>; |
---|
| 796 | friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
---|
| 797 | // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
---|
| 798 | typename Graph::InEdgeIt e; |
---|
[311] | 799 | public: |
---|
| 800 | InEdgeIt() { } |
---|
[317] | 801 | InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
---|
| 802 | InEdgeIt(const Invalid& i) : e(i) { } |
---|
[311] | 803 | InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
---|
[317] | 804 | const Node& _n) : |
---|
| 805 | e(*(_G.graph), typename Graph::Node(_n)) { } |
---|
| 806 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[311] | 807 | }; |
---|
| 808 | //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
[317] | 809 | class EdgeIt { |
---|
| 810 | friend class GraphWrapper<Graph>; |
---|
| 811 | friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
---|
| 812 | // typedef typename Graph::EdgeIt GraphEdgeIt; |
---|
| 813 | typename Graph::EdgeIt e; |
---|
[311] | 814 | public: |
---|
| 815 | EdgeIt() { } |
---|
[317] | 816 | EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
---|
| 817 | EdgeIt(const Invalid& i) : e(i) { } |
---|
[311] | 818 | EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
---|
[317] | 819 | e(*(_G.graph)) { } |
---|
| 820 | operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
[311] | 821 | }; |
---|
| 822 | |
---|
[338] | 823 | using GraphWrapper<Graph>::first; |
---|
| 824 | // NodeIt& first(NodeIt& i) const { |
---|
| 825 | // i=NodeIt(*this); return i; |
---|
| 826 | // } |
---|
[317] | 827 | OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 828 | i=OutEdgeIt(*this, p); return i; |
---|
[269] | 829 | } |
---|
[317] | 830 | InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 831 | i=InEdgeIt(*this, p); return i; |
---|
[311] | 832 | } |
---|
[317] | 833 | EdgeIt& first(EdgeIt& i) const { |
---|
| 834 | i=EdgeIt(*this); return i; |
---|
[311] | 835 | } |
---|
| 836 | |
---|
[338] | 837 | using GraphWrapper<Graph>::next; |
---|
| 838 | // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
---|
[317] | 839 | OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 840 | InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 841 | EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 842 | |
---|
| 843 | Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 844 | Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 845 | Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 846 | Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
[311] | 847 | |
---|
[269] | 848 | void erase(const OutEdgeIt& e) const { |
---|
| 849 | OutEdgeIt f=e; |
---|
| 850 | this->next(f); |
---|
[317] | 851 | first_out_edges->set(this->tail(e), f.e); |
---|
[269] | 852 | } |
---|
| 853 | }; |
---|
| 854 | |
---|
[341] | 855 | |
---|
| 856 | |
---|
| 857 | // /// experimentral, do not try it. |
---|
| 858 | // template<typename Graph> |
---|
| 859 | // class stGraphWrapper : public GraphWrapper<Graph> { |
---|
| 860 | // public: |
---|
| 861 | // class Node; |
---|
| 862 | // class NodeIt; |
---|
| 863 | // class Edge; |
---|
| 864 | // class OutEdgeIt; |
---|
| 865 | // class InEdgeIt; |
---|
| 866 | // class EdgeIt; |
---|
| 867 | |
---|
| 868 | // const Node s; |
---|
| 869 | // const Node t; |
---|
| 870 | |
---|
| 871 | // stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph), |
---|
| 872 | // s(INVALID, 1), t(INVALID, 2) { } |
---|
| 873 | |
---|
| 874 | // class Node : public Graph::Node { |
---|
| 875 | // friend class GraphWrapper<Graph>; |
---|
| 876 | // friend class stGraphWrapper<Graph>; |
---|
| 877 | // protected: |
---|
| 878 | // int spec; //0 if real node, 1 iff s, 2 iff t |
---|
| 879 | // public: |
---|
| 880 | // Node() { } |
---|
| 881 | // Node(const typename Graph::Node& _n, int _spec=0) : |
---|
| 882 | // Graph::Node(_n), spec(_spec) { } |
---|
| 883 | // Node(const Invalid& i) : Graph::Node(i), spec(2) { } |
---|
| 884 | // //invalid: (invalid, 2); |
---|
| 885 | // }; |
---|
| 886 | |
---|
| 887 | // class NodeIt { |
---|
| 888 | // friend class GraphWrapper<Graph>; |
---|
| 889 | // friend class stGraphWrapper<Graph>; |
---|
| 890 | // typename Graph::NodeIt n; |
---|
| 891 | // int spec; |
---|
| 892 | // public: |
---|
| 893 | // NodeIt() { } |
---|
| 894 | // NodeIt(const typename Graph::NodeIt& _n, int _spec=0) : |
---|
| 895 | // n(_n), spec(_spec) { } |
---|
| 896 | // NodeIt(const Invalid& i) : n(i), spec(2) { } |
---|
| 897 | // NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { |
---|
| 898 | // if (!_G->valid(n)) spec=1; |
---|
| 899 | // } |
---|
| 900 | // operator Node() const { return Node(n, spec); } |
---|
| 901 | // }; |
---|
| 902 | // // typedef typename Graph::Edge Edge; |
---|
| 903 | // class Edge : public Graph::Edge { |
---|
| 904 | // friend class GraphWrapper<Graph>; |
---|
| 905 | // friend class stGraphWrapper<Graph>; |
---|
| 906 | // Node tail_spec; |
---|
| 907 | // Node head_spec; |
---|
| 908 | // public: |
---|
| 909 | // Edge() { } |
---|
| 910 | // Edge(const typename Graph::Edge& _e) : |
---|
| 911 | // Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) { |
---|
| 912 | // //a tail-t es a head-et real node-ra csinaljuk |
---|
| 913 | // } |
---|
| 914 | // Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { } |
---|
| 915 | // }; |
---|
| 916 | // class OutEdgeIt { |
---|
| 917 | // friend class GraphWrapper<Graph>; |
---|
| 918 | // friend class stGraphWrapper<Graph>; |
---|
| 919 | // typename Graph::OutEdgeIt e; |
---|
| 920 | // Node tail_spec; |
---|
| 921 | // Node head_spec; |
---|
| 922 | // public: |
---|
| 923 | // OutEdgeIt() { } |
---|
| 924 | // OutEdgeIt(const typename Graph::OutEdgeIt& _e) : |
---|
| 925 | // e(_e), tail_spec(i, 0), head_spec(i, 0) { |
---|
| 926 | // //a tail-t es a head-et real node-ra csinaljuk |
---|
| 927 | // } |
---|
| 928 | // OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { } |
---|
| 929 | // //invalid: (barmi, 0, 2) |
---|
| 930 | // OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) { |
---|
| 931 | // switch (_n.spec) { |
---|
| 932 | // case 0 : |
---|
| 933 | // e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
---|
| 934 | // _tail.spec=0; |
---|
| 935 | // _head.spec=0; |
---|
| 936 | // if (!_G.graph->valid(e)) spec=1; |
---|
| 937 | // break; |
---|
| 938 | // case 1: |
---|
| 939 | // e=INVALID; |
---|
| 940 | // _tail.spec=1; |
---|
| 941 | // _head(_G.graph->first(typename Graph::NodeIt())); |
---|
| 942 | // if _head.spec==1 |
---|
| 943 | // break; |
---|
| 944 | // }; |
---|
| 945 | |
---|
| 946 | // } |
---|
| 947 | // operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
| 948 | // }; |
---|
| 949 | // class InEdgeIt { |
---|
| 950 | // friend class GraphWrapper<Graph>; |
---|
| 951 | // typename Graph::InEdgeIt e; |
---|
| 952 | // public: |
---|
| 953 | // InEdgeIt() { } |
---|
| 954 | // InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
---|
| 955 | // InEdgeIt(const Invalid& i) : e(i) { } |
---|
| 956 | // InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : |
---|
| 957 | // e(*(_G.graph), typename Graph::Node(_n)) { } |
---|
| 958 | // operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
| 959 | // }; |
---|
| 960 | // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
---|
| 961 | // class EdgeIt { |
---|
| 962 | // friend class GraphWrapper<Graph>; |
---|
| 963 | // typename Graph::EdgeIt e; |
---|
| 964 | // public: |
---|
| 965 | // EdgeIt() { } |
---|
| 966 | // EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
---|
| 967 | // EdgeIt(const Invalid& i) : e(i) { } |
---|
| 968 | // EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { } |
---|
| 969 | // operator Edge() const { return Edge(typename Graph::Edge(e)); } |
---|
| 970 | // }; |
---|
| 971 | |
---|
| 972 | // NodeIt& first(NodeIt& i) const { |
---|
| 973 | // i=NodeIt(*this); return i; |
---|
| 974 | // } |
---|
| 975 | // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
---|
| 976 | // i=OutEdgeIt(*this, p); return i; |
---|
| 977 | // } |
---|
| 978 | // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
---|
| 979 | // i=InEdgeIt(*this, p); return i; |
---|
| 980 | // } |
---|
| 981 | // EdgeIt& first(EdgeIt& i) const { |
---|
| 982 | // i=EdgeIt(*this); return i; |
---|
| 983 | // } |
---|
| 984 | |
---|
| 985 | // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
---|
| 986 | // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 987 | // InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 988 | // EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
---|
| 989 | |
---|
| 990 | // Node head(const Edge& e) const { |
---|
| 991 | // return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
---|
| 992 | // Node tail(const Edge& e) const { |
---|
| 993 | // return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
---|
| 994 | |
---|
| 995 | // bool valid(const Node& n) const { |
---|
| 996 | // return graph->valid(static_cast<typename Graph::Node>(n)); } |
---|
| 997 | // bool valid(const Edge& e) const { |
---|
| 998 | // return graph->valid(static_cast<typename Graph::Edge>(e)); } |
---|
| 999 | |
---|
| 1000 | // int nodeNum() const { return graph->nodeNum(); } |
---|
| 1001 | // int edgeNum() const { return graph->edgeNum(); } |
---|
| 1002 | |
---|
| 1003 | // Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 1004 | // Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
---|
| 1005 | // Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 1006 | // Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
---|
| 1007 | |
---|
| 1008 | // Node addNode() const { return Node(graph->addNode()); } |
---|
| 1009 | // Edge addEdge(const Node& tail, const Node& head) const { |
---|
| 1010 | // return Edge(graph->addEdge(tail, head)); } |
---|
| 1011 | |
---|
| 1012 | // void erase(const Node& i) const { graph->erase(i); } |
---|
| 1013 | // void erase(const Edge& i) const { graph->erase(i); } |
---|
| 1014 | |
---|
| 1015 | // void clear() const { graph->clear(); } |
---|
| 1016 | |
---|
| 1017 | // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
---|
| 1018 | // public: |
---|
| 1019 | // NodeMap(const GraphWrapper<Graph>& _G) : |
---|
| 1020 | // Graph::NodeMap<T>(*(_G.graph)) { } |
---|
| 1021 | // NodeMap(const GraphWrapper<Graph>& _G, T a) : |
---|
| 1022 | // Graph::NodeMap<T>(*(_G.graph), a) { } |
---|
| 1023 | // }; |
---|
| 1024 | |
---|
| 1025 | // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
---|
| 1026 | // public: |
---|
| 1027 | // EdgeMap(const GraphWrapper<Graph>& _G) : |
---|
| 1028 | // Graph::EdgeMap<T>(*(_G.graph)) { } |
---|
| 1029 | // EdgeMap(const GraphWrapper<Graph>& _G, T a) : |
---|
| 1030 | // Graph::EdgeMap<T>(*(_G.graph), a) { } |
---|
| 1031 | // }; |
---|
| 1032 | // }; |
---|
| 1033 | |
---|
[105] | 1034 | } //namespace hugo |
---|
[76] | 1035 | |
---|
[259] | 1036 | #endif //HUGO_GRAPH_WRAPPER_H |
---|
[76] | 1037 | |
---|