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