COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1949:5db4ff8d69de

Last change on this file since 1949:5db4ff8d69de was 1949:5db4ff8d69de, checked in by Alpar Juttner, 14 years ago

Fight with Doxygen.
Victory hasn't been reached yet, but it's on the horizon.

File size: 52.7 KB
Line 
1/* -*- C++ -*-
2 * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_GRAPH_ADAPTOR_H
18#define LEMON_GRAPH_ADAPTOR_H
19
20///\ingroup graph_adaptors
21///\file
22///\brief Several graph adaptors.
23///
24///This file contains several useful graph adaptor functions.
25///
26///\author Marton Makai
27
28#include <lemon/invalid.h>
29#include <lemon/maps.h>
30#include <lemon/bits/erasable_graph_extender.h>
31#include <lemon/bits/clearable_graph_extender.h>
32#include <lemon/bits/extendable_graph_extender.h>
33#include <lemon/bits/iterable_graph_extender.h>
34#include <lemon/bits/alteration_notifier.h>
35#include <lemon/bits/default_map.h>
36#include <lemon/bits/graph_extender.h>
37#include <iostream>
38
39namespace lemon {
40
41  //x\brief Base type for the Graph Adaptors
42  //x\ingroup graph_adaptors
43  //x   
44  //xBase type for the Graph Adaptors
45  //x   
46  //x\warning Graph adaptors are in even
47  //xmore experimental state than the other
48  //xparts of the lib. Use them at you own risk.
49  //x
50  //xThis is the base type for most of LEMON graph adaptors.
51  //xThis class implements a trivial graph adaptor i.e. it only wraps the
52  //xfunctions and types of the graph. The purpose of this class is to
53  //xmake easier implementing graph adaptors. E.g. if an adaptor is
54  //xconsidered which differs from the wrapped graph only in some of its
55  //xfunctions or types, then it can be derived from GraphAdaptor,
56  //xand only the
57  //xdifferences should be implemented.
58  //x
59  //xauthor Marton Makai
60  template<typename _Graph>
61  class GraphAdaptorBase {
62  public:
63    typedef _Graph Graph;
64    typedef Graph ParentGraph;
65
66  protected:
67    Graph* graph;
68    GraphAdaptorBase() : graph(0) { }
69    void setGraph(Graph& _graph) { graph=&_graph; }
70
71  public:
72    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
73 
74    typedef typename Graph::Node Node;
75    typedef typename Graph::Edge Edge;
76   
77    void first(Node& i) const { graph->first(i); }
78    void first(Edge& i) const { graph->first(i); }
79    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
80    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
81
82    void next(Node& i) const { graph->next(i); }
83    void next(Edge& i) const { graph->next(i); }
84    void nextIn(Edge& i) const { graph->nextIn(i); }
85    void nextOut(Edge& i) const { graph->nextOut(i); }
86
87    Node source(const Edge& e) const { return graph->source(e); }
88    Node target(const Edge& e) const { return graph->target(e); }
89
90    typedef NodeNumTagIndicator<Graph> NodeNumTag;
91    int nodeNum() const { return graph->nodeNum(); }
92   
93    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
94    int edgeNum() const { return graph->edgeNum(); }
95
96    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
97    Edge findEdge(const Node& source, const Node& target,
98                  const Edge& prev = INVALID) {
99      return graph->findEdge(source, target, prev);
100    }
101 
102    Node addNode() const {
103      return Node(graph->addNode());
104    }
105
106    Edge addEdge(const Node& source, const Node& target) const {
107      return Edge(graph->addEdge(source, target));
108    }
109
110    void erase(const Node& i) const { graph->erase(i); }
111    void erase(const Edge& i) const { graph->erase(i); }
112 
113    void clear() const { graph->clear(); }
114   
115    int id(const Node& v) const { return graph->id(v); }
116    int id(const Edge& e) const { return graph->id(e); }
117   
118    Edge oppositeNode(const Edge& e) const {
119      return Edge(graph->opposite(e));
120    }
121
122    template <typename _Value>
123    class NodeMap : public _Graph::template NodeMap<_Value> {
124    public:
125      typedef typename _Graph::template NodeMap<_Value> Parent;
126      explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
127        : Parent(*gw.graph) { }
128      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
129        : Parent(*gw.graph, value) { }
130    };
131
132    template <typename _Value>
133    class EdgeMap : public _Graph::template EdgeMap<_Value> {
134    public:
135      typedef typename _Graph::template EdgeMap<_Value> Parent;
136      explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
137        : Parent(*gw.graph) { }
138      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
139        : Parent(*gw.graph, value) { }
140    };
141
142  };
143
144  template <typename _Graph>
145  class GraphAdaptor :
146    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
147  public:
148    typedef _Graph Graph;
149    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
150  protected:
151    GraphAdaptor() : Parent() { }
152
153  public:
154    explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
155  };
156
157  template <typename _Graph>
158  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
159  public:
160    typedef _Graph Graph;
161    typedef GraphAdaptorBase<_Graph> Parent;
162  protected:
163    RevGraphAdaptorBase() : Parent() { }
164  public:
165    typedef typename Parent::Node Node;
166    typedef typename Parent::Edge Edge;
167
168    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
169    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
170
171    void nextIn(Edge& i) const { Parent::nextOut(i); }
172    void nextOut(Edge& i) const { Parent::nextIn(i); }
173
174    Node source(const Edge& e) const { return Parent::target(e); }
175    Node target(const Edge& e) const { return Parent::source(e); }
176  };
177   
178
179  ///\brief A graph adaptor which reverses the orientation of the edges.
180  ///\ingroup graph_adaptors
181  ///
182  ///\warning Graph adaptors are in even more experimental
183  ///state than the other
184  ///parts of the lib. Use them at you own risk.
185  ///
186  /// If \c g is defined as
187  ///\code
188  /// ListGraph g;
189  ///\endcode
190  /// then
191  ///\code
192  /// RevGraphAdaptor<ListGraph> gw(g);
193  ///\endcode
194  ///implements the graph obtained from \c g by
195  /// reversing the orientation of its edges.
196
197  template<typename _Graph>
198  class RevGraphAdaptor :
199    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
200  public:
201    typedef _Graph Graph;
202    typedef IterableGraphExtender<
203      RevGraphAdaptorBase<_Graph> > Parent;
204  protected:
205    RevGraphAdaptor() { }
206  public:
207    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
208  };
209
210 
211  template <typename _Graph, typename NodeFilterMap,
212            typename EdgeFilterMap, bool checked = true>
213  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
214  public:
215    typedef _Graph Graph;
216    typedef GraphAdaptorBase<_Graph> Parent;
217  protected:
218    NodeFilterMap* node_filter_map;
219    EdgeFilterMap* edge_filter_map;
220    SubGraphAdaptorBase() : Parent(),
221                            node_filter_map(0), edge_filter_map(0) { }
222
223    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
224      node_filter_map=&_node_filter_map;
225    }
226    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
227      edge_filter_map=&_edge_filter_map;
228    }
229
230  public:
231
232    typedef typename Parent::Node Node;
233    typedef typename Parent::Edge Edge;
234
235    void first(Node& i) const {
236      Parent::first(i);
237      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
238    }
239
240    void first(Edge& i) const {
241      Parent::first(i);
242      while (i!=INVALID && (!(*edge_filter_map)[i]
243             || !(*node_filter_map)[Parent::source(i)]
244             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
245    }
246
247    void firstIn(Edge& i, const Node& n) const {
248      Parent::firstIn(i, n);
249      while (i!=INVALID && (!(*edge_filter_map)[i]
250             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
251    }
252
253    void firstOut(Edge& i, const Node& n) const {
254      Parent::firstOut(i, n);
255      while (i!=INVALID && (!(*edge_filter_map)[i]
256             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
257    }
258
259    void next(Node& i) const {
260      Parent::next(i);
261      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
262    }
263
264    void next(Edge& i) const {
265      Parent::next(i);
266      while (i!=INVALID && (!(*edge_filter_map)[i]
267             || !(*node_filter_map)[Parent::source(i)]
268             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
269    }
270
271    void nextIn(Edge& i) const {
272      Parent::nextIn(i);
273      while (i!=INVALID && (!(*edge_filter_map)[i]
274             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
275    }
276
277    void nextOut(Edge& i) const {
278      Parent::nextOut(i);
279      while (i!=INVALID && (!(*edge_filter_map)[i]
280             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
281    }
282
283    //x\e
284
285    //x This function hides \c n in the graph, i.e. the iteration
286    //x jumps over it. This is done by simply setting the value of \c n 
287    //x to be false in the corresponding node-map.
288    void hide(const Node& n) const { node_filter_map->set(n, false); }
289
290    //x\e
291
292    //x This function hides \c e in the graph, i.e. the iteration
293    //x jumps over it. This is done by simply setting the value of \c e 
294    //x to be false in the corresponding edge-map.
295    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
296
297    //x\e
298
299    //x The value of \c n is set to be true in the node-map which stores
300    //x hide information. If \c n was hidden previuosly, then it is shown
301    //x again
302     void unHide(const Node& n) const { node_filter_map->set(n, true); }
303
304    //x\e
305
306    //x The value of \c e is set to be true in the edge-map which stores
307    //x hide information. If \c e was hidden previuosly, then it is shown
308    //x again
309    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
310
311    //x Returns true if \c n is hidden.
312   
313    //x\e
314    //x
315    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
316
317    //x Returns true if \c n is hidden.
318   
319    //x\e
320    //x
321    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
322
323    typedef False NodeNumTag;
324    typedef False EdgeNumTag;
325  };
326
327  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
328  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
329    : public GraphAdaptorBase<_Graph> {
330  public:
331    typedef _Graph Graph;
332    typedef GraphAdaptorBase<_Graph> Parent;
333  protected:
334    NodeFilterMap* node_filter_map;
335    EdgeFilterMap* edge_filter_map;
336    SubGraphAdaptorBase() : Parent(),
337                            node_filter_map(0), edge_filter_map(0) { }
338
339    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
340      node_filter_map=&_node_filter_map;
341    }
342    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
343      edge_filter_map=&_edge_filter_map;
344    }
345
346  public:
347
348    typedef typename Parent::Node Node;
349    typedef typename Parent::Edge Edge;
350
351    void first(Node& i) const {
352      Parent::first(i);
353      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
354    }
355
356    void first(Edge& i) const {
357      Parent::first(i);
358      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
359    }
360
361    void firstIn(Edge& i, const Node& n) const {
362      Parent::firstIn(i, n);
363      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
364    }
365
366    void firstOut(Edge& i, const Node& n) const {
367      Parent::firstOut(i, n);
368      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
369    }
370
371    void next(Node& i) const {
372      Parent::next(i);
373      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
374    }
375    void next(Edge& i) const {
376      Parent::next(i);
377      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
378    }
379    void nextIn(Edge& i) const {
380      Parent::nextIn(i);
381      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
382    }
383
384    void nextOut(Edge& i) const {
385      Parent::nextOut(i);
386      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
387    }
388
389    //x\e
390
391    //x This function hides \c n in the graph, i.e. the iteration
392    //x jumps over it. This is done by simply setting the value of \c n 
393    //x to be false in the corresponding node-map.
394    void hide(const Node& n) const { node_filter_map->set(n, false); }
395
396    //x\e
397
398    //x This function hides \c e in the graph, i.e. the iteration
399    //x jumps over it. This is done by simply setting the value of \c e 
400    //x to be false in the corresponding edge-map.
401    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
402
403    //x\e
404
405    //x The value of \c n is set to be true in the node-map which stores
406    //x hide information. If \c n was hidden previuosly, then it is shown
407    //x again
408     void unHide(const Node& n) const { node_filter_map->set(n, true); }
409
410    //x\e
411
412    //x The value of \c e is set to be true in the edge-map which stores
413    //x hide information. If \c e was hidden previuosly, then it is shown
414    //x again
415    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
416
417    //x Returns true if \c n is hidden.
418   
419    //x\e
420    //x
421    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
422
423    //x Returns true if \c n is hidden.
424   
425    //x\e
426    //x
427    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
428
429    typedef False NodeNumTag;
430    typedef False EdgeNumTag;
431  };
432
433  //x\brief A graph adaptor for hiding nodes and edges from a graph.
434  //x\ingroup graph_adaptors
435  //x
436  //x\warning Graph adaptors are in even more experimental
437  //xstate than the other
438  //xparts of the lib. Use them at you own risk.
439  //x
440  //xSubGraphAdaptor shows the graph with filtered node-set and
441  //xedge-set. If the \c checked parameter is true then it filters the edgeset
442  //xto do not get invalid edges without source or target.
443  //xLet \f$G=(V, A)\f$ be a directed graph
444  //xand suppose that the graph instance \c g of type ListGraph implements
445  //x\f$G\f$.
446  //x/Let moreover \f$b_V\f$ and
447  //x\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
448  //xSubGraphAdaptor<...>::NodeIt iterates
449  //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
450  //xSubGraphAdaptor<...>::EdgeIt iterates
451  //xon the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
452  //xSubGraphAdaptor<...>::OutEdgeIt and
453  //xSubGraphAdaptor<...>::InEdgeIt iterates
454  //xonly on edges leaving and entering a specific node which have true value.
455  //x
456  //xIf the \c checked template parameter is false then we have to note that
457  //xthe node-iterator cares only the filter on the node-set, and the
458  //xedge-iterator cares only the filter on the edge-set.
459  //xThis way the edge-map
460  //xshould filter all edges which's source or target is filtered by the
461  //xnode-filter.
462  //x\code
463  //xtypedef ListGraph Graph;
464  //xGraph g;
465  //xtypedef Graph::Node Node;
466  //xtypedef Graph::Edge Edge;
467  //xNode u=g.addNode(); //node of id 0
468  //xNode v=g.addNode(); //node of id 1
469  //xNode e=g.addEdge(u, v); //edge of id 0
470  //xNode f=g.addEdge(v, u); //edge of id 1
471  //xGraph::NodeMap<bool> nm(g, true);
472  //xnm.set(u, false);
473  //xGraph::EdgeMap<bool> em(g, true);
474  //xem.set(e, false);
475  //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
476  //xSubGW gw(g, nm, em);
477  //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
478  //xstd::cout << ":-)" << std::endl;
479  //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
480  //x\endcode
481  //xThe output of the above code is the following.
482  //x\code
483  //x1
484  //x:-)
485  //x1
486  //x\endcode
487  //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to
488  //x\c Graph::Node that is why \c g.id(n) can be applied.
489  //x
490  //xFor other examples see also the documentation of NodeSubGraphAdaptor and
491  //xEdgeSubGraphAdaptor.
492  //x
493  //x\author Marton Makai
494
495  template<typename _Graph, typename NodeFilterMap,
496           typename EdgeFilterMap, bool checked = true>
497  class SubGraphAdaptor :
498    public IterableGraphExtender<
499    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
500  public:
501    typedef _Graph Graph;
502    typedef IterableGraphExtender<
503      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
504  protected:
505    SubGraphAdaptor() { }
506  public:
507    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
508                    EdgeFilterMap& _edge_filter_map) {
509      setGraph(_graph);
510      setNodeFilterMap(_node_filter_map);
511      setEdgeFilterMap(_edge_filter_map);
512    }
513  };
514
515
516
517  //x\brief An adaptor for hiding nodes from a graph.
518  //x\ingroup graph_adaptors
519  //x
520  //x\warning Graph adaptors are in even more experimental state
521  //xthan the other
522  //xparts of the lib. Use them at you own risk.
523  //x
524  //xAn adaptor for hiding nodes from a graph.
525  //xThis adaptor specializes SubGraphAdaptor in the way that only
526  //xthe node-set
527  //xcan be filtered. In usual case the checked parameter is true, we get the
528  //xinduced subgraph. But if the checked parameter is false then we can only
529  //xfilter only isolated nodes.
530  //x\author Marton Makai
531  template<typename Graph, typename NodeFilterMap, bool checked = true>
532  class NodeSubGraphAdaptor :
533    public SubGraphAdaptor<Graph, NodeFilterMap,
534                           ConstMap<typename Graph::Edge,bool>, checked> {
535  public:
536    typedef SubGraphAdaptor<Graph, NodeFilterMap,
537                            ConstMap<typename Graph::Edge,bool> > Parent;
538  protected:
539    ConstMap<typename Graph::Edge, bool> const_true_map;
540  public:
541    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
542      Parent(), const_true_map(true) {
543      Parent::setGraph(_graph);
544      Parent::setNodeFilterMap(_node_filter_map);
545      Parent::setEdgeFilterMap(const_true_map);
546    }
547  };
548
549
550  //x\brief An adaptor for hiding edges from a graph.
551  //x
552  //x\warning Graph adaptors are in even more experimental state
553  //xthan the other parts of the lib. Use them at you own risk.
554  //x
555  //xAn adaptor for hiding edges from a graph.
556  //xThis adaptor specializes SubGraphAdaptor in the way that
557  //xonly the edge-set
558  //xcan be filtered. The usefulness of this adaptor is demonstrated in the
559  //xproblem of searching a maximum number of edge-disjoint shortest paths
560  //xbetween
561  //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.
562  //xnon-negative edge-lengths. Note that
563  //xthe comprehension of the presented solution
564  //xneed's some elementary knowledge from combinatorial optimization.
565  //x
566  //xIf a single shortest path is to be
567  //xsearched between \c s and \c t, then this can be done easily by
568  //xapplying the Dijkstra algorithm. What happens, if a maximum number of
569  //xedge-disjoint shortest paths is to be computed. It can be proved that an
570  //xedge can be in a shortest path if and only
571  //xif it is tight with respect to
572  //xthe potential function computed by Dijkstra.
573  //xMoreover, any path containing
574  //xonly such edges is a shortest one.
575  //xThus we have to compute a maximum number
576  //xof edge-disjoint paths between \c s and \c t in
577  //xthe graph which has edge-set
578  //xall the tight edges. The computation will be demonstrated
579  //xon the following
580  //xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
581  //xThe full source code is available in \ref sub_graph_adaptor_demo.cc.
582  //xIf you are interested in more demo programs, you can use
583  //x\ref dim_to_dot.cc to generate .dot files from dimacs files.
584  //xThe .dot file of the following figure was generated by 
585  //xthe demo program \ref dim_to_dot.cc.
586  //x
587  //x\dot
588  //xdigraph lemon_dot_example {
589  //xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
590  //xn0 [ label="0 (s)" ];
591  //xn1 [ label="1" ];
592  //xn2 [ label="2" ];
593  //xn3 [ label="3" ];
594  //xn4 [ label="4" ];
595  //xn5 [ label="5" ];
596  //xn6 [ label="6 (t)" ];
597  //xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
598  //xn5 ->  n6 [ label="9, length:4" ];
599  //xn4 ->  n6 [ label="8, length:2" ];
600  //xn3 ->  n5 [ label="7, length:1" ];
601  //xn2 ->  n5 [ label="6, length:3" ];
602  //xn2 ->  n6 [ label="5, length:5" ];
603  //xn2 ->  n4 [ label="4, length:2" ];
604  //xn1 ->  n4 [ label="3, length:3" ];
605  //xn0 ->  n3 [ label="2, length:1" ];
606  //xn0 ->  n2 [ label="1, length:2" ];
607  //xn0 ->  n1 [ label="0, length:3" ];
608  //x}
609  //x\enddot
610  //x
611  //x\code
612  //xGraph g;
613  //xNode s, t;
614  //xLengthMap length(g);
615  //x
616  //xreadDimacs(std::cin, g, length, s, t);
617  //x
618  //xcout << "edges with lengths (of form id, source--length->target): " << endl;
619  //xfor(EdgeIt e(g); e!=INVALID; ++e)
620  //x  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
621  //x       << length[e] << "->" << g.id(g.target(e)) << endl;
622  //x
623  //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
624  //x\endcode
625  //xNext, the potential function is computed with Dijkstra.
626  //x\code
627  //xtypedef Dijkstra<Graph, LengthMap> Dijkstra;
628  //xDijkstra dijkstra(g, length);
629  //xdijkstra.run(s);
630  //x\endcode
631  //xNext, we consrtruct a map which filters the edge-set to the tight edges.
632  //x\code
633  //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
634  //x  TightEdgeFilter;
635  //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
636  //x
637  //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
638  //xSubGW gw(g, tight_edge_filter);
639  //x\endcode
640  //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed
641  //xwith a max flow algorithm Preflow.
642  //x\code
643  //xConstMap<Edge, int> const_1_map(1);
644  //xGraph::EdgeMap<int> flow(g, 0);
645  //x
646  //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
647  //x  preflow(gw, s, t, const_1_map, flow);
648  //xpreflow.run();
649  //x\endcode
650  //xLast, the output is:
651  //x\code 
652  //xcout << "maximum number of edge-disjoint shortest path: "
653  //x     << preflow.flowValue() << endl;
654  //xcout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
655  //x     << endl;
656  //xfor(EdgeIt e(g); e!=INVALID; ++e)
657  //x  if (flow[e])
658  //x    cout << " " << g.id(g.source(e)) << "--"
659  //x         << length[e] << "->" << g.id(g.target(e)) << endl;
660  //x\endcode
661  //xThe program has the following (expected :-)) output:
662  //x\code
663  //xedges with lengths (of form id, source--length->target):
664  //x 9, 5--4->6
665  //x 8, 4--2->6
666  //x 7, 3--1->5
667  //x 6, 2--3->5
668  //x 5, 2--5->6
669  //x 4, 2--2->4
670  //x 3, 1--3->4
671  //x 2, 0--1->3
672  //x 1, 0--2->2
673  //x 0, 0--3->1
674  //xs: 0 t: 6
675  //xmaximum number of edge-disjoint shortest path: 2
676  //xedges of the maximum number of edge-disjoint shortest s-t paths:
677  //x 9, 5--4->6
678  //x 8, 4--2->6
679  //x 7, 3--1->5
680  //x 4, 2--2->4
681  //x 2, 0--1->3
682  //x 1, 0--2->2
683  //x\endcode
684  //x
685  //x\author Marton Makai
686  template<typename Graph, typename EdgeFilterMap>
687  class EdgeSubGraphAdaptor :
688    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
689                           EdgeFilterMap, false> {
690  public:
691    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
692                            EdgeFilterMap, false> Parent;
693  protected:
694    ConstMap<typename Graph::Node, bool> const_true_map;
695  public:
696    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
697      Parent(), const_true_map(true) {
698      Parent::setGraph(_graph);
699      Parent::setNodeFilterMap(const_true_map);
700      Parent::setEdgeFilterMap(_edge_filter_map);
701    }
702  };
703
704  template <typename _Graph>
705  class UGraphAdaptorBase :
706    public UGraphExtender<GraphAdaptorBase<_Graph> > {
707  public:
708    typedef _Graph Graph;
709    typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
710  protected:
711    UGraphAdaptorBase() : Parent() { }
712  public:
713    typedef typename Parent::UEdge UEdge;
714    typedef typename Parent::Edge Edge;
715   
716    template <typename T>
717    class EdgeMap {
718    protected:
719      const UGraphAdaptorBase<_Graph>* g;
720      template <typename TT> friend class EdgeMap;
721      typename _Graph::template EdgeMap<T> forward_map, backward_map;
722    public:
723      typedef T Value;
724      typedef Edge Key;
725     
726      EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g),
727        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
728
729      EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
730        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
731     
732      void set(Edge e, T a) {
733        if (g->direction(e))
734          forward_map.set(e, a);
735        else
736          backward_map.set(e, a);
737      }
738
739      T operator[](Edge e) const {
740        if (g->direction(e))
741          return forward_map[e];
742        else
743          return backward_map[e];
744      }
745    };
746       
747    template <typename T>
748    class UEdgeMap {
749      template <typename TT> friend class UEdgeMap;
750      typename _Graph::template EdgeMap<T> map;
751    public:
752      typedef T Value;
753      typedef UEdge Key;
754     
755      UEdgeMap(const UGraphAdaptorBase<_Graph>& g) :
756        map(*(g.graph)) { }
757
758      UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) :
759        map(*(g.graph), a) { }
760     
761      void set(UEdge e, T a) {
762        map.set(e, a);
763      }
764
765      T operator[](UEdge e) const {
766        return map[e];
767      }
768    };
769     
770  };
771
772  //x\brief An undirected graph is made from a directed graph by an adaptor
773  //x\ingroup graph_adaptors
774  //x
775  //x Undocumented, untested!!!
776  //x If somebody knows nice demo application, let's polulate it.
777  //x
778  //x \author Marton Makai
779  template<typename _Graph>
780  class UGraphAdaptor :
781    public IterableUGraphExtender<
782    UGraphAdaptorBase<_Graph> > {
783  public:
784    typedef _Graph Graph;
785    typedef IterableUGraphExtender<
786      UGraphAdaptorBase<_Graph> > Parent;
787  protected:
788    UGraphAdaptor() { }
789  public:
790    UGraphAdaptor(_Graph& _graph) {
791      setGraph(_graph);
792    }
793  };
794
795 
796  template <typename _Graph,
797            typename ForwardFilterMap, typename BackwardFilterMap>
798  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
799  public:
800    typedef _Graph Graph;
801    typedef GraphAdaptorBase<_Graph> Parent;
802  protected:
803    ForwardFilterMap* forward_filter;
804    BackwardFilterMap* backward_filter;
805    SubBidirGraphAdaptorBase() : Parent(),
806                                 forward_filter(0), backward_filter(0) { }
807
808    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
809      forward_filter=&_forward_filter;
810    }
811    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
812      backward_filter=&_backward_filter;
813    }
814
815  public:
816//     SubGraphAdaptorBase(Graph& _graph,
817//                      NodeFilterMap& _node_filter_map,
818//                      EdgeFilterMap& _edge_filter_map) :
819//       Parent(&_graph),
820//       node_filter_map(&node_filter_map),
821//       edge_filter_map(&edge_filter_map) { }
822
823    typedef typename Parent::Node Node;
824    typedef typename _Graph::Edge GraphEdge;
825    template <typename T> class EdgeMap;
826    // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
827    // _Graph::Edge. It contains an extra bool flag which is true
828    // if and only if the
829    // edge is the backward version of the original edge.
830    class Edge : public _Graph::Edge {
831      friend class SubBidirGraphAdaptorBase<
832        Graph, ForwardFilterMap, BackwardFilterMap>;
833      template<typename T> friend class EdgeMap;
834    protected:
835      bool backward; //true, iff backward
836    public:
837      Edge() { }
838      // \todo =false is needed, or causes problems?
839      // If \c _backward is false, then we get an edge corresponding to the
840      // original one, otherwise its oppositely directed pair is obtained.
841      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
842        _Graph::Edge(e), backward(_backward) { }
843      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
844      bool operator==(const Edge& v) const {
845        return (this->backward==v.backward &&
846                static_cast<typename _Graph::Edge>(*this)==
847                static_cast<typename _Graph::Edge>(v));
848      }
849      bool operator!=(const Edge& v) const {
850        return (this->backward!=v.backward ||
851                static_cast<typename _Graph::Edge>(*this)!=
852                static_cast<typename _Graph::Edge>(v));
853      }
854    };
855
856    void first(Node& i) const {
857      Parent::first(i);
858    }
859
860    void first(Edge& i) const {
861      Parent::first(i);
862      i.backward=false;
863      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
864             !(*forward_filter)[i]) Parent::next(i);
865      if (*static_cast<GraphEdge*>(&i)==INVALID) {
866        Parent::first(i);
867        i.backward=true;
868        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
869               !(*backward_filter)[i]) Parent::next(i);
870      }
871    }
872
873    void firstIn(Edge& i, const Node& n) const {
874      Parent::firstIn(i, n);
875      i.backward=false;
876      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
877             !(*forward_filter)[i]) Parent::nextIn(i);
878      if (*static_cast<GraphEdge*>(&i)==INVALID) {
879        Parent::firstOut(i, n);
880        i.backward=true;
881        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
882               !(*backward_filter)[i]) Parent::nextOut(i);
883      }
884    }
885
886    void firstOut(Edge& i, const Node& n) const {
887      Parent::firstOut(i, n);
888      i.backward=false;
889      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
890             !(*forward_filter)[i]) Parent::nextOut(i);
891      if (*static_cast<GraphEdge*>(&i)==INVALID) {
892        Parent::firstIn(i, n);
893        i.backward=true;
894        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
895               !(*backward_filter)[i]) Parent::nextIn(i);
896      }
897    }
898
899    void next(Node& i) const {
900      Parent::next(i);
901    }
902
903    void next(Edge& i) const {
904      if (!(i.backward)) {
905        Parent::next(i);
906        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
907               !(*forward_filter)[i]) Parent::next(i);
908        if (*static_cast<GraphEdge*>(&i)==INVALID) {
909          Parent::first(i);
910          i.backward=true;
911          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
912                 !(*backward_filter)[i]) Parent::next(i);
913        }
914      } else {
915        Parent::next(i);
916        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
917               !(*backward_filter)[i]) Parent::next(i);
918      }
919    }
920
921    void nextIn(Edge& i) const {
922      if (!(i.backward)) {
923        Node n=Parent::target(i);
924        Parent::nextIn(i);
925        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
926               !(*forward_filter)[i]) Parent::nextIn(i);
927        if (*static_cast<GraphEdge*>(&i)==INVALID) {
928          Parent::firstOut(i, n);
929          i.backward=true;
930          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
931                 !(*backward_filter)[i]) Parent::nextOut(i);
932        }
933      } else {
934        Parent::nextOut(i);
935        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
936               !(*backward_filter)[i]) Parent::nextOut(i);
937      }
938    }
939
940    void nextOut(Edge& i) const {
941      if (!(i.backward)) {
942        Node n=Parent::source(i);
943        Parent::nextOut(i);
944        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
945               !(*forward_filter)[i]) Parent::nextOut(i);
946        if (*static_cast<GraphEdge*>(&i)==INVALID) {
947          Parent::firstIn(i, n);
948          i.backward=true;
949          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
950                 !(*backward_filter)[i]) Parent::nextIn(i);
951        }
952      } else {
953        Parent::nextIn(i);
954        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
955               !(*backward_filter)[i]) Parent::nextIn(i);
956      }
957    }
958
959    Node source(Edge e) const {
960      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
961    Node target(Edge e) const {
962      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
963
964    //x Gives back the opposite edge.
965
966    //x\e
967    //x
968    Edge opposite(const Edge& e) const {
969      Edge f=e;
970      f.backward=!f.backward;
971      return f;
972    }
973
974    //x\e
975
976    //x \warning This is a linear time operation and works only if
977    //x \c Graph::EdgeIt is defined.
978    //x \todo hmm
979    int edgeNum() const {
980      int i=0;
981      Edge e;
982      for (first(e); e!=INVALID; next(e)) ++i;
983      return i;
984    }
985
986    bool forward(const Edge& e) const { return !e.backward; }
987    bool backward(const Edge& e) const { return e.backward; }
988
989    //x\e
990
991    //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
992    //x _Graph::EdgeMap one for the forward edges and
993    //x one for the backward edges.
994    template <typename T>
995    class EdgeMap {
996      template <typename TT> friend class EdgeMap;
997      typename _Graph::template EdgeMap<T> forward_map, backward_map;
998    public:
999      typedef T Value;
1000      typedef Edge Key;
1001
1002      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
1003              ForwardFilterMap, BackwardFilterMap>& g) :
1004        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1005
1006      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
1007              ForwardFilterMap, BackwardFilterMap>& g, T a) :
1008        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1009     
1010      void set(Edge e, T a) {
1011        if (!e.backward)
1012          forward_map.set(e, a);
1013        else
1014          backward_map.set(e, a);
1015      }
1016
1017//       typename _Graph::template EdgeMap<T>::ConstReference
1018//       operator[](Edge e) const {
1019//      if (!e.backward)
1020//        return forward_map[e];
1021//      else
1022//        return backward_map[e];
1023//       }
1024
1025//      typename _Graph::template EdgeMap<T>::Reference
1026      T operator[](Edge e) const {
1027        if (!e.backward)
1028          return forward_map[e];
1029        else
1030          return backward_map[e];
1031      }
1032
1033      void update() {
1034        forward_map.update();
1035        backward_map.update();
1036      }
1037    };
1038
1039  };
1040
1041
1042  //x\brief An adaptor for composing a subgraph of a
1043  //x bidirected graph made from a directed one.
1044  //x\ingroup graph_adaptors
1045  //x
1046  //x An adaptor for composing a subgraph of a
1047  //x bidirected graph made from a directed one.
1048  //x
1049  //x\warning Graph adaptors are in even more experimental state
1050  //xthan the other
1051  //xparts of the lib. Use them at you own risk.
1052  //x
1053  //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1054  //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1055  //x reversing its orientation. We are given moreover two bool valued
1056  //x maps on the edge-set,
1057  //x \f$forward\_filter\f$, and \f$backward\_filter\f$.
1058  //x SubBidirGraphAdaptor implements the graph structure with node-set
1059  //x \f$V\f$ and edge-set
1060  //x \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
1061  //x The purpose of writing + instead of union is because parallel
1062  //x edges can arise. (Similarly, antiparallel edges also can arise).
1063  //x In other words, a subgraph of the bidirected graph obtained, which
1064  //x is given by orienting the edges of the original graph in both directions.
1065  //x As the oppositely directed edges are logically different,
1066  //x the maps are able to attach different values for them.
1067  //x
1068  //x An example for such a construction is \c RevGraphAdaptor where the
1069  //x forward_filter is everywhere false and the backward_filter is
1070  //x everywhere true. We note that for sake of efficiency,
1071  //x \c RevGraphAdaptor is implemented in a different way.
1072  //x But BidirGraphAdaptor is obtained from
1073  //x SubBidirGraphAdaptor by considering everywhere true
1074  //x valued maps both for forward_filter and backward_filter.
1075  //x
1076  //x The most important application of SubBidirGraphAdaptor
1077  //x is ResGraphAdaptor, which stands for the residual graph in directed
1078  //x flow and circulation problems.
1079  //x As adaptors usually, the SubBidirGraphAdaptor implements the
1080  //x above mentioned graph structure without its physical storage,
1081  //x that is the whole stuff is stored in constant memory.
1082  template<typename _Graph,
1083           typename ForwardFilterMap, typename BackwardFilterMap>
1084  class SubBidirGraphAdaptor :
1085    public IterableGraphExtender<
1086    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1087  public:
1088    typedef _Graph Graph;
1089    typedef IterableGraphExtender<
1090      SubBidirGraphAdaptorBase<
1091      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1092  protected:
1093    SubBidirGraphAdaptor() { }
1094  public:
1095    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1096                         BackwardFilterMap& _backward_filter) {
1097      setGraph(_graph);
1098      setForwardFilterMap(_forward_filter);
1099      setBackwardFilterMap(_backward_filter);
1100    }
1101  };
1102
1103
1104
1105  //x\brief An adaptor for composing bidirected graph from a directed one.
1106  //x\ingroup graph_adaptors
1107  //x
1108  //x\warning Graph adaptors are in even more experimental state
1109  //xthan the other
1110  //xparts of the lib. Use them at you own risk.
1111  //x
1112  //x An adaptor for composing bidirected graph from a directed one.
1113  //x A bidirected graph is composed over the directed one without physical
1114  //x storage. As the oppositely directed edges are logically different ones
1115  //x the maps are able to attach different values for them.
1116  template<typename Graph>
1117  class BidirGraphAdaptor :
1118    public SubBidirGraphAdaptor<
1119    Graph,
1120    ConstMap<typename Graph::Edge, bool>,
1121    ConstMap<typename Graph::Edge, bool> > {
1122  public:
1123    typedef  SubBidirGraphAdaptor<
1124      Graph,
1125      ConstMap<typename Graph::Edge, bool>,
1126      ConstMap<typename Graph::Edge, bool> > Parent;
1127  protected:
1128    ConstMap<typename Graph::Edge, bool> cm;
1129
1130    BidirGraphAdaptor() : Parent(), cm(true) {
1131      Parent::setForwardFilterMap(cm);
1132      Parent::setBackwardFilterMap(cm);
1133    }
1134  public:
1135    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1136      Parent::setGraph(_graph);
1137      Parent::setForwardFilterMap(cm);
1138      Parent::setBackwardFilterMap(cm);
1139    }
1140
1141    int edgeNum() const {
1142      return 2*this->graph->edgeNum();
1143    }
1144  };
1145
1146
1147  template<typename Graph, typename Number,
1148           typename CapacityMap, typename FlowMap>
1149  class ResForwardFilter {
1150    //    const Graph* graph;
1151    const CapacityMap* capacity;
1152    const FlowMap* flow;
1153  public:
1154    ResForwardFilter(/*const Graph& _graph, */
1155                     const CapacityMap& _capacity, const FlowMap& _flow) :
1156      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1157    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1158    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1159    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1160    bool operator[](const typename Graph::Edge& e) const {
1161      return (Number((*flow)[e]) < Number((*capacity)[e]));
1162    }
1163  };
1164
1165  template<typename Graph, typename Number,
1166           typename CapacityMap, typename FlowMap>
1167  class ResBackwardFilter {
1168    const CapacityMap* capacity;
1169    const FlowMap* flow;
1170  public:
1171    ResBackwardFilter(/*const Graph& _graph,*/
1172                      const CapacityMap& _capacity, const FlowMap& _flow) :
1173      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1174    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1175    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1176    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1177    bool operator[](const typename Graph::Edge& e) const {
1178      return (Number(0) < Number((*flow)[e]));
1179    }
1180  };
1181
1182 
1183  //x\brief An adaptor for composing the residual
1184  //xgraph for directed flow and circulation problems.
1185  //x\ingroup graph_adaptors
1186  //x
1187  //xAn adaptor for composing the residual graph for
1188  //xdirected flow and circulation problems.
1189  //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1190  //xnumber type. Let moreover
1191  //x\f$f,c:A\to F\f$, be functions on the edge-set.
1192  //xIn the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1193  //xand \f$c\f$ for a capacity function.   
1194  //xSuppose that a graph instange \c g of type
1195  //x\c ListGraph implements \f$G\f$ .
1196  //x\code
1197  //x  ListGraph g;
1198  //x\endcode
1199  //xThen RevGraphAdaptor implements the graph structure with node-set
1200  //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1201  //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1202  //x\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1203  //xi.e. the so called residual graph.
1204  //xWhen we take the union \f$A_{forward}\cup A_{backward}\f$,
1205  //xmultilicities are counted, i.e. if an edge is in both
1206  //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1207  //xappears twice.
1208  //xThe following code shows how
1209  //xsuch an instance can be constructed.
1210  //x\code
1211  //xtypedef ListGraph Graph;
1212  //xGraph::EdgeMap<int> f(g);
1213  //xGraph::EdgeMap<int> c(g);
1214  //xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1215  //x\endcode
1216  //x\author Marton Makai
1217  //x
1218  template<typename Graph, typename Number,
1219           typename CapacityMap, typename FlowMap>
1220  class ResGraphAdaptor :
1221    public SubBidirGraphAdaptor<
1222    Graph,
1223    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1224    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1225  public:
1226    typedef SubBidirGraphAdaptor<
1227      Graph,
1228      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1229      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1230  protected:
1231    const CapacityMap* capacity;
1232    FlowMap* flow;
1233    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1234    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1235    ResGraphAdaptor() : Parent(),
1236                        capacity(0), flow(0) { }
1237    void setCapacityMap(const CapacityMap& _capacity) {
1238      capacity=&_capacity;
1239      forward_filter.setCapacity(_capacity);
1240      backward_filter.setCapacity(_capacity);
1241    }
1242    void setFlowMap(FlowMap& _flow) {
1243      flow=&_flow;
1244      forward_filter.setFlow(_flow);
1245      backward_filter.setFlow(_flow);
1246    }
1247  public:
1248    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1249                       FlowMap& _flow) :
1250      Parent(), capacity(&_capacity), flow(&_flow),
1251      forward_filter(/*_graph,*/ _capacity, _flow),
1252      backward_filter(/*_graph,*/ _capacity, _flow) {
1253      Parent::setGraph(_graph);
1254      Parent::setForwardFilterMap(forward_filter);
1255      Parent::setBackwardFilterMap(backward_filter);
1256    }
1257
1258    typedef typename Parent::Edge Edge;
1259
1260    void augment(const Edge& e, Number a) const {
1261      if (Parent::forward(e)) 
1262        flow->set(e, (*flow)[e]+a);
1263      else 
1264        flow->set(e, (*flow)[e]-a);
1265    }
1266
1267    //x \brief Residual capacity map.
1268    //x
1269    //x In generic residual graphs the residual capacity can be obtained
1270    //x as a map.
1271    class ResCap {
1272    protected:
1273      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1274    public:
1275      typedef Number Value;
1276      typedef Edge Key;
1277      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1278             _res_graph) : res_graph(&_res_graph) { }
1279      Number operator[](const Edge& e) const {
1280        if (res_graph->forward(e))
1281          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1282        else
1283          return (*(res_graph->flow))[e];
1284      }
1285    };
1286
1287    //    KEEP_MAPS(Parent, ResGraphAdaptor);
1288  };
1289
1290
1291
1292  template <typename _Graph, typename FirstOutEdgesMap>
1293  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1294  public:
1295    typedef _Graph Graph;
1296    typedef GraphAdaptorBase<_Graph> Parent;
1297  protected:
1298    FirstOutEdgesMap* first_out_edges;
1299    ErasingFirstGraphAdaptorBase() : Parent(),
1300                                     first_out_edges(0) { }
1301
1302    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1303      first_out_edges=&_first_out_edges;
1304    }
1305
1306  public:
1307
1308    typedef typename Parent::Node Node;
1309    typedef typename Parent::Edge Edge;
1310
1311    void firstOut(Edge& i, const Node& n) const {
1312      i=(*first_out_edges)[n];
1313    }
1314
1315    void erase(const Edge& e) const {
1316      Node n=source(e);
1317      Edge f=e;
1318      Parent::nextOut(f);
1319      first_out_edges->set(n, f);
1320    }   
1321  };
1322
1323
1324  //x\brief For blocking flows.
1325  //x\ingroup graph_adaptors
1326  //x
1327  //x\warning Graph adaptors are in even more
1328  //xexperimental state than the other
1329  //xparts of the lib. Use them at you own risk.
1330  //x
1331  //xThis graph adaptor is used for on-the-fly
1332  //xDinits blocking flow computations.
1333  //xFor each node, an out-edge is stored which is used when the
1334  //x\code
1335  //xOutEdgeIt& first(OutEdgeIt&, const Node&)
1336  //x\endcode
1337  //xis called.
1338  //x
1339  //x\author Marton Makai
1340  //x
1341  template <typename _Graph, typename FirstOutEdgesMap>
1342  class ErasingFirstGraphAdaptor :
1343    public IterableGraphExtender<
1344    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1345  public:
1346    typedef _Graph Graph;
1347    typedef IterableGraphExtender<
1348      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1349    ErasingFirstGraphAdaptor(Graph& _graph,
1350                             FirstOutEdgesMap& _first_out_edges) {
1351      setGraph(_graph);
1352      setFirstOutEdgesMap(_first_out_edges);
1353    }
1354
1355  };
1356
1357  template <typename _Graph>
1358  class SplitGraphAdaptorBase
1359    : public GraphAdaptorBase<_Graph> {
1360  public:
1361    typedef GraphAdaptorBase<_Graph> Parent;
1362
1363    class Node;
1364    class Edge;
1365    template <typename T> class NodeMap;
1366    template <typename T> class EdgeMap;
1367   
1368
1369    class Node : public Parent::Node {
1370      friend class SplitGraphAdaptorBase;
1371      template <typename T> friend class NodeMap;
1372      typedef typename Parent::Node NodeParent;
1373    private:
1374
1375      bool entry;
1376      Node(typename Parent::Node _node, bool _entry)
1377        : Parent::Node(_node), entry(_entry) {}
1378     
1379    public:
1380      Node() {}
1381      Node(Invalid) : NodeParent(INVALID), entry(true) {}
1382
1383      bool operator==(const Node& node) const {
1384        return NodeParent::operator==(node) && entry == node.entry;
1385      }
1386     
1387      bool operator!=(const Node& node) const {
1388        return !(*this == node);
1389      }
1390     
1391      bool operator<(const Node& node) const {
1392        return NodeParent::operator<(node) ||
1393          (NodeParent::operator==(node) && entry < node.entry);
1394      }
1395    };
1396
1397    //x \todo May we want VARIANT/union type
1398    class Edge : public Parent::Edge {
1399      friend class SplitGraphAdaptorBase;
1400      template <typename T> friend class EdgeMap;
1401    private:
1402      typedef typename Parent::Edge EdgeParent;
1403      typedef typename Parent::Node NodeParent;
1404      NodeParent bind;
1405
1406      Edge(const EdgeParent& edge, const NodeParent& node)
1407        : EdgeParent(edge), bind(node) {}
1408    public:
1409      Edge() {}
1410      Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1411
1412      bool operator==(const Edge& edge) const {
1413        return EdgeParent::operator==(edge) && bind == edge.bind;
1414      }
1415     
1416      bool operator!=(const Edge& edge) const {
1417        return !(*this == edge);
1418      }
1419     
1420      bool operator<(const Edge& edge) const {
1421        return EdgeParent::operator<(edge) ||
1422          (EdgeParent::operator==(edge) && bind < edge.bind);
1423      }
1424    };
1425
1426    void first(Node& node) const {
1427      Parent::first(node);
1428      node.entry = true;
1429    }
1430
1431    void next(Node& node) const {
1432      if (node.entry) {
1433        node.entry = false;
1434      } else {
1435        node.entry = true;
1436        Parent::next(node);
1437      }
1438    }
1439
1440    void first(Edge& edge) const {
1441      Parent::first(edge);
1442      if ((typename Parent::Edge&)edge == INVALID) {
1443        Parent::first(edge.bind);
1444      } else {
1445        edge.bind = INVALID;
1446      }
1447    }
1448
1449    void next(Edge& edge) const {
1450      if ((typename Parent::Edge&)edge != INVALID) {
1451        Parent::next(edge);
1452        if ((typename Parent::Edge&)edge == INVALID) {
1453          Parent::first(edge.bind);
1454        }
1455      } else {
1456        Parent::next(edge.bind);
1457      }     
1458    }
1459
1460    void firstIn(Edge& edge, const Node& node) const {
1461      if (node.entry) {
1462        Parent::firstIn(edge, node);
1463        edge.bind = INVALID;
1464      } else {
1465        (typename Parent::Edge&)edge = INVALID;
1466        edge.bind = node;
1467      }
1468    }
1469
1470    void nextIn(Edge& edge) const {
1471      if ((typename Parent::Edge&)edge != INVALID) {
1472        Parent::nextIn(edge);
1473      } else {
1474        edge.bind = INVALID;
1475      }     
1476    }
1477
1478    void firstOut(Edge& edge, const Node& node) const {
1479      if (!node.entry) {
1480        Parent::firstOut(edge, node);
1481        edge.bind = INVALID;
1482      } else {
1483        (typename Parent::Edge&)edge = INVALID;
1484        edge.bind = node;
1485      }
1486    }
1487
1488    void nextOut(Edge& edge) const {
1489      if ((typename Parent::Edge&)edge != INVALID) {
1490        Parent::nextOut(edge);
1491      } else {
1492        edge.bind = INVALID;
1493      }
1494    }
1495
1496    Node source(const Edge& edge) const {
1497      if ((typename Parent::Edge&)edge != INVALID) {
1498        return Node(Parent::source(edge), false);
1499      } else {
1500        return Node(edge.bind, true);
1501      }
1502    }
1503
1504    Node target(const Edge& edge) const {
1505      if ((typename Parent::Edge&)edge != INVALID) {
1506        return Node(Parent::target(edge), true);
1507      } else {
1508        return Node(edge.bind, false);
1509      }
1510    }
1511
1512    static bool entryNode(const Node& node) {
1513      return node.entry;
1514    }
1515
1516    static bool exitNode(const Node& node) {
1517      return !node.entry;
1518    }
1519
1520    static Node getEntry(const typename Parent::Node& node) {
1521      return Node(node, true);
1522    }
1523
1524    static Node getExit(const typename Parent::Node& node) {
1525      return Node(node, false);
1526    }
1527
1528    static bool originalEdge(const Edge& edge) {
1529      return (typename Parent::Edge&)edge != INVALID;
1530    }
1531
1532    static bool bindingEdge(const Edge& edge) {
1533      return edge.bind != INVALID;
1534    }
1535
1536    static Node getBindedNode(const Edge& edge) {
1537      return edge.bind;
1538    }
1539
1540    int nodeNum() const {
1541      return Parent::nodeNum() * 2;
1542    }
1543
1544    typedef CompileTimeAnd<typename Parent::NodeNumTag,
1545                           typename Parent::EdgeNumTag> EdgeNumTag;
1546   
1547    int edgeNum() const {
1548      return Parent::edgeNum() + Parent::nodeNum();
1549    }
1550
1551    Edge findEdge(const Node& source, const Node& target,
1552                  const Edge& prev = INVALID) const {
1553      if (exitNode(source) && entryNode(target)) {
1554        return Parent::findEdge(source, target, prev);
1555      } else {
1556        if (prev == INVALID && entryNode(source) && exitNode(target) &&
1557            (typename Parent::Node&)source == (typename Parent::Node&)target) {
1558          return Edge(INVALID, source);
1559        } else {
1560          return INVALID;
1561        }
1562      }
1563    }
1564   
1565    template <typename T>
1566    class NodeMap : public MapBase<Node, T> {
1567      typedef typename Parent::template NodeMap<T> NodeImpl;
1568    public:
1569      NodeMap(const SplitGraphAdaptorBase& _graph)
1570        : entry(_graph), exit(_graph) {}
1571      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1572        : entry(_graph, t), exit(_graph, t) {}
1573     
1574      void set(const Node& key, const T& val) {
1575        if (key.entry) { entry.set(key, val); }
1576        else {exit.set(key, val); }
1577      }
1578     
1579      typename MapTraits<NodeImpl>::ReturnValue
1580      operator[](const Node& key) {
1581        if (key.entry) { return entry[key]; }
1582        else { return exit[key]; }
1583      }
1584
1585      typename MapTraits<NodeImpl>::ConstReturnValue
1586      operator[](const Node& key) const {
1587        if (key.entry) { return entry[key]; }
1588        else { return exit[key]; }
1589      }
1590
1591    private:
1592      NodeImpl entry, exit;
1593    };
1594
1595    template <typename T>
1596    class EdgeMap : public MapBase<Edge, T> {
1597      typedef typename Parent::template NodeMap<T> NodeImpl;
1598      typedef typename Parent::template EdgeMap<T> EdgeImpl;
1599    public:
1600      EdgeMap(const SplitGraphAdaptorBase& _graph)
1601        : bind(_graph), orig(_graph) {}
1602      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1603        : bind(_graph, t), orig(_graph, t) {}
1604     
1605      void set(const Edge& key, const T& val) {
1606        if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1607        else {bind.set(key.bind, val); }
1608      }
1609     
1610      typename MapTraits<EdgeImpl>::ReturnValue
1611      operator[](const Edge& key) {
1612        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1613        else {return bind[key.bind]; }
1614      }
1615
1616      typename MapTraits<EdgeImpl>::ConstReturnValue
1617      operator[](const Edge& key) const {
1618        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1619        else {return bind[key.bind]; }
1620      }
1621
1622    private:
1623      typename Parent::template NodeMap<T> bind;
1624      typename Parent::template EdgeMap<T> orig;
1625    };
1626
1627    template <typename EntryMap, typename ExitMap>
1628    class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1629    public:
1630      typedef MapBase<Node, typename EntryMap::Value> Parent;
1631
1632      typedef typename Parent::Key Key;
1633      typedef typename Parent::Value Value;
1634
1635      CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1636        : entryMap(_entryMap), exitMap(_exitMap) {}
1637
1638      Value& operator[](const Key& key) {
1639        if (key.entry) {
1640          return entryMap[key];
1641        } else {
1642          return exitMap[key];
1643        }
1644      }
1645
1646      Value operator[](const Key& key) const {
1647        if (key.entry) {
1648          return entryMap[key];
1649        } else {
1650          return exitMap[key];
1651        }
1652      }
1653
1654      void set(const Key& key, const Value& value) {
1655        if (key.entry) {
1656          entryMap.set(key, value);
1657        } else {
1658          exitMap.set(key, value);
1659        }
1660      }
1661     
1662    private:
1663     
1664      EntryMap& entryMap;
1665      ExitMap& exitMap;
1666     
1667    };
1668
1669    template <typename EdgeMap, typename NodeMap>
1670    class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
1671    public:
1672      typedef MapBase<Edge, typename EdgeMap::Value> Parent;
1673
1674      typedef typename Parent::Key Key;
1675      typedef typename Parent::Value Value;
1676
1677      CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
1678        : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
1679
1680      void set(const Edge& edge, const Value& val) {
1681        if (SplitGraphAdaptorBase::originalEdge(edge)) {
1682          edgeMap.set(edge, val);
1683        } else {
1684          nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
1685        }
1686      }
1687
1688      Value operator[](const Key& edge) const {
1689        if (SplitGraphAdaptorBase::originalEdge(edge)) {
1690          return edgeMap[edge];
1691        } else {
1692          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1693        }
1694      }     
1695
1696      Value& operator[](const Key& edge) {
1697        if (SplitGraphAdaptorBase::originalEdge(edge)) {
1698          return edgeMap[edge];
1699        } else {
1700          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1701        }
1702      }     
1703     
1704    private:
1705      EdgeMap& edgeMap;
1706      NodeMap& nodeMap;
1707    };
1708
1709  };
1710
1711  template <typename _Graph>
1712  class SplitGraphAdaptor
1713    : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
1714  public:
1715    typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1716
1717    SplitGraphAdaptor(_Graph& graph) {
1718      Parent::setGraph(graph);
1719    }
1720
1721
1722  };
1723
1724} //namespace lemon
1725
1726#endif //LEMON_GRAPH_ADAPTOR_H
1727
Note: See TracBrowser for help on using the repository browser.