COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1999:2ff283124dfc

Last change on this file since 1999:2ff283124dfc was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

Clarifing alteration observing system
It is directly connected now to a container

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