COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

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