COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2083:f50c8c191cbd

Last change on this file since 2083:f50c8c191cbd was 2081:94a7deb46c07, checked in by Balazs Dezso, 14 years ago

New demo file for computing disjoint paths

Doc review

Correcting misformatting in adaptors
Adding header to demos

File size: 77.1 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 and Balazs Dezso
29
30#include <lemon/bits/invalid.h>
31#include <lemon/maps.h>
32
33#include <lemon/bits/base_extender.h>
34#include <lemon/bits/graph_adaptor_extender.h>
35#include <lemon/bits/graph_extender.h>
36
37#include <lemon/tolerance.h>
38
39#include <algorithm>
40
41namespace lemon {
42
43  ///\brief Base type for the Graph Adaptors
44  ///
45  ///Base type for the Graph Adaptors
46  ///
47  ///This is the base type for most of LEMON graph adaptors.
48  ///This class implements a trivial graph adaptor i.e. it only wraps the
49  ///functions and types of the graph. The purpose of this class is to
50  ///make easier implementing graph adaptors. E.g. if an adaptor is
51  ///considered which differs from the wrapped graph only in some of its
52  ///functions or types, then it can be derived from GraphAdaptor,
53  ///and only the
54  ///differences should be implemented.
55  ///
56  ///author Marton Makai
57  template<typename _Graph>
58  class GraphAdaptorBase {
59  public:
60    typedef _Graph Graph;
61    typedef GraphAdaptorBase Adaptor;
62    typedef Graph ParentGraph;
63
64  protected:
65    Graph* graph;
66    GraphAdaptorBase() : graph(0) { }
67    void setGraph(Graph& _graph) { graph=&_graph; }
68
69  public:
70    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
71
72    typedef typename Graph::Node Node;
73    typedef typename Graph::Edge Edge;
74   
75    void first(Node& i) const { graph->first(i); }
76    void first(Edge& i) const { graph->first(i); }
77    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
78    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
79
80    void next(Node& i) const { graph->next(i); }
81    void next(Edge& i) const { graph->next(i); }
82    void nextIn(Edge& i) const { graph->nextIn(i); }
83    void nextOut(Edge& i) const { graph->nextOut(i); }
84
85    Node source(const Edge& e) const { return graph->source(e); }
86    Node target(const Edge& e) const { return graph->target(e); }
87
88    typedef NodeNumTagIndicator<Graph> NodeNumTag;
89    int nodeNum() const { return graph->nodeNum(); }
90   
91    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
92    int edgeNum() const { return graph->edgeNum(); }
93
94    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
95    Edge findEdge(const Node& source, const Node& target,
96                  const Edge& prev = INVALID) {
97      return graph->findEdge(source, target, prev);
98    }
99 
100    Node addNode() const {
101      return Node(graph->addNode());
102    }
103
104    Edge addEdge(const Node& source, const Node& target) const {
105      return Edge(graph->addEdge(source, target));
106    }
107
108    void erase(const Node& i) const { graph->erase(i); }
109    void erase(const Edge& i) const { graph->erase(i); }
110 
111    void clear() const { graph->clear(); }
112   
113    int id(const Node& v) const { return graph->id(v); }
114    int id(const Edge& e) const { return graph->id(e); }
115
116    Node fromNodeId(int id) const {
117      return graph->fromNodeId(id);
118    }
119
120    Edge fromEdgeId(int id) const {
121      return graph->fromEdgeId(id);
122    }
123
124    int maxNodeId() const {
125      return graph->maxNodeId();
126    }
127
128    int maxEdgeId() const {
129      return graph->maxEdgeId();
130    }
131
132    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
133
134    NodeNotifier& getNotifier(Node) const {
135      return graph->getNotifier(Node());
136    }
137
138    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
139
140    EdgeNotifier& getNotifier(Edge) const {
141      return graph->getNotifier(Edge());
142    }
143   
144    template <typename _Value>
145    class NodeMap : public Graph::template NodeMap<_Value> {
146    public:
147
148      typedef typename Graph::template NodeMap<_Value> Parent;
149
150      explicit NodeMap(const Adaptor& ga)
151        : Parent(*ga.graph) {}
152
153      NodeMap(const Adaptor& ga, const _Value& value)
154        : Parent(*ga.graph, value) { }
155
156      NodeMap& operator=(const NodeMap& cmap) {
157        return operator=<NodeMap>(cmap);
158      }
159
160      template <typename CMap>
161      NodeMap& operator=(const CMap& cmap) {
162        Parent::operator=(cmap);
163        return *this;
164      }
165     
166    };
167
168    template <typename _Value>
169    class EdgeMap : public Graph::template EdgeMap<_Value> {
170    public:
171     
172      typedef typename Graph::template EdgeMap<_Value> Parent;
173     
174      explicit EdgeMap(const Adaptor& ga)
175        : Parent(*ga.graph) {}
176
177      EdgeMap(const Adaptor& ga, const _Value& value)
178        : Parent(*ga.graph, value) {}
179
180      EdgeMap& operator=(const EdgeMap& cmap) {
181        return operator=<EdgeMap>(cmap);
182      }
183
184      template <typename CMap>
185      EdgeMap& operator=(const CMap& cmap) {
186        Parent::operator=(cmap);
187        return *this;
188      }
189
190    };
191
192  };
193
194  ///\ingroup graph_adaptors
195  ///
196  ///\brief Trivial Graph Adaptor
197  ///
198  /// This class is an adaptor which does not change the adapted graph.
199  /// It can be used only to test the graph adaptors.
200  template <typename _Graph>
201  class GraphAdaptor :
202    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
203  public:
204    typedef _Graph Graph;
205    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
206  protected:
207    GraphAdaptor() : Parent() { }
208
209  public:
210    explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
211  };
212
213  /// \brief Just gives back a graph adaptor
214  ///
215  /// Just gives back a graph adaptor which
216  /// should be provide original graph
217  template<typename Graph>
218  GraphAdaptor<const Graph>
219  graphAdaptor(const Graph& graph) {
220    return GraphAdaptor<const Graph>(graph);
221  }
222
223
224  template <typename _Graph>
225  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
226  public:
227    typedef _Graph Graph;
228    typedef GraphAdaptorBase<_Graph> Parent;
229  protected:
230    RevGraphAdaptorBase() : Parent() { }
231  public:
232    typedef typename Parent::Node Node;
233    typedef typename Parent::Edge Edge;
234
235    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
236    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
237
238    void nextIn(Edge& i) const { Parent::nextOut(i); }
239    void nextOut(Edge& i) const { Parent::nextIn(i); }
240
241    Node source(const Edge& e) const { return Parent::target(e); }
242    Node target(const Edge& e) const { return Parent::source(e); }
243
244    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
245    Edge findEdge(const Node& source, const Node& target,
246                  const Edge& prev = INVALID) {
247      return Parent::findEdge(target, source, prev);
248    }
249
250  };
251   
252
253  ///\ingroup graph_adaptors
254  ///
255  ///\brief A graph adaptor which reverses the orientation of the edges.
256  ///
257  /// If \c g is defined as
258  ///\code
259  /// ListGraph g;
260  ///\endcode
261  /// then
262  ///\code
263  /// RevGraphAdaptor<ListGraph> ga(g);
264  ///\endcode
265  /// implements the graph obtained from \c g by
266  /// reversing the orientation of its edges.
267  template<typename _Graph>
268  class RevGraphAdaptor :
269    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
270  public:
271    typedef _Graph Graph;
272    typedef GraphAdaptorExtender<
273      RevGraphAdaptorBase<_Graph> > Parent;
274  protected:
275    RevGraphAdaptor() { }
276  public:
277    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
278  };
279
280  /// \brief Just gives back a reverse graph adaptor
281  ///
282  /// Just gives back a reverse graph adaptor
283  template<typename Graph>
284  RevGraphAdaptor<const Graph>
285  revGraphAdaptor(const Graph& graph) {
286    return RevGraphAdaptor<const Graph>(graph);
287  }
288
289  template <typename _Graph, typename NodeFilterMap,
290            typename EdgeFilterMap, bool checked = true>
291  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
292  public:
293    typedef _Graph Graph;
294    typedef SubGraphAdaptorBase Adaptor;
295    typedef GraphAdaptorBase<_Graph> Parent;
296  protected:
297    NodeFilterMap* node_filter_map;
298    EdgeFilterMap* edge_filter_map;
299    SubGraphAdaptorBase() : Parent(),
300                            node_filter_map(0), edge_filter_map(0) { }
301
302    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
303      node_filter_map=&_node_filter_map;
304    }
305    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
306      edge_filter_map=&_edge_filter_map;
307    }
308
309  public:
310
311    typedef typename Parent::Node Node;
312    typedef typename Parent::Edge Edge;
313
314    void first(Node& i) const {
315      Parent::first(i);
316      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
317    }
318
319    void first(Edge& i) const {
320      Parent::first(i);
321      while (i!=INVALID && (!(*edge_filter_map)[i]
322             || !(*node_filter_map)[Parent::source(i)]
323             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
324    }
325
326    void firstIn(Edge& i, const Node& n) const {
327      Parent::firstIn(i, n);
328      while (i!=INVALID && (!(*edge_filter_map)[i]
329             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
330    }
331
332    void firstOut(Edge& i, const Node& n) const {
333      Parent::firstOut(i, n);
334      while (i!=INVALID && (!(*edge_filter_map)[i]
335             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
336    }
337
338    void next(Node& i) const {
339      Parent::next(i);
340      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
341    }
342
343    void next(Edge& i) const {
344      Parent::next(i);
345      while (i!=INVALID && (!(*edge_filter_map)[i]
346             || !(*node_filter_map)[Parent::source(i)]
347             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
348    }
349
350    void nextIn(Edge& i) const {
351      Parent::nextIn(i);
352      while (i!=INVALID && (!(*edge_filter_map)[i]
353             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
354    }
355
356    void nextOut(Edge& i) const {
357      Parent::nextOut(i);
358      while (i!=INVALID && (!(*edge_filter_map)[i]
359             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
360    }
361
362    ///\e
363
364    /// This function hides \c n in the graph, i.e. the iteration
365    /// jumps over it. This is done by simply setting the value of \c n 
366    /// to be false in the corresponding node-map.
367    void hide(const Node& n) const { node_filter_map->set(n, false); }
368
369    ///\e
370
371    /// This function hides \c e in the graph, i.e. the iteration
372    /// jumps over it. This is done by simply setting the value of \c e 
373    /// to be false in the corresponding edge-map.
374    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
375
376    ///\e
377
378    /// The value of \c n is set to be true in the node-map which stores
379    /// hide information. If \c n was hidden previuosly, then it is shown
380    /// again
381     void unHide(const Node& n) const { node_filter_map->set(n, true); }
382
383    ///\e
384
385    /// The value of \c e is set to be true in the edge-map which stores
386    /// hide information. If \c e was hidden previuosly, then it is shown
387    /// again
388    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
389
390    /// Returns true if \c n is hidden.
391   
392    ///\e
393    ///
394    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
395
396    /// Returns true if \c n is hidden.
397   
398    ///\e
399    ///
400    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
401
402    typedef False NodeNumTag;
403    typedef False EdgeNumTag;
404
405    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
406    Edge findEdge(const Node& source, const Node& target,
407                  const Edge& prev = INVALID) {
408      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
409        return INVALID;
410      }
411      Edge edge = Parent::findEdge(source, target, prev);
412      while (edge != INVALID && !(*edge_filter_map)[edge]) {
413        edge = Parent::findEdge(source, target, edge);
414      }
415      return edge;
416    }
417
418    template <typename _Value>
419    class NodeMap
420      : public SubMapExtender<Adaptor,
421                              typename Parent::template NodeMap<_Value> >
422    {
423    public:
424      typedef Adaptor Graph;
425      typedef SubMapExtender<Adaptor, typename Parent::
426                             template NodeMap<_Value> > Parent;
427   
428      NodeMap(const Graph& graph)
429        : Parent(graph) {}
430      NodeMap(const Graph& graph, const _Value& value)
431        : Parent(graph, value) {}
432   
433      NodeMap& operator=(const NodeMap& cmap) {
434        return operator=<NodeMap>(cmap);
435      }
436   
437      template <typename CMap>
438      NodeMap& operator=(const CMap& cmap) {
439        Parent::operator=(cmap);
440        return *this;
441      }
442    };
443
444    template <typename _Value>
445    class EdgeMap
446      : public SubMapExtender<Adaptor,
447                              typename Parent::template EdgeMap<_Value> >
448    {
449    public:
450      typedef Adaptor Graph;
451      typedef SubMapExtender<Adaptor, typename Parent::
452                             template EdgeMap<_Value> > Parent;
453   
454      EdgeMap(const Graph& graph)
455        : Parent(graph) {}
456      EdgeMap(const Graph& graph, const _Value& value)
457        : Parent(graph, value) {}
458   
459      EdgeMap& operator=(const EdgeMap& cmap) {
460        return operator=<EdgeMap>(cmap);
461      }
462   
463      template <typename CMap>
464      EdgeMap& operator=(const CMap& cmap) {
465        Parent::operator=(cmap);
466        return *this;
467      }
468    };
469
470  };
471
472  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
473  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
474    : public GraphAdaptorBase<_Graph> {
475  public:
476    typedef _Graph Graph;
477    typedef SubGraphAdaptorBase Adaptor;
478    typedef GraphAdaptorBase<_Graph> Parent;
479  protected:
480    NodeFilterMap* node_filter_map;
481    EdgeFilterMap* edge_filter_map;
482    SubGraphAdaptorBase() : Parent(),
483                            node_filter_map(0), edge_filter_map(0) { }
484
485    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
486      node_filter_map=&_node_filter_map;
487    }
488    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
489      edge_filter_map=&_edge_filter_map;
490    }
491
492  public:
493
494    typedef typename Parent::Node Node;
495    typedef typename Parent::Edge Edge;
496
497    void first(Node& i) const {
498      Parent::first(i);
499      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
500    }
501
502    void first(Edge& i) const {
503      Parent::first(i);
504      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
505    }
506
507    void firstIn(Edge& i, const Node& n) const {
508      Parent::firstIn(i, n);
509      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
510    }
511
512    void firstOut(Edge& i, const Node& n) const {
513      Parent::firstOut(i, n);
514      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
515    }
516
517    void next(Node& i) const {
518      Parent::next(i);
519      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
520    }
521    void next(Edge& i) const {
522      Parent::next(i);
523      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
524    }
525    void nextIn(Edge& i) const {
526      Parent::nextIn(i);
527      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
528    }
529
530    void nextOut(Edge& i) const {
531      Parent::nextOut(i);
532      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
533    }
534
535    ///\e
536
537    /// This function hides \c n in the graph, i.e. the iteration
538    /// jumps over it. This is done by simply setting the value of \c n 
539    /// to be false in the corresponding node-map.
540    void hide(const Node& n) const { node_filter_map->set(n, false); }
541
542    ///\e
543
544    /// This function hides \c e in the graph, i.e. the iteration
545    /// jumps over it. This is done by simply setting the value of \c e 
546    /// to be false in the corresponding edge-map.
547    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
548
549    ///\e
550
551    /// The value of \c n is set to be true in the node-map which stores
552    /// hide information. If \c n was hidden previuosly, then it is shown
553    /// again
554     void unHide(const Node& n) const { node_filter_map->set(n, true); }
555
556    ///\e
557
558    /// The value of \c e is set to be true in the edge-map which stores
559    /// hide information. If \c e was hidden previuosly, then it is shown
560    /// again
561    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
562
563    /// Returns true if \c n is hidden.
564   
565    ///\e
566    ///
567    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
568
569    /// Returns true if \c n is hidden.
570   
571    ///\e
572    ///
573    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
574
575    typedef False NodeNumTag;
576    typedef False EdgeNumTag;
577
578    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
579    Edge findEdge(const Node& source, const Node& target,
580                  const Edge& prev = INVALID) {
581      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
582        return INVALID;
583      }
584      Edge edge = Parent::findEdge(source, target, prev);
585      while (edge != INVALID && !(*edge_filter_map)[edge]) {
586        edge = Parent::findEdge(source, target, edge);
587      }
588      return edge;
589    }
590
591    template <typename _Value>
592    class NodeMap
593      : public SubMapExtender<Adaptor,
594                              typename Parent::template NodeMap<_Value> >
595    {
596    public:
597      typedef Adaptor Graph;
598      typedef SubMapExtender<Adaptor, typename Parent::
599                             template NodeMap<_Value> > Parent;
600   
601      NodeMap(const Graph& graph)
602        : Parent(graph) {}
603      NodeMap(const Graph& graph, const _Value& value)
604        : Parent(graph, value) {}
605   
606      NodeMap& operator=(const NodeMap& cmap) {
607        return operator=<NodeMap>(cmap);
608      }
609   
610      template <typename CMap>
611      NodeMap& operator=(const CMap& cmap) {
612        Parent::operator=(cmap);
613        return *this;
614      }
615    };
616
617    template <typename _Value>
618    class EdgeMap
619      : public SubMapExtender<Adaptor,
620                              typename Parent::template EdgeMap<_Value> >
621    {
622    public:
623      typedef Adaptor Graph;
624      typedef SubMapExtender<Adaptor, typename Parent::
625                             template EdgeMap<_Value> > Parent;
626   
627      EdgeMap(const Graph& graph)
628        : Parent(graph) {}
629      EdgeMap(const Graph& graph, const _Value& value)
630        : Parent(graph, value) {}
631   
632      EdgeMap& operator=(const EdgeMap& cmap) {
633        return operator=<EdgeMap>(cmap);
634      }
635   
636      template <typename CMap>
637      EdgeMap& operator=(const CMap& cmap) {
638        Parent::operator=(cmap);
639        return *this;
640      }
641    };
642
643  };
644
645  /// \ingroup graph_adaptors
646  ///
647  /// \brief A graph adaptor for hiding nodes and edges from a graph.
648  ///
649  /// SubGraphAdaptor shows the graph with filtered node-set and
650  /// edge-set. If the \c checked parameter is true then it filters the edgeset
651  /// to do not get invalid edges without source or target.
652  /// Let \f$ G=(V, A) \f$ be a directed graph
653  /// and suppose that the graph instance \c g of type ListGraph
654  /// implements \f$ G \f$.
655  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
656  /// on the node-set and edge-set.
657  /// SubGraphAdaptor<...>::NodeIt iterates
658  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
659  /// SubGraphAdaptor<...>::EdgeIt iterates
660  /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
661  /// SubGraphAdaptor<...>::OutEdgeIt and
662  /// SubGraphAdaptor<...>::InEdgeIt iterates
663  /// only on edges leaving and entering a specific node which have true value.
664  ///
665  /// If the \c checked template parameter is false then we have to note that
666  /// the node-iterator cares only the filter on the node-set, and the
667  /// edge-iterator cares only the filter on the edge-set.
668  /// This way the edge-map
669  /// should filter all edges which's source or target is filtered by the
670  /// node-filter.
671  ///\code
672  /// typedef ListGraph Graph;
673  /// Graph g;
674  /// typedef Graph::Node Node;
675  /// typedef Graph::Edge Edge;
676  /// Node u=g.addNode(); //node of id 0
677  /// Node v=g.addNode(); //node of id 1
678  /// Node e=g.addEdge(u, v); //edge of id 0
679  /// Node f=g.addEdge(v, u); //edge of id 1
680  /// Graph::NodeMap<bool> nm(g, true);
681  /// nm.set(u, false);
682  /// Graph::EdgeMap<bool> em(g, true);
683  /// em.set(e, false);
684  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
685  /// SubGA ga(g, nm, em);
686  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
687  /// std::cout << ":-)" << std::endl;
688  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
689  ///\endcode
690  /// The output of the above code is the following.
691  ///\code
692  /// 1
693  /// :-)
694  /// 1
695  ///\endcode
696  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
697  /// \c Graph::Node that is why \c g.id(n) can be applied.
698  ///
699  /// For other examples see also the documentation of NodeSubGraphAdaptor and
700  /// EdgeSubGraphAdaptor.
701  ///
702  /// \author Marton Makai
703
704  template<typename _Graph, typename NodeFilterMap,
705           typename EdgeFilterMap, bool checked = true>
706  class SubGraphAdaptor :
707    public GraphAdaptorExtender<
708    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
709  public:
710    typedef _Graph Graph;
711    typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
712                                                      EdgeFilterMap, checked> >
713    Parent;
714
715  protected:
716    SubGraphAdaptor() { }
717  public:
718
719    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
720                    EdgeFilterMap& _edge_filter_map) {
721      setGraph(_graph);
722      setNodeFilterMap(_node_filter_map);
723      setEdgeFilterMap(_edge_filter_map);
724    }
725
726  };
727
728  /// \brief Just gives back a sub graph adaptor
729  ///
730  /// Just gives back a sub graph adaptor
731  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
732  SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
733  subGraphAdaptor(const Graph& graph,
734                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
735    return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
736      (graph, nfm, efm);
737  }
738
739  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
740  SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
741  subGraphAdaptor(const Graph& graph,
742                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
743    return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
744      (graph, nfm, efm);
745  }
746
747  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
748  SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
749  subGraphAdaptor(const Graph& graph,
750                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
751    return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
752      (graph, nfm, efm);
753  }
754
755  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
756  SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
757  subGraphAdaptor(const Graph& graph,
758                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
759    return SubGraphAdaptor<const Graph, const NodeFilterMap,
760      const EdgeFilterMap>(graph, nfm, efm);
761  }
762
763
764
765  ///\ingroup graph_adaptors
766  ///
767  ///\brief An adaptor for hiding nodes from a graph.
768  ///
769  ///An adaptor for hiding nodes from a graph.
770  ///This adaptor specializes SubGraphAdaptor in the way that only
771  ///the node-set
772  ///can be filtered. In usual case the checked parameter is true, we get the
773  ///induced subgraph. But if the checked parameter is false then we can only
774  ///filter only isolated nodes.
775  ///\author Marton Makai
776  template<typename Graph, typename NodeFilterMap, bool checked = true>
777  class NodeSubGraphAdaptor :
778    public SubGraphAdaptor<Graph, NodeFilterMap,
779                           ConstMap<typename Graph::Edge,bool>, checked> {
780  public:
781
782    typedef SubGraphAdaptor<Graph, NodeFilterMap,
783                            ConstMap<typename Graph::Edge,bool>, checked >
784    Parent;
785
786  protected:
787    ConstMap<typename Graph::Edge, bool> const_true_map;
788
789    NodeSubGraphAdaptor() : const_true_map(true) {
790      Parent::setEdgeFilterMap(const_true_map);
791    }
792
793  public:
794
795    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
796      Parent(), const_true_map(true) {
797      Parent::setGraph(_graph);
798      Parent::setNodeFilterMap(_node_filter_map);
799      Parent::setEdgeFilterMap(const_true_map);
800    }
801
802  };
803
804
805  /// \brief Just gives back a node sub graph adaptor
806  ///
807  /// Just gives back a node sub graph adaptor
808  template<typename Graph, typename NodeFilterMap>
809  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
810  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
811    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
812  }
813
814  template<typename Graph, typename NodeFilterMap>
815  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
816  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
817    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
818  }
819
820  ///\ingroup graph_adaptors
821  ///
822  ///\brief An adaptor for hiding edges from a graph.
823  ///
824  ///An adaptor for hiding edges from a graph.
825  ///This adaptor specializes SubGraphAdaptor in the way that
826  ///only the edge-set
827  ///can be filtered. The usefulness of this adaptor is demonstrated in the
828  ///problem of searching a maximum number of edge-disjoint shortest paths
829  ///between
830  ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
831  ///non-negative edge-lengths. Note that
832  ///the comprehension of the presented solution
833  ///need's some elementary knowledge from combinatorial optimization.
834  ///
835  ///If a single shortest path is to be
836  ///searched between \c s and \c t, then this can be done easily by
837  ///applying the Dijkstra algorithm. What happens, if a maximum number of
838  ///edge-disjoint shortest paths is to be computed. It can be proved that an
839  ///edge can be in a shortest path if and only
840  ///if it is tight with respect to
841  ///the potential function computed by Dijkstra.
842  ///Moreover, any path containing
843  ///only such edges is a shortest one.
844  ///Thus we have to compute a maximum number
845  ///of edge-disjoint paths between \c s and \c t in
846  ///the graph which has edge-set
847  ///all the tight edges. The computation will be demonstrated
848  ///on the following
849  ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
850  ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
851  ///If you are interested in more demo programs, you can use
852  ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
853  ///The .dot file of the following figure was generated by 
854  ///the demo program \ref dim_to_dot.cc.
855  ///
856  ///\dot
857  ///digraph lemon_dot_example {
858  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
859  ///n0 [ label="0 (s)" ];
860  ///n1 [ label="1" ];
861  ///n2 [ label="2" ];
862  ///n3 [ label="3" ];
863  ///n4 [ label="4" ];
864  ///n5 [ label="5" ];
865  ///n6 [ label="6 (t)" ];
866  ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
867  ///n5 ->  n6 [ label="9, length:4" ];
868  ///n4 ->  n6 [ label="8, length:2" ];
869  ///n3 ->  n5 [ label="7, length:1" ];
870  ///n2 ->  n5 [ label="6, length:3" ];
871  ///n2 ->  n6 [ label="5, length:5" ];
872  ///n2 ->  n4 [ label="4, length:2" ];
873  ///n1 ->  n4 [ label="3, length:3" ];
874  ///n0 ->  n3 [ label="2, length:1" ];
875  ///n0 ->  n2 [ label="1, length:2" ];
876  ///n0 ->  n1 [ label="0, length:3" ];
877  ///}
878  ///\enddot
879  ///
880  ///\code
881  ///Graph g;
882  ///Node s, t;
883  ///LengthMap length(g);
884  ///
885  ///readDimacs(std::cin, g, length, s, t);
886  ///
887  ///cout << "edges with lengths (of form id, source--length->target): " << endl;
888  ///for(EdgeIt e(g); e!=INVALID; ++e)
889  ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
890  ///       << length[e] << "->" << g.id(g.target(e)) << endl;
891  ///
892  ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
893  ///\endcode
894  ///Next, the potential function is computed with Dijkstra.
895  ///\code
896  ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
897  ///Dijkstra dijkstra(g, length);
898  ///dijkstra.run(s);
899  ///\endcode
900  ///Next, we consrtruct a map which filters the edge-set to the tight edges.
901  ///\code
902  ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
903  ///  TightEdgeFilter;
904  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
905  ///
906  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
907  ///SubGA ga(g, tight_edge_filter);
908  ///\endcode
909  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
910  ///with a max flow algorithm Preflow.
911  ///\code
912  ///ConstMap<Edge, int> const_1_map(1);
913  ///Graph::EdgeMap<int> flow(g, 0);
914  ///
915  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
916  ///  preflow(ga, s, t, const_1_map, flow);
917  ///preflow.run();
918  ///\endcode
919  ///Last, the output is:
920  ///\code 
921  ///cout << "maximum number of edge-disjoint shortest path: "
922  ///     << preflow.flowValue() << endl;
923  ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
924  ///     << endl;
925  ///for(EdgeIt e(g); e!=INVALID; ++e)
926  ///  if (flow[e])
927  ///    cout << " " << g.id(g.source(e)) << "--"
928  ///         << length[e] << "->" << g.id(g.target(e)) << endl;
929  ///\endcode
930  ///The program has the following (expected :-)) output:
931  ///\code
932  ///edges with lengths (of form id, source--length->target):
933  /// 9, 5--4->6
934  /// 8, 4--2->6
935  /// 7, 3--1->5
936  /// 6, 2--3->5
937  /// 5, 2--5->6
938  /// 4, 2--2->4
939  /// 3, 1--3->4
940  /// 2, 0--1->3
941  /// 1, 0--2->2
942  /// 0, 0--3->1
943  ///s: 0 t: 6
944  ///maximum number of edge-disjoint shortest path: 2
945  ///edges of the maximum number of edge-disjoint shortest s-t paths:
946  /// 9, 5--4->6
947  /// 8, 4--2->6
948  /// 7, 3--1->5
949  /// 4, 2--2->4
950  /// 2, 0--1->3
951  /// 1, 0--2->2
952  ///\endcode
953  ///
954  ///\author Marton Makai
955  template<typename Graph, typename EdgeFilterMap>
956  class EdgeSubGraphAdaptor :
957    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
958                           EdgeFilterMap, false> {
959  public:
960    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
961                            EdgeFilterMap, false> Parent;
962  protected:
963    ConstMap<typename Graph::Node, bool> const_true_map;
964
965    EdgeSubGraphAdaptor() : const_true_map(true) {
966      Parent::setNodeFilterMap(const_true_map);
967    }
968
969  public:
970
971    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
972      Parent(), const_true_map(true) {
973      Parent::setGraph(_graph);
974      Parent::setNodeFilterMap(const_true_map);
975      Parent::setEdgeFilterMap(_edge_filter_map);
976    }
977
978  };
979
980  /// \brief Just gives back an edge sub graph adaptor
981  ///
982  /// Just gives back an edge sub graph adaptor
983  template<typename Graph, typename EdgeFilterMap>
984  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
985  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
986    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
987  }
988
989  template<typename Graph, typename EdgeFilterMap>
990  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
991  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
992    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
993  }
994
995  template <typename _Graph>
996  class UndirGraphAdaptorBase :
997    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
998  public:
999    typedef _Graph Graph;
1000    typedef UndirGraphAdaptorBase Adaptor;
1001    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1002
1003  protected:
1004
1005    UndirGraphAdaptorBase() : Parent() {}
1006
1007  public:
1008
1009    typedef typename Parent::UEdge UEdge;
1010    typedef typename Parent::Edge Edge;
1011
1012  private:
1013   
1014    template <typename _Value>
1015    class EdgeMapBase {
1016    private:
1017     
1018      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1019     
1020    public:
1021
1022      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1023
1024      typedef _Value Value;
1025      typedef Edge Key;
1026     
1027      EdgeMapBase(const Adaptor& adaptor) :
1028        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1029
1030      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1031        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1032     
1033      void set(const Edge& e, const Value& a) {
1034        if (Parent::direction(e)) {
1035          forward_map.set(e, a);
1036        } else {
1037          backward_map.set(e, a);
1038        }
1039      }
1040
1041      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1042        if (Parent::direction(e)) {
1043          return forward_map[e];
1044        } else {
1045          return backward_map[e];
1046        }
1047      }
1048
1049      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1050        if (Parent::direction(e)) {
1051          return forward_map[e];
1052        } else {
1053          return backward_map[e];
1054        }
1055      }
1056
1057    protected:
1058
1059      MapImpl forward_map, backward_map;
1060
1061    };
1062
1063  public:
1064
1065    template <typename _Value>
1066    class EdgeMap
1067      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1068    {
1069    public:
1070      typedef Adaptor Graph;
1071      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1072   
1073      EdgeMap(const Graph& graph)
1074        : Parent(graph) {}
1075      EdgeMap(const Graph& graph, const _Value& value)
1076        : Parent(graph, value) {}
1077   
1078      EdgeMap& operator=(const EdgeMap& cmap) {
1079        return operator=<EdgeMap>(cmap);
1080      }
1081   
1082      template <typename CMap>
1083      EdgeMap& operator=(const CMap& cmap) {
1084        Parent::operator=(cmap);
1085        return *this;
1086      }
1087    };
1088       
1089    template <typename _Value>
1090    class UEdgeMap : public Graph::template EdgeMap<_Value> {
1091    public:
1092     
1093      typedef typename Graph::template EdgeMap<_Value> Parent;
1094     
1095      explicit UEdgeMap(const Adaptor& ga)
1096        : Parent(*ga.graph) {}
1097
1098      UEdgeMap(const Adaptor& ga, const _Value& value)
1099        : Parent(*ga.graph, value) {}
1100
1101      UEdgeMap& operator=(const UEdgeMap& cmap) {
1102        return operator=<UEdgeMap>(cmap);
1103      }
1104
1105      template <typename CMap>
1106      UEdgeMap& operator=(const CMap& cmap) {
1107        Parent::operator=(cmap);
1108        return *this;
1109      }
1110
1111    };
1112     
1113  };
1114
1115  template <typename _Graph, typename Enable = void>
1116  class AlterableUndirGraphAdaptor
1117    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1118  public:
1119    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1120   
1121  protected:
1122
1123    AlterableUndirGraphAdaptor() : Parent() {}
1124
1125  public:
1126
1127    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1128    typedef InvalidType EdgeNotifier;
1129
1130  };
1131
1132  template <typename _Graph>
1133  class AlterableUndirGraphAdaptor<
1134    _Graph,
1135    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1136    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1137  public:
1138
1139    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1140    typedef _Graph Graph;
1141    typedef typename _Graph::Edge GraphEdge;
1142   
1143  protected:
1144
1145    AlterableUndirGraphAdaptor()
1146      : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
1147
1148    void setGraph(_Graph& graph) {
1149      Parent::setGraph(graph);
1150      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1151    }
1152
1153  public:
1154
1155    ~AlterableUndirGraphAdaptor() {
1156      edge_notifier.clear();
1157    }
1158
1159    typedef typename Parent::UEdge UEdge;
1160    typedef typename Parent::Edge Edge;
1161
1162    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1163
1164    using Parent::getNotifier;
1165
1166    typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1167                               Edge> EdgeNotifier;
1168    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1169
1170  protected:
1171
1172    class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1173    public:
1174
1175      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1176      typedef AlterableUndirGraphAdaptor AdaptorBase;
1177     
1178      NotifierProxy(const AdaptorBase& _adaptor)
1179        : Parent(), adaptor(&_adaptor) {
1180      }
1181
1182      virtual ~NotifierProxy() {
1183        if (Parent::attached()) {
1184          Parent::detach();
1185        }
1186      }
1187
1188      void setNotifier(typename Graph::EdgeNotifier& notifier) {
1189        Parent::attach(notifier);
1190      }
1191
1192     
1193    protected:
1194
1195      virtual void add(const GraphEdge& ge) {
1196        std::vector<Edge> edges;
1197        edges.push_back(AdaptorBase::Parent::direct(ge, true));
1198        edges.push_back(AdaptorBase::Parent::direct(ge, false));
1199        adaptor->getNotifier(Edge()).add(edges);
1200      }
1201      virtual void add(const std::vector<GraphEdge>& ge) {
1202        std::vector<Edge> edges;
1203        for (int i = 0; i < (int)ge.size(); ++i) {
1204          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1205          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1206        }
1207        adaptor->getNotifier(Edge()).add(edges);
1208      }
1209      virtual void erase(const GraphEdge& ge) {
1210        std::vector<Edge> edges;
1211        edges.push_back(AdaptorBase::Parent::direct(ge, true));
1212        edges.push_back(AdaptorBase::Parent::direct(ge, false));
1213        adaptor->getNotifier(Edge()).erase(edges);
1214      }
1215      virtual void erase(const std::vector<GraphEdge>& ge) {
1216        std::vector<Edge> edges;
1217        for (int i = 0; i < (int)ge.size(); ++i) {
1218          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1219          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1220        }
1221        adaptor->getNotifier(Edge()).erase(edges);
1222      }
1223      virtual void build() {
1224        adaptor->getNotifier(Edge()).build();
1225      }
1226      virtual void clear() {
1227        adaptor->getNotifier(Edge()).clear();
1228      }
1229
1230      const AdaptorBase* adaptor;
1231    };
1232
1233
1234    mutable EdgeNotifier edge_notifier;
1235    NotifierProxy edge_notifier_proxy;
1236
1237  };
1238
1239
1240  ///\ingroup graph_adaptors
1241  ///
1242  /// \brief An undirected graph is made from a directed graph by an adaptor
1243  ///
1244  /// Undocumented, untested!!!
1245  /// If somebody knows nice demo application, let's polulate it.
1246  ///
1247  /// \author Marton Makai
1248  template<typename _Graph>
1249  class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1250  public:
1251    typedef _Graph Graph;
1252    typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1253  protected:
1254    UndirGraphAdaptor() { }
1255  public:
1256    UndirGraphAdaptor(_Graph& _graph) {
1257      setGraph(_graph);
1258    }
1259
1260    template <typename _ForwardMap, typename _BackwardMap>
1261    class CombinedEdgeMap {
1262    public:
1263     
1264      typedef _ForwardMap ForwardMap;
1265      typedef _BackwardMap BackwardMap;
1266
1267      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1268
1269      typedef typename ForwardMap::Value Value;
1270      typedef typename Parent::Edge Key;
1271     
1272      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1273
1274      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1275        : forward_map(&_forward_map), backward_map(&_backward_map) {}
1276     
1277      void set(const Key& e, const Value& a) {
1278        if (Parent::direction(e)) {
1279          forward_map->set(e, a);
1280        } else {
1281          backward_map->set(e, a);
1282        }
1283      }
1284
1285      typename MapTraits<ForwardMap>::ConstReturnValue
1286      operator[](const Key& e) const {
1287        if (Parent::direction(e)) {
1288          return (*forward_map)[e];
1289        } else {
1290          return (*backward_map)[e];
1291        }
1292      }
1293
1294      typename MapTraits<ForwardMap>::ReturnValue
1295      operator[](const Key& e) {
1296        if (Parent::direction(e)) {
1297          return (*forward_map)[e];
1298        } else {
1299          return (*backward_map)[e];
1300        }
1301      }
1302
1303      void setForwardMap(ForwardMap& _forward_map) {
1304        forward_map = &_forward_map;
1305      }
1306
1307      void setBackwardMap(BackwardMap& _backward_map) {
1308        backward_map = &_backward_map;
1309      }
1310
1311    protected:
1312
1313      ForwardMap* forward_map;
1314      BackwardMap* backward_map;
1315
1316    };
1317
1318  };
1319
1320  /// \brief Just gives back an undir graph adaptor
1321  ///
1322  /// Just gives back an undir graph adaptor
1323  template<typename Graph>
1324  UndirGraphAdaptor<const Graph>
1325  undirGraphAdaptor(const Graph& graph) {
1326    return UndirGraphAdaptor<const Graph>(graph);
1327  }
1328
1329  template<typename Graph, typename Number, 
1330           typename CapacityMap, typename FlowMap,
1331           typename Tolerance = Tolerance<Number> >
1332  class ResForwardFilter {
1333    const CapacityMap* capacity;
1334    const FlowMap* flow;
1335    Tolerance tolerance;
1336  public:
1337    typedef typename Graph::Edge Key;
1338    typedef bool Value;
1339
1340    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1341                     const Tolerance& _tolerance = Tolerance())
1342      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1343
1344    ResForwardFilter(const Tolerance& _tolerance)
1345      : capacity(0), flow(0), tolerance(_tolerance)  { }
1346
1347    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1348    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1349
1350    bool operator[](const typename Graph::Edge& e) const {
1351      return tolerance.less((*flow)[e], (*capacity)[e]);
1352    }
1353  };
1354
1355  template<typename Graph, typename Number,
1356           typename CapacityMap, typename FlowMap,
1357           typename Tolerance = Tolerance<Number> >
1358  class ResBackwardFilter {
1359    const CapacityMap* capacity;
1360    const FlowMap* flow;
1361    Tolerance tolerance;
1362  public:
1363    typedef typename Graph::Edge Key;
1364    typedef bool Value;
1365
1366    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1367                      const Tolerance& _tolerance = Tolerance())
1368      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1369    ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
1370      : capacity(0), flow(0), tolerance(_tolerance) { }
1371    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1372    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1373    bool operator[](const typename Graph::Edge& e) const {
1374      return tolerance.less(0, Number((*flow)[e]));
1375    }
1376  };
1377
1378 
1379  ///\ingroup graph_adaptors
1380  ///
1381  ///\brief An adaptor for composing the residual
1382  ///graph for directed flow and circulation problems.
1383  ///
1384  ///An adaptor for composing the residual graph for directed flow and
1385  ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
1386  ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1387  ///be functions on the edge-set.
1388  ///
1389  ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1390  ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
1391  ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1392  ///
1393  ///\code
1394  ///  ListGraph g;
1395  ///\endcode
1396  ///
1397  ///Then RevGraphAdaptor implements the graph structure with node-set
1398  /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1399  ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1400  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1401  ///residual graph.  When we take the union
1402  /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1403  ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1404  ///then in the adaptor it appears twice. The following code shows how
1405  ///such an instance can be constructed.
1406  ///
1407  ///\code
1408  ///  typedef ListGraph Graph;
1409  ///  Graph::EdgeMap<int> f(g);
1410  ///  Graph::EdgeMap<int> c(g);
1411  ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1412  ///\endcode
1413  ///\author Marton Makai
1414  ///
1415  template<typename Graph, typename Number,
1416           typename CapacityMap, typename FlowMap,
1417           typename Tolerance = Tolerance<Number> >
1418  class ResGraphAdaptor :
1419    public EdgeSubGraphAdaptor<
1420    UndirGraphAdaptor<const Graph>,
1421    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1422    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 
1423    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1424  public:
1425
1426    typedef UndirGraphAdaptor<const Graph> UGraph;
1427
1428    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1429    ForwardFilter;
1430
1431    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1432    BackwardFilter;
1433
1434    typedef typename UGraph::
1435    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1436    EdgeFilter;
1437
1438    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1439
1440  protected:
1441
1442    const CapacityMap* capacity;
1443    FlowMap* flow;
1444
1445    UGraph ugraph;
1446    ForwardFilter forward_filter;
1447    BackwardFilter backward_filter;
1448    EdgeFilter edge_filter;
1449
1450    void setCapacityMap(const CapacityMap& _capacity) {
1451      capacity=&_capacity;
1452      forward_filter.setCapacity(_capacity);
1453      backward_filter.setCapacity(_capacity);
1454    }
1455
1456    void setFlowMap(FlowMap& _flow) {
1457      flow=&_flow;
1458      forward_filter.setFlow(_flow);
1459      backward_filter.setFlow(_flow);
1460    }
1461
1462  public:
1463
1464    /// \brief Constructor of the residual graph.
1465    ///
1466    /// Constructor of the residual graph. The parameters are the graph type,
1467    /// the flow map, the capacity map and a tolerance object.
1468    ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
1469                    FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
1470      : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1471        forward_filter(_capacity, _flow, _tolerance),
1472        backward_filter(_capacity, _flow, _tolerance),
1473        edge_filter(forward_filter, backward_filter)
1474    {
1475      Parent::setGraph(ugraph);
1476      Parent::setEdgeFilterMap(edge_filter);
1477    }
1478
1479    typedef typename Parent::Edge Edge;
1480
1481    /// \brief Gives back the residual capacity of the edge.
1482    ///
1483    /// Gives back the residual capacity of the edge.
1484    Number rescap(const Edge& edge) const {
1485      if (UGraph::direction(edge)) {
1486        return (*capacity)[edge]-(*flow)[edge];
1487      } else {
1488        return (*flow)[edge];
1489      }
1490    }
1491
1492    /// \brief Augment on the given edge in the residual graph.
1493    ///
1494    /// Augment on the given edge in the residual graph. It increase
1495    /// or decrease the flow on the original edge depend on the direction
1496    /// of the residual edge.
1497    void augment(const Edge& e, Number a) const {
1498      if (UGraph::direction(e)) {
1499        flow->set(e, (*flow)[e] + a);
1500      } else { 
1501        flow->set(e, (*flow)[e] - a);
1502      }
1503    }
1504
1505    /// \brief Returns the direction of the edge.
1506    ///
1507    /// Returns true when the edge is same oriented as the original edge.
1508    static bool forward(const Edge& e) {
1509      return UGraph::direction(e);
1510    }
1511
1512    /// \brief Returns the direction of the edge.
1513    ///
1514    /// Returns true when the edge is opposite oriented as the original edge.
1515    static bool backward(const Edge& e) {
1516      return !UGraph::direction(e);
1517    }
1518
1519    /// \brief Gives back the forward oriented residual edge.
1520    ///
1521    /// Gives back the forward oriented residual edge.
1522    static Edge forward(const typename Graph::Edge& e) {
1523      return UGraph::direct(e, true);
1524    }
1525
1526    /// \brief Gives back the backward oriented residual edge.
1527    ///
1528    /// Gives back the backward oriented residual edge.
1529    static Edge backward(const typename Graph::Edge& e) {
1530      return UGraph::direct(e, false);
1531    }
1532
1533    /// \brief Residual capacity map.
1534    ///
1535    /// In generic residual graphs the residual capacity can be obtained
1536    /// as a map.
1537    class ResCap {
1538    protected:
1539      const ResGraphAdaptor* res_graph;
1540    public:
1541      typedef Number Value;
1542      typedef Edge Key;
1543      ResCap(const ResGraphAdaptor& _res_graph)
1544        : res_graph(&_res_graph) {}
1545     
1546      Number operator[](const Edge& e) const {
1547        return res_graph->rescap(e);
1548      }
1549     
1550    };
1551
1552  };
1553
1554
1555
1556  template <typename _Graph, typename FirstOutEdgesMap>
1557  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1558  public:
1559    typedef _Graph Graph;
1560    typedef GraphAdaptorBase<_Graph> Parent;
1561  protected:
1562    FirstOutEdgesMap* first_out_edges;
1563    ErasingFirstGraphAdaptorBase() : Parent(),
1564                                     first_out_edges(0) { }
1565
1566    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1567      first_out_edges=&_first_out_edges;
1568    }
1569
1570  public:
1571
1572    typedef typename Parent::Node Node;
1573    typedef typename Parent::Edge Edge;
1574
1575    void firstOut(Edge& i, const Node& n) const {
1576      i=(*first_out_edges)[n];
1577    }
1578
1579    void erase(const Edge& e) const {
1580      Node n=source(e);
1581      Edge f=e;
1582      Parent::nextOut(f);
1583      first_out_edges->set(n, f);
1584    }   
1585  };
1586
1587
1588  ///\ingroup graph_adaptors
1589  ///
1590  ///\brief For blocking flows.
1591  ///
1592  ///This graph adaptor is used for on-the-fly
1593  ///Dinits blocking flow computations.
1594  ///For each node, an out-edge is stored which is used when the
1595  ///\code
1596  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1597  ///\endcode
1598  ///is called.
1599  ///
1600  ///\author Marton Makai
1601  ///
1602  template <typename _Graph, typename FirstOutEdgesMap>
1603  class ErasingFirstGraphAdaptor :
1604    public GraphAdaptorExtender<
1605    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1606  public:
1607    typedef _Graph Graph;
1608    typedef GraphAdaptorExtender<
1609      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1610    ErasingFirstGraphAdaptor(Graph& _graph,
1611                             FirstOutEdgesMap& _first_out_edges) {
1612      setGraph(_graph);
1613      setFirstOutEdgesMap(_first_out_edges);
1614    }
1615
1616  };
1617
1618  /// \brief Base class for split graph adaptor
1619  ///
1620  /// Base class of split graph adaptor. In most case you do not need to
1621  /// use it directly but the documented member functions of this class can
1622  /// be used with the SplitGraphAdaptor class.
1623  /// \sa SplitGraphAdaptor
1624  template <typename _Graph>
1625  class SplitGraphAdaptorBase
1626    : public GraphAdaptorBase<const _Graph> {
1627  public:
1628
1629    typedef _Graph Graph;
1630
1631    typedef GraphAdaptorBase<const _Graph> Parent;
1632
1633    typedef typename Graph::Node GraphNode;
1634    typedef typename Graph::Edge GraphEdge;
1635
1636    class Node;
1637    class Edge;
1638
1639    template <typename T> class NodeMap;
1640    template <typename T> class EdgeMap;
1641   
1642
1643    class Node : public GraphNode {
1644      friend class SplitGraphAdaptorBase;
1645      template <typename T> friend class NodeMap;
1646    private:
1647
1648      bool in_node;
1649      Node(GraphNode _node, bool _in_node)
1650        : GraphNode(_node), in_node(_in_node) {}
1651     
1652    public:
1653
1654      Node() {}
1655      Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1656
1657      bool operator==(const Node& node) const {
1658        return GraphNode::operator==(node) && in_node == node.in_node;
1659      }
1660     
1661      bool operator!=(const Node& node) const {
1662        return !(*this == node);
1663      }
1664     
1665      bool operator<(const Node& node) const {
1666        return GraphNode::operator<(node) ||
1667          (GraphNode::operator==(node) && in_node < node.in_node);
1668      }
1669    };
1670
1671    class Edge {
1672      friend class SplitGraphAdaptorBase;
1673      template <typename T> friend class EdgeMap;
1674    private:
1675      typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1676
1677      explicit Edge(const GraphEdge& edge) : item(edge) {}
1678      explicit Edge(const GraphNode& node) : item(node) {}
1679     
1680      EdgeImpl item;
1681
1682    public:
1683      Edge() {}
1684      Edge(Invalid) : item(GraphEdge(INVALID)) {}
1685
1686      bool operator==(const Edge& edge) const {
1687        if (item.firstState()) {
1688          if (edge.item.firstState()) {
1689            return item.first() == edge.item.first();
1690          }
1691        } else {
1692          if (edge.item.secondState()) {
1693            return item.second() == edge.item.second();
1694          }
1695        }
1696        return false;
1697      }
1698     
1699      bool operator!=(const Edge& edge) const {
1700        return !(*this == edge);
1701      }
1702     
1703      bool operator<(const Edge& edge) const {
1704        if (item.firstState()) {
1705          if (edge.item.firstState()) {
1706            return item.first() < edge.item.first();
1707          }
1708          return false;
1709        } else {
1710          if (edge.item.secondState()) {
1711            return item.second() < edge.item.second();
1712          }
1713          return true;
1714        }
1715      }
1716
1717      operator GraphEdge() const { return item.first(); }
1718      operator GraphNode() const { return item.second(); }
1719
1720    };
1721
1722    void first(Node& node) const {
1723      Parent::first(node);
1724      node.in_node = true;
1725    }
1726
1727    void next(Node& node) const {
1728      if (node.in_node) {
1729        node.in_node = false;
1730      } else {
1731        node.in_node = true;
1732        Parent::next(node);
1733      }
1734    }
1735
1736    void first(Edge& edge) const {
1737      edge.item.setSecond();
1738      Parent::first(edge.item.second());
1739      if (edge.item.second() == INVALID) {
1740        edge.item.setFirst();
1741        Parent::first(edge.item.first());
1742      }
1743    }
1744
1745    void next(Edge& edge) const {
1746      if (edge.item.secondState()) {
1747        Parent::next(edge.item.second());
1748        if (edge.item.second() == INVALID) {
1749          edge.item.setFirst();
1750          Parent::first(edge.item.first());
1751        }
1752      } else {
1753        Parent::next(edge.item.first());
1754      }     
1755    }
1756
1757    void firstOut(Edge& edge, const Node& node) const {
1758      if (node.in_node) {
1759        edge.item.setSecond(node);
1760      } else {
1761        edge.item.setFirst();
1762        Parent::firstOut(edge.item.first(), node);
1763      }
1764    }
1765
1766    void nextOut(Edge& edge) const {
1767      if (!edge.item.firstState()) {
1768        edge.item.setFirst(INVALID);
1769      } else {
1770        Parent::nextOut(edge.item.first());
1771      }     
1772    }
1773
1774    void firstIn(Edge& edge, const Node& node) const {
1775      if (!node.in_node) {
1776        edge.item.setSecond(node);       
1777      } else {
1778        edge.item.setFirst();
1779        Parent::firstIn(edge.item.first(), node);
1780      }
1781    }
1782
1783    void nextIn(Edge& edge) const {
1784      if (!edge.item.firstState()) {
1785        edge.item.setFirst(INVALID);
1786      } else {
1787        Parent::nextIn(edge.item.first());
1788      }
1789    }
1790
1791    Node source(const Edge& edge) const {
1792      if (edge.item.firstState()) {
1793        return Node(Parent::source(edge.item.first()), false);
1794      } else {
1795        return Node(edge.item.second(), true);
1796      }
1797    }
1798
1799    Node target(const Edge& edge) const {
1800      if (edge.item.firstState()) {
1801        return Node(Parent::target(edge.item.first()), true);
1802      } else {
1803        return Node(edge.item.second(), false);
1804      }
1805    }
1806
1807    int id(const Node& node) const {
1808      return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1809    }
1810    Node nodeFromId(int id) const {
1811      return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1812    }
1813    int maxNodeId() const {
1814      return 2 * Parent::maxNodeId() + 1;
1815    }
1816
1817    int id(const Edge& edge) const {
1818      if (edge.item.firstState()) {
1819        return Parent::id(edge.item.first()) << 1;
1820      } else {
1821        return (Parent::id(edge.item.second()) << 1) | 1;
1822      }
1823    }
1824    Edge edgeFromId(int id) const {
1825      if ((id & 1) == 0) {
1826        return Edge(Parent::edgeFromId(id >> 1));
1827      } else {
1828        return Edge(Parent::nodeFromId(id >> 1));
1829      }
1830    }
1831    int maxEdgeId() const {
1832      return std::max(Parent::maxNodeId() << 1,
1833                      (Parent::maxEdgeId() << 1) | 1);
1834    }
1835
1836    /// \brief Returns true when the node is in-node.
1837    ///
1838    /// Returns true when the node is in-node.
1839    static bool inNode(const Node& node) {
1840      return node.in_node;
1841    }
1842
1843    /// \brief Returns true when the node is out-node.
1844    ///
1845    /// Returns true when the node is out-node.
1846    static bool outNode(const Node& node) {
1847      return !node.in_node;
1848    }
1849
1850    /// \brief Returns true when the edge is edge in the original graph.
1851    ///
1852    /// Returns true when the edge is edge in the original graph.
1853    static bool origEdge(const Edge& edge) {
1854      return edge.item.firstState();
1855    }
1856
1857    /// \brief Returns true when the edge binds an in-node and an out-node.
1858    ///
1859    /// Returns true when the edge binds an in-node and an out-node.
1860    static bool bindEdge(const Edge& edge) {
1861      return edge.item.secondState();
1862    }
1863
1864    /// \brief Gives back the in-node created from the \c node.
1865    ///
1866    /// Gives back the in-node created from the \c node.
1867    static Node inNode(const GraphNode& node) {
1868      return Node(node, true);
1869    }
1870
1871    /// \brief Gives back the out-node created from the \c node.
1872    ///
1873    /// Gives back the out-node created from the \c node.
1874    static Node outNode(const GraphNode& node) {
1875      return Node(node, false);
1876    }
1877
1878    /// \brief Gives back the edge binds the two part of the node.
1879    ///
1880    /// Gives back the edge binds the two part of the node.
1881    static Edge edge(const GraphNode& node) {
1882      return Edge(node);
1883    }
1884
1885    /// \brief Gives back the edge of the original edge.
1886    ///
1887    /// Gives back the edge of the original edge.
1888    static Edge edge(const GraphEdge& edge) {
1889      return Edge(edge);
1890    }
1891
1892    typedef True NodeNumTag;
1893
1894    int nodeNum() const {
1895      return  2 * countNodes(*Parent::graph);
1896    }
1897
1898    typedef True EdgeNumTag;
1899   
1900    int edgeNum() const {
1901      return countEdges(*Parent::graph) + countNodes(*Parent::graph);
1902    }
1903
1904    typedef True FindEdgeTag;
1905
1906    Edge findEdge(const Node& source, const Node& target,
1907                  const Edge& prev = INVALID) const {
1908      if (inNode(source)) {
1909        if (outNode(target)) {
1910          if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
1911            return Edge(source);
1912          }
1913        }
1914      } else {
1915        if (inNode(target)) {
1916          return Edge(findEdge(*Parent::graph, source, target, prev));
1917        }
1918      }
1919      return INVALID;
1920    }
1921   
1922    template <typename T>
1923    class NodeMap : public MapBase<Node, T> {
1924      typedef typename Parent::template NodeMap<T> NodeImpl;
1925    public:
1926      NodeMap(const SplitGraphAdaptorBase& _graph)
1927        : inNodeMap(_graph), outNodeMap(_graph) {}
1928      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1929        : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
1930     
1931      void set(const Node& key, const T& val) {
1932        if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
1933        else {outNodeMap.set(key, val); }
1934      }
1935     
1936      typename MapTraits<NodeImpl>::ReturnValue
1937      operator[](const Node& key) {
1938        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1939        else { return outNodeMap[key]; }
1940      }
1941
1942      typename MapTraits<NodeImpl>::ConstReturnValue
1943      operator[](const Node& key) const {
1944        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1945        else { return outNodeMap[key]; }
1946      }
1947
1948    private:
1949      NodeImpl inNodeMap, outNodeMap;
1950    };
1951
1952    template <typename T>
1953    class EdgeMap : public MapBase<Edge, T> {
1954      typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
1955      typedef typename Parent::template NodeMap<T> NodeMapImpl;
1956    public:
1957
1958      EdgeMap(const SplitGraphAdaptorBase& _graph)
1959        : edge_map(_graph), node_map(_graph) {}
1960      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1961        : edge_map(_graph, t), node_map(_graph, t) {}
1962     
1963      void set(const Edge& key, const T& val) {
1964        if (SplitGraphAdaptorBase::origEdge(key)) {
1965          edge_map.set(key.item.first(), val);
1966        } else {
1967          node_map.set(key.item.second(), val);
1968        }
1969      }
1970     
1971      typename MapTraits<EdgeMapImpl>::ReturnValue
1972      operator[](const Edge& key) {
1973        if (SplitGraphAdaptorBase::origEdge(key)) {
1974          return edge_map[key.item.first()];
1975        } else {
1976          return node_map[key.item.second()];
1977        }
1978      }
1979
1980      typename MapTraits<EdgeMapImpl>::ConstReturnValue
1981      operator[](const Edge& key) const {
1982        if (SplitGraphAdaptorBase::origEdge(key)) {
1983          return edge_map[key.item.first()];
1984        } else {
1985          return node_map[key.item.second()];
1986        }
1987      }
1988
1989    private:
1990      typename Parent::template EdgeMap<T> edge_map;
1991      typename Parent::template NodeMap<T> node_map;
1992    };
1993
1994
1995  };
1996
1997  template <typename _Graph, typename NodeEnable = void,
1998            typename EdgeEnable = void>
1999  class AlterableSplitGraphAdaptor
2000    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2001  public:
2002
2003    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2004    typedef _Graph Graph;
2005
2006    typedef typename Graph::Node GraphNode;
2007    typedef typename Graph::Node GraphEdge;
2008
2009  protected:
2010
2011    AlterableSplitGraphAdaptor() : Parent() {}
2012
2013  public:
2014   
2015    typedef InvalidType NodeNotifier;
2016    typedef InvalidType EdgeNotifier;
2017
2018  };
2019
2020  template <typename _Graph, typename EdgeEnable>
2021  class AlterableSplitGraphAdaptor<
2022    _Graph,
2023    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2024    EdgeEnable>
2025      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2026  public:
2027
2028    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2029    typedef _Graph Graph;
2030
2031    typedef typename Graph::Node GraphNode;
2032    typedef typename Graph::Edge GraphEdge;
2033
2034    typedef typename Parent::Node Node;
2035    typedef typename Parent::Edge Edge;
2036 
2037  protected:
2038
2039    AlterableSplitGraphAdaptor()
2040      : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2041
2042    void setGraph(_Graph& graph) {
2043      Parent::setGraph(graph);
2044      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2045    }
2046
2047  public:
2048
2049    ~AlterableSplitGraphAdaptor() {
2050      node_notifier.clear();
2051    }
2052
2053    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2054    typedef InvalidType EdgeNotifier;
2055
2056    NodeNotifier& getNotifier(Node) const { return node_notifier; }
2057
2058  protected:
2059
2060    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2061    public:
2062
2063      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2064      typedef AlterableSplitGraphAdaptor AdaptorBase;
2065     
2066      NodeNotifierProxy(const AdaptorBase& _adaptor)
2067        : Parent(), adaptor(&_adaptor) {
2068      }
2069
2070      virtual ~NodeNotifierProxy() {
2071        if (Parent::attached()) {
2072          Parent::detach();
2073        }
2074      }
2075
2076      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2077        Parent::attach(graph_notifier);
2078      }
2079
2080     
2081    protected:
2082
2083      virtual void add(const GraphNode& gn) {
2084        std::vector<Node> nodes;
2085        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2086        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2087        adaptor->getNotifier(Node()).add(nodes);
2088      }
2089
2090      virtual void add(const std::vector<GraphNode>& gn) {
2091        std::vector<Node> nodes;
2092        for (int i = 0; i < (int)gn.size(); ++i) {
2093          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2094          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2095        }
2096        adaptor->getNotifier(Node()).add(nodes);
2097      }
2098
2099      virtual void erase(const GraphNode& gn) {
2100        std::vector<Node> nodes;
2101        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2102        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2103        adaptor->getNotifier(Node()).erase(nodes);
2104      }
2105
2106      virtual void erase(const std::vector<GraphNode>& gn) {
2107        std::vector<Node> nodes;
2108        for (int i = 0; i < (int)gn.size(); ++i) {
2109          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2110          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2111        }
2112        adaptor->getNotifier(Node()).erase(nodes);
2113      }
2114      virtual void build() {
2115        adaptor->getNotifier(Node()).build();
2116      }
2117      virtual void clear() {
2118        adaptor->getNotifier(Node()).clear();
2119      }
2120
2121      const AdaptorBase* adaptor;
2122    };
2123
2124
2125    mutable NodeNotifier node_notifier;
2126
2127    NodeNotifierProxy node_notifier_proxy;
2128
2129  };
2130
2131  template <typename _Graph>
2132  class AlterableSplitGraphAdaptor<
2133    _Graph,
2134    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2135    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2136      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2137  public:
2138
2139    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2140    typedef _Graph Graph;
2141
2142    typedef typename Graph::Node GraphNode;
2143    typedef typename Graph::Edge GraphEdge;
2144
2145    typedef typename Parent::Node Node;
2146    typedef typename Parent::Edge Edge;
2147 
2148  protected:
2149   
2150    AlterableSplitGraphAdaptor()
2151      : Parent(), node_notifier(*this), edge_notifier(*this),
2152        node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2153   
2154    void setGraph(_Graph& graph) {
2155      Parent::setGraph(graph);
2156      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2157      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
2158    }
2159
2160  public:
2161
2162    ~AlterableSplitGraphAdaptor() {
2163      node_notifier.clear();
2164      edge_notifier.clear();
2165    }
2166
2167    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2168    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2169
2170    NodeNotifier& getNotifier(Node) const { return node_notifier; }
2171    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
2172
2173  protected:
2174
2175    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2176    public:
2177     
2178      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2179      typedef AlterableSplitGraphAdaptor AdaptorBase;
2180     
2181      NodeNotifierProxy(const AdaptorBase& _adaptor)
2182        : Parent(), adaptor(&_adaptor) {
2183      }
2184
2185      virtual ~NodeNotifierProxy() {
2186        if (Parent::attached()) {
2187          Parent::detach();
2188        }
2189      }
2190
2191      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2192        Parent::attach(graph_notifier);
2193      }
2194
2195     
2196    protected:
2197
2198      virtual void add(const GraphNode& gn) {
2199        std::vector<Node> nodes;
2200        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2201        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2202        adaptor->getNotifier(Node()).add(nodes);
2203        adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2204      }
2205      virtual void add(const std::vector<GraphNode>& gn) {
2206        std::vector<Node> nodes;
2207        std::vector<Edge> edges;
2208        for (int i = 0; i < (int)gn.size(); ++i) {
2209          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2210          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2211          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2212        }
2213        adaptor->getNotifier(Node()).add(nodes);
2214        adaptor->getNotifier(Edge()).add(edges);
2215      }
2216      virtual void erase(const GraphNode& gn) {
2217        adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2218        std::vector<Node> nodes;
2219        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2220        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2221        adaptor->getNotifier(Node()).erase(nodes);
2222      }
2223      virtual void erase(const std::vector<GraphNode>& gn) {
2224        std::vector<Node> nodes;
2225        std::vector<Edge> edges;
2226        for (int i = 0; i < (int)gn.size(); ++i) {
2227          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2228          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2229          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2230        }
2231        adaptor->getNotifier(Edge()).erase(edges);
2232        adaptor->getNotifier(Node()).erase(nodes);
2233      }
2234      virtual void build() {
2235        std::vector<Edge> edges;
2236        const typename Parent::Notifier* notifier = Parent::getNotifier();
2237        GraphNode it;
2238        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2239          edges.push_back(AdaptorBase::Parent::edge(it));
2240        }
2241        adaptor->getNotifier(Node()).build();
2242        adaptor->getNotifier(Edge()).add(edges);       
2243      }
2244      virtual void clear() {
2245        std::vector<Edge> edges;
2246        const typename Parent::Notifier* notifier = Parent::getNotifier();
2247        GraphNode it;
2248        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2249          edges.push_back(AdaptorBase::Parent::edge(it));
2250        }
2251        adaptor->getNotifier(Edge()).erase(edges);       
2252        adaptor->getNotifier(Node()).clear();
2253      }
2254
2255      const AdaptorBase* adaptor;
2256    };
2257
2258    class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2259    public:
2260
2261      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2262      typedef AlterableSplitGraphAdaptor AdaptorBase;
2263     
2264      EdgeNotifierProxy(const AdaptorBase& _adaptor)
2265        : Parent(), adaptor(&_adaptor) {
2266      }
2267
2268      virtual ~EdgeNotifierProxy() {
2269        if (Parent::attached()) {
2270          Parent::detach();
2271        }
2272      }
2273
2274      void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2275        Parent::attach(graph_notifier);
2276      }
2277
2278     
2279    protected:
2280
2281      virtual void add(const GraphEdge& ge) {
2282        adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
2283      }
2284      virtual void add(const std::vector<GraphEdge>& ge) {
2285        std::vector<Edge> edges;
2286        for (int i = 0; i < (int)ge.size(); ++i) {
2287          edges.push_back(AdaptorBase::edge(ge[i]));
2288        }
2289        adaptor->getNotifier(Edge()).add(edges);
2290      }
2291      virtual void erase(const GraphEdge& ge) {
2292        adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
2293      }
2294      virtual void erase(const std::vector<GraphEdge>& ge) {
2295        std::vector<Edge> edges;
2296        for (int i = 0; i < (int)ge.size(); ++i) {
2297          edges.push_back(AdaptorBase::edge(ge[i]));
2298        }
2299        adaptor->getNotifier(Edge()).erase(edges);
2300      }
2301      virtual void build() {
2302        std::vector<Edge> edges;
2303        const typename Parent::Notifier* notifier = Parent::getNotifier();
2304        GraphEdge it;
2305        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2306          edges.push_back(AdaptorBase::Parent::edge(it));
2307        }
2308        adaptor->getNotifier(Edge()).add(edges);
2309      }
2310      virtual void clear() {
2311        std::vector<Edge> edges;
2312        const typename Parent::Notifier* notifier = Parent::getNotifier();
2313        GraphEdge it;
2314        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2315          edges.push_back(AdaptorBase::Parent::edge(it));
2316        }
2317        adaptor->getNotifier(Edge()).erase(edges);
2318      }
2319
2320      const AdaptorBase* adaptor;
2321    };
2322
2323
2324    mutable NodeNotifier node_notifier;
2325    mutable EdgeNotifier edge_notifier;
2326
2327    NodeNotifierProxy node_notifier_proxy;
2328    EdgeNotifierProxy edge_notifier_proxy;
2329
2330  };
2331
2332  /// \ingroup graph_adaptors
2333  ///
2334  /// \brief Split graph adaptor class
2335  ///
2336  /// This is an graph adaptor which splits all node into an in-node
2337  /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2338  /// node in the graph with two node, \f$ u_{in} \f$ node and
2339  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2340  /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2341  /// similarly the source of the original \f$ (u, v) \f$ edge will be
2342  /// \f$ u_{out} \f$.  The adaptor will add for each node in the
2343  /// original graph an additional edge which will connect
2344  /// \f$ (u_{in}, u_{out}) \f$.
2345  ///
2346  /// The aim of this class is to run algorithm with node costs if the
2347  /// algorithm can use directly just edge costs. In this case we should use
2348  /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2349  /// bind edge in the adapted graph.
2350  ///
2351  /// By example a maximum flow algoritm can compute how many edge
2352  /// disjoint paths are in the graph. But we would like to know how
2353  /// many node disjoint paths are in the graph. First we have to
2354  /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2355  /// algorithm on the adapted graph. The bottleneck of the flow will
2356  /// be the bind edges which bounds the flow with the count of the
2357  /// node disjoint paths.
2358  ///
2359  ///\code
2360  ///
2361  /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2362  ///
2363  /// SGraph sgraph(graph);
2364  ///
2365  /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2366  /// SCapacity scapacity(1);
2367  ///
2368  /// SGraph::EdgeMap<int> sflow(sgraph);
2369  ///
2370  /// Preflow<SGraph, int, SCapacity>
2371  ///   spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), 
2372  ///            scapacity, sflow);
2373  ///                                           
2374  /// spreflow.run();
2375  ///
2376  ///\endcode
2377  ///
2378  /// The result of the mamixum flow on the original graph
2379  /// shows the next figure:
2380  ///
2381  /// \image html edge_disjoint.png
2382  /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2383  ///
2384  /// And the maximum flow on the adapted graph:
2385  ///
2386  /// \image html node_disjoint.png
2387  /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2388  ///
2389  /// The second solution contains just 3 disjoint paths while the first 4.
2390  /// The full code can be found in the \ref disjoint_paths.cc demo file.
2391  ///
2392  /// This graph adaptor is fully conform to the
2393  /// \ref concept::StaticGraph "StaticGraph" concept and
2394  /// contains some additional member functions and types. The
2395  /// documentation of some member functions may be found just in the
2396  /// SplitGraphAdaptorBase class.
2397  ///
2398  /// \sa SplitGraphAdaptorBase
2399  template <typename _Graph>
2400  class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2401  public:
2402    typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2403
2404    typedef typename Parent::Node Node;
2405    typedef typename Parent::Edge Edge;
2406
2407    /// \brief Constructor of the adaptor.
2408    ///
2409    /// Constructor of the adaptor.
2410    SplitGraphAdaptor(_Graph& graph) {
2411      Parent::setGraph(graph);
2412    }
2413
2414    /// \brief NodeMap combined from two original NodeMap
2415    ///
2416    /// This class adapt two of the original graph NodeMap to
2417    /// get a node map on the adapted graph.
2418    template <typename InNodeMap, typename OutNodeMap>
2419    class CombinedNodeMap {
2420    public:
2421
2422      typedef Node Key;
2423      typedef typename InNodeMap::Value Value;
2424
2425      /// \brief Constructor
2426      ///
2427      /// Constructor.
2428      CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2429        : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2430
2431      /// \brief The subscript operator.
2432      ///
2433      /// The subscript operator.
2434      Value& operator[](const Key& key) {
2435        if (Parent::inNode(key)) {
2436          return inNodeMap[key];
2437        } else {
2438          return outNodeMap[key];
2439        }
2440      }
2441
2442      /// \brief The const subscript operator.
2443      ///
2444      /// The const subscript operator.
2445      Value operator[](const Key& key) const {
2446        if (Parent::inNode(key)) {
2447          return inNodeMap[key];
2448        } else {
2449          return outNodeMap[key];
2450        }
2451      }
2452
2453      /// \brief The setter function of the map.
2454      ///
2455      /// The setter function of the map.
2456      void set(const Key& key, const Value& value) {
2457        if (Parent::inNode(key)) {
2458          inNodeMap.set(key, value);
2459        } else {
2460          outNodeMap.set(key, value);
2461        }
2462      }
2463     
2464    private:
2465     
2466      InNodeMap& inNodeMap;
2467      OutNodeMap& outNodeMap;
2468     
2469    };
2470
2471
2472    /// \brief Just gives back a combined node map.
2473    ///
2474    /// Just gives back a combined node map.
2475    template <typename InNodeMap, typename OutNodeMap>
2476    static CombinedNodeMap<InNodeMap, OutNodeMap>
2477    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2478      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2479    }
2480
2481    template <typename InNodeMap, typename OutNodeMap>
2482    static CombinedNodeMap<const InNodeMap, OutNodeMap>
2483    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2484      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2485    }
2486
2487    template <typename InNodeMap, typename OutNodeMap>
2488    static CombinedNodeMap<InNodeMap, const OutNodeMap>
2489    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2490      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2491    }
2492
2493    template <typename InNodeMap, typename OutNodeMap>
2494    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2495    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2496      return CombinedNodeMap<const InNodeMap,
2497        const OutNodeMap>(in_map, out_map);
2498    }
2499
2500    /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2501    ///
2502    /// This class adapt an original graph EdgeMap and NodeMap to
2503    /// get an edge map on the adapted graph.
2504    template <typename GraphEdgeMap, typename GraphNodeMap>
2505    class CombinedEdgeMap
2506      : public MapBase<Edge, typename GraphEdgeMap::Value> {
2507    public:
2508      typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
2509
2510      typedef typename Parent::Key Key;
2511      typedef typename Parent::Value Value;
2512
2513      /// \brief Constructor
2514      ///
2515      /// Constructor.
2516      CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2517        : edge_map(_edge_map), node_map(_node_map) {}
2518
2519      /// \brief The subscript operator.
2520      ///
2521      /// The subscript operator.
2522      void set(const Edge& edge, const Value& val) {
2523        if (Parent::origEdge(edge)) {
2524          edge_map.set(edge, val);
2525        } else {
2526          node_map.set(edge, val);
2527        }
2528      }
2529
2530      /// \brief The const subscript operator.
2531      ///
2532      /// The const subscript operator.
2533      Value operator[](const Key& edge) const {
2534        if (Parent::origEdge(edge)) {
2535          return edge_map[edge];
2536        } else {
2537          return node_map[edge];
2538        }
2539      }     
2540
2541      /// \brief The const subscript operator.
2542      ///
2543      /// The const subscript operator.
2544      Value& operator[](const Key& edge) {
2545        if (Parent::origEdge(edge)) {
2546          return edge_map[edge];
2547        } else {
2548          return node_map[edge];
2549        }
2550      }     
2551     
2552    private:
2553      GraphEdgeMap& edge_map;
2554      GraphNodeMap& node_map;
2555    };
2556                   
2557    /// \brief Just gives back a combined edge map.
2558    ///
2559    /// Just gives back a combined edge map.
2560    template <typename GraphEdgeMap, typename GraphNodeMap>
2561    static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2562    combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2563      return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2564    }
2565
2566    template <typename GraphEdgeMap, typename GraphNodeMap>
2567    static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2568    combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2569      return CombinedEdgeMap<const GraphEdgeMap,
2570        GraphNodeMap>(edge_map, node_map);
2571    }
2572
2573    template <typename GraphEdgeMap, typename GraphNodeMap>
2574    static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2575    combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2576      return CombinedEdgeMap<GraphEdgeMap,
2577        const GraphNodeMap>(edge_map, node_map);
2578    }
2579
2580    template <typename GraphEdgeMap, typename GraphNodeMap>
2581    static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2582    combinedEdgeMap(const GraphEdgeMap& edge_map,
2583                    const GraphNodeMap& node_map) {
2584      return CombinedEdgeMap<const GraphEdgeMap,
2585        const GraphNodeMap>(edge_map, node_map);
2586    }
2587
2588  };
2589
2590
2591} //namespace lemon
2592
2593#endif //LEMON_GRAPH_ADAPTOR_H
2594
Note: See TracBrowser for help on using the repository browser.