COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1992:6e1b62d42d94

Last change on this file since 1992:6e1b62d42d94 was 1991:d7442141d9ef, checked in by Balazs Dezso, 18 years ago

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

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/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.