COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

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