COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Timestamp:
04/30/04 16:02:10 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@655
Message:

gw

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/bipartite_graph_wrapper.h

    r495 r496  
    11// -*- c++ -*-
    2 #ifndef HUGO_GRAPH_WRAPPER_H
    3 #define HUGO_GRAPH_WRAPPER_H
     2#ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H
     3#define HUGO_BIPARTITE_GRAPH_WRAPPER_H
    44
    55///\ingroup gwrappers
    … …  
    1313#include <invalid.h>
    1414#include <iter_map.h>
     15#include <graph_wrapper.h>
    1516
    1617namespace hugo {
    17 
    18   // Graph wrappers
    19 
    20   /// \addtogroup gwrappers
    21   /// A main parts of HUGOlib are the different graph structures,
    22   /// generic graph algorithms, graph concepts which couple these, and
    23   /// graph wrappers. While the previous ones are more or less clear, the
    24   /// latter notion needs further explanation.
    25   /// Graph wrappers are graph classes which serve for considering graph
    26   /// structures in different ways. A short example makes the notion much
    27   /// clearer.
    28   /// Suppose that we have an instance \c g of a directed graph
    29   /// type say \c ListGraph and an algorithm
    30   /// \code template<typename Graph> int algorithm(const Graph&); \endcode
    31   /// is needed to run on the reversely oriented graph.
    32   /// It may be expensive (in time or in memory usage) to copy
    33   /// \c g with the reverse orientation.
    34   /// Thus, a wrapper class
    35   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
    36   /// The code looks as follows
    37   /// \code
    38   /// ListGraph g;
    39   /// RevGraphWrapper<ListGraph> rgw(g);
    40   /// int result=algorithm(rgw);
    41   /// \endcode
    42   /// After running the algorithm, the original graph \c g
    43   /// remains untouched. Thus the graph wrapper used above is to consider the
    44   /// original graph with reverse orientation.
    45   /// This techniques gives rise to an elegant code, and
    46   /// based on stable graph wrappers, complex algorithms can be
    47   /// implemented easily.
    48   /// In flow, circulation and bipartite matching problems, the residual
    49   /// graph is of particular importance. Combining a wrapper implementing
    50   /// this, shortest path algorithms and minimum mean cycle algorithms,
    51   /// a range of weighted and cardinality optimization algorithms can be
    52   /// obtained. For lack of space, for other examples,
    53   /// the interested user is referred to the detailed documentation of graph
    54   /// wrappers.
    55   /// The behavior of graph wrappers can be very different. Some of them keep
    56   /// capabilities of the original graph while in other cases this would be
    57   /// meaningless. This means that the concepts that they are a model of depend
    58   /// on the graph wrapper, and the wrapped graph(s).
    59   /// If an edge of \c rgw is deleted, this is carried out by
    60   /// deleting the corresponding edge of \c g. But for a residual
    61   /// graph, this operation has no sense.
    62   /// Let we stand one more example here to simplify your work.
    63   /// wrapper class
    64   /// \code template<typename Graph> class RevGraphWrapper; \endcode
    65   /// has constructor
    66   /// <tt> RevGraphWrapper(Graph& _g)</tt>.
    67   /// This means that in a situation,
    68   /// when a <tt> const ListGraph& </tt> reference to a graph is given,
    69   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    70   /// \code
    71   /// int algorithm1(const ListGraph& g) {
    72   ///   RevGraphWrapper<const ListGraph> rgw(g);
    73   ///   return algorithm2(rgw);
    74   /// }
    75   /// \endcode
    76 
    77   /// \addtogroup gwrappers
    78   /// @{
    79 
    80   ///Base type for the Graph Wrappers
    81 
    82   ///This is the base type for the Graph Wrappers.
    83   ///\todo Some more docs...
    84   ///
    85   ///\author Marton Makai
    86  
    87   template<typename Graph>
    88   class GraphWrapper {
    89   protected:
    90     Graph* graph;
    91  
    92   public:
    93     typedef Graph BaseGraph;
    94     typedef Graph ParentGraph;
    95 
    96 //     GraphWrapper() : graph(0) { }
    97     GraphWrapper(Graph& _graph) : graph(&_graph) { }
    98 //     void setGraph(Graph& _graph) { graph=&_graph; }
    99 //     Graph& getGraph() const { return *graph; }
    100  
    101 //    typedef typename Graph::Node Node;
    102     class Node : public Graph::Node {
    103       friend class GraphWrapper<Graph>;
    104     public:
    105       Node() { }
    106       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
    107       Node(const Invalid& i) : Graph::Node(i) { }
    108     };
    109     class NodeIt {
    110       friend class GraphWrapper<Graph>;
    111       typename Graph::NodeIt n;
    112      public:
    113       NodeIt() { }
    114       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    115       NodeIt(const Invalid& i) : n(i) { }
    116       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
    117       operator Node() const { return Node(typename Graph::Node(n)); }
    118     };
    119 //    typedef typename Graph::Edge Edge;
    120     class Edge : public Graph::Edge {
    121       friend class GraphWrapper<Graph>;
    122     public:
    123       Edge() { }
    124       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
    125       Edge(const Invalid& i) : Graph::Edge(i) { }
    126     };
    127     class OutEdgeIt {
    128       friend class GraphWrapper<Graph>;
    129       typename Graph::OutEdgeIt e;
    130     public:
    131       OutEdgeIt() { }
    132       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    133       OutEdgeIt(const Invalid& i) : e(i) { }
    134       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    135         e(*(_G.graph), typename Graph::Node(_n)) { }
    136       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    137     };
    138     class InEdgeIt {
    139       friend class GraphWrapper<Graph>;
    140       typename Graph::InEdgeIt e;
    141     public:
    142       InEdgeIt() { }
    143       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    144       InEdgeIt(const Invalid& i) : e(i) { }
    145       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    146         e(*(_G.graph), typename Graph::Node(_n)) { }
    147       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    148     };
    149     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    150     class EdgeIt {
    151       friend class GraphWrapper<Graph>;
    152       typename Graph::EdgeIt e;
    153     public:
    154       EdgeIt() { }
    155       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    156       EdgeIt(const Invalid& i) : e(i) { }
    157       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
    158       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    159     };
    160    
    161     NodeIt& first(NodeIt& i) const {
    162       i=NodeIt(*this); return i;
    163     }
    164     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    165       i=OutEdgeIt(*this, p); return i;
    166     }
    167     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    168       i=InEdgeIt(*this, p); return i;
    169     }
    170     EdgeIt& first(EdgeIt& i) const {
    171       i=EdgeIt(*this); return i;
    172     }
    173 
    174     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    175     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    176     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    177     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    178 
    179     Node tail(const Edge& e) const {
    180       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    181     Node head(const Edge& e) const {
    182       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    183 
    184     bool valid(const Node& n) const {
    185       return graph->valid(static_cast<typename Graph::Node>(n)); }
    186     bool valid(const Edge& e) const {
    187       return graph->valid(static_cast<typename Graph::Edge>(e)); }
    188 
    189     int nodeNum() const { return graph->nodeNum(); }
    190     int edgeNum() const { return graph->edgeNum(); }
    191  
    192     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    193     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    194     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    195     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    196  
    197     Node addNode() const { return Node(graph->addNode()); }
    198     Edge addEdge(const Node& tail, const Node& head) const {
    199       return Edge(graph->addEdge(tail, head)); }
    200 
    201     void erase(const Node& i) const { graph->erase(i); }
    202     void erase(const Edge& i) const { graph->erase(i); }
    203  
    204     void clear() const { graph->clear(); }
    205    
    206     template<typename T> class NodeMap : public Graph::template NodeMap<T> {
    207       typedef typename Graph::template NodeMap<T> Parent;
    208     public:
    209       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
    210       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
    211     };
    212 
    213     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
    214       typedef typename Graph::template EdgeMap<T> Parent;
    215     public:
    216       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
    217       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
    218     };
    219   };
    220 
    221   /// A graph wrapper which reverses the orientation of the edges.
    222 
    223   /// A graph wrapper which reverses the orientation of the edges.
    224   ///
    225   ///\author Marton Makai
    226   template<typename Graph>
    227   class RevGraphWrapper : public GraphWrapper<Graph> {
    228   public:
    229 
    230     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
    231 
    232     typedef typename GraphWrapper<Graph>::Node Node;
    233     typedef typename GraphWrapper<Graph>::Edge Edge;
    234     //If Graph::OutEdgeIt is not defined
    235     //and we do not want to use RevGraphWrapper::InEdgeIt,
    236     //the typdef techinque does not work.
    237     //Unfortunately all the typedefs are instantiated in templates.
    238     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
    239     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
    240 
    241     class OutEdgeIt {
    242       friend class GraphWrapper<Graph>;
    243       friend class RevGraphWrapper<Graph>;
    244       typename Graph::InEdgeIt e;
    245     public:
    246       OutEdgeIt() { }
    247       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    248       OutEdgeIt(const Invalid& i) : e(i) { }
    249       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    250         e(*(_G.graph), typename Graph::Node(_n)) { }
    251       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    252     };
    253     class InEdgeIt {
    254       friend class GraphWrapper<Graph>;
    255       friend class RevGraphWrapper<Graph>;
    256       typename Graph::OutEdgeIt e;
    257     public:
    258       InEdgeIt() { }
    259       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    260       InEdgeIt(const Invalid& i) : e(i) { }
    261       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    262         e(*(_G.graph), typename Graph::Node(_n)) { }
    263       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    264     };
    265 
    266     using GraphWrapper<Graph>::first;
    267     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    268       i=OutEdgeIt(*this, p); return i;
    269     }
    270     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    271       i=InEdgeIt(*this, p); return i;
    272     }
    273 
    274     using GraphWrapper<Graph>::next;
    275     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    276     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    277 
    278     Node aNode(const OutEdgeIt& e) const {
    279       return Node(this->graph->aNode(e.e)); }
    280     Node aNode(const InEdgeIt& e) const {
    281       return Node(this->graph->aNode(e.e)); }
    282     Node bNode(const OutEdgeIt& e) const {
    283       return Node(this->graph->bNode(e.e)); }
    284     Node bNode(const InEdgeIt& e) const {
    285       return Node(this->graph->bNode(e.e)); }
    286 
    287     Node tail(const Edge& e) const {
    288       return GraphWrapper<Graph>::head(e); }
    289     Node head(const Edge& e) const {
    290       return GraphWrapper<Graph>::tail(e); }
    291 
    292   };
    293 
    294   /// Wrapper for hiding nodes and edges from a graph.
    295  
    296   /// This wrapper shows a graph with filtered node-set and
    297   /// edge-set. The quick brown fox iterator jumps over
    298   /// the lazy dog nodes or edges if the values for them are false
    299   /// in the bool maps.
    300   ///
    301   ///\author Marton Makai
    302   template<typename Graph, typename NodeFilterMap,
    303            typename EdgeFilterMap>
    304   class SubGraphWrapper : public GraphWrapper<Graph> {
    305   protected:
    306     NodeFilterMap* node_filter_map;
    307     EdgeFilterMap* edge_filter_map;
    308   public:
    309 
    310     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
    311                     EdgeFilterMap& _edge_filter_map) :
    312       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
    313       edge_filter_map(&_edge_filter_map) { } 
    314 
    315     typedef typename GraphWrapper<Graph>::Node Node;
    316     class NodeIt {
    317       friend class GraphWrapper<Graph>;
    318       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    319       typename Graph::NodeIt n;
    320      public:
    321       NodeIt() { }
    322       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    323       NodeIt(const Invalid& i) : n(i) { }
    324       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    325         n(*(_G.graph)) {
    326         while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
    327           _G.graph->next(n);
    328       }
    329       operator Node() const { return Node(typename Graph::Node(n)); }
    330     };
    331     typedef typename GraphWrapper<Graph>::Edge Edge;
    332     class OutEdgeIt {
    333       friend class GraphWrapper<Graph>;
    334       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    335       typename Graph::OutEdgeIt e;
    336     public:
    337       OutEdgeIt() { }
    338       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    339       OutEdgeIt(const Invalid& i) : e(i) { }
    340       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
    341                 const Node& _n) :
    342         e(*(_G.graph), typename Graph::Node(_n)) {
    343         while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
    344           _G.graph->next(e);
    345       }
    346       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    347     };
    348     class InEdgeIt {
    349       friend class GraphWrapper<Graph>;
    350       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    351       typename Graph::InEdgeIt e;
    352     public:
    353       InEdgeIt() { }
    354       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    355       InEdgeIt(const Invalid& i) : e(i) { }
    356       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
    357                const Node& _n) :
    358         e(*(_G.graph), typename Graph::Node(_n)) {
    359         while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
    360           _G.graph->next(e);
    361       }
    362       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    363     };
    364     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    365     class EdgeIt {
    366       friend class GraphWrapper<Graph>;
    367       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    368       typename Graph::EdgeIt e;
    369     public:
    370       EdgeIt() { }
    371       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    372       EdgeIt(const Invalid& i) : e(i) { }
    373       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    374         e(*(_G.graph)) {
    375         while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
    376           _G.graph->next(e);
    377       }
    378       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    379     };
    380 
    381     NodeIt& first(NodeIt& i) const {
    382       i=NodeIt(*this); return i;
    383     }
    384     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    385       i=OutEdgeIt(*this, p); return i;
    386     }
    387     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    388       i=InEdgeIt(*this, p); return i;
    389     }
    390     EdgeIt& first(EdgeIt& i) const {
    391       i=EdgeIt(*this); return i;
    392     }
    393    
    394     NodeIt& next(NodeIt& i) const {
    395       this->graph->next(i.n);
    396       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
    397         this->graph->next(i.n); }
    398       return i;
    399     }
    400     OutEdgeIt& next(OutEdgeIt& i) const {
    401       this->graph->next(i.e);
    402       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    403         this->graph->next(i.e); }
    404       return i;
    405     }
    406     InEdgeIt& next(InEdgeIt& i) const {
    407       this->graph->next(i.e);
    408       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    409         this->graph->next(i.e); }
    410       return i;
    411     }
    412     EdgeIt& next(EdgeIt& i) const {
    413       this->graph->next(i.e);
    414       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    415         this->graph->next(i.e); }
    416       return i;
    417     }
    418 
    419     Node aNode(const OutEdgeIt& e) const {
    420       return Node(this->graph->aNode(e.e)); }
    421     Node aNode(const InEdgeIt& e) const {
    422       return Node(this->graph->aNode(e.e)); }
    423     Node bNode(const OutEdgeIt& e) const {
    424       return Node(this->graph->bNode(e.e)); }
    425     Node bNode(const InEdgeIt& e) const {
    426       return Node(this->graph->bNode(e.e)); }
    427 
    428     ///\todo
    429     ///Some doki, please.
    430     void hide(const Node& n) const { node_filter_map->set(n, false); }
    431     ///\todo
    432     ///Some doki, please.
    433     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    434 
    435     ///\todo
    436     ///Some doki, please.
    437     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    438     ///\todo
    439     ///Some doki, please.
    440     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    441 
    442     ///\todo
    443     ///Some doki, please.
    444     bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
    445     ///\todo
    446     ///Some doki, please.
    447     bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
    448   };
    449 
    450   /// A wrapper for forgetting the orientation of a graph.
    451 
    452   /// A wrapper for getting an undirected graph by forgetting
    453   /// the orientation of a directed one.
    454   template<typename Graph>
    455   class UndirGraphWrapper : public GraphWrapper<Graph> {
    456   public:
    457     typedef typename GraphWrapper<Graph>::Node Node;
    458     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    459     typedef typename GraphWrapper<Graph>::Edge Edge;
    460     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    461 
    462     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
    463 
    464     class OutEdgeIt {
    465       friend class UndirGraphWrapper<Graph>;
    466       bool out_or_in; //true iff out
    467       typename Graph::OutEdgeIt out;
    468       typename Graph::InEdgeIt in;
    469     public:
    470       OutEdgeIt() { }
    471       OutEdgeIt(const Invalid& i) : Edge(i) { }
    472       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
    473         out_or_in=true; _G.graph->first(out, _n);
    474         if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
    475       }
    476       operator Edge() const {
    477         if (out_or_in) return Edge(out); else return Edge(in);
    478       }
    479     };
    480 
    481 //FIXME InEdgeIt
    482     typedef OutEdgeIt InEdgeIt;
    483 
    484     using GraphWrapper<Graph>::first;
    485 //     NodeIt& first(NodeIt& i) const {
    486 //       i=NodeIt(*this); return i;
    487 //     }
    488     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    489       i=OutEdgeIt(*this, p); return i;
    490     }
    491 //FIXME
    492 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    493 //       i=InEdgeIt(*this, p); return i;
    494 //     }
    495 //     EdgeIt& first(EdgeIt& i) const {
    496 //       i=EdgeIt(*this); return i;
    497 //     }
    498 
    499     using GraphWrapper<Graph>::next;
    500 //     NodeIt& next(NodeIt& n) const {
    501 //       GraphWrapper<Graph>::next(n);
    502 //       return n;
    503 //     }
    504     OutEdgeIt& next(OutEdgeIt& e) const {
    505       if (e.out_or_in) {
    506         typename Graph::Node n=this->graph->tail(e.out);
    507         this->graph->next(e.out);
    508         if (!this->graph->valid(e.out)) {
    509           e.out_or_in=false; this->graph->first(e.in, n); }
    510       } else {
    511         this->graph->next(e.in);
    512       }
    513       return e;
    514     }
    515     //FIXME InEdgeIt
    516 //     EdgeIt& next(EdgeIt& e) const {
    517 //       GraphWrapper<Graph>::next(n);
    518 // //      graph->next(e.e);
    519 //       return e;
    520 //     }
    521 
    522     Node aNode(const OutEdgeIt& e) const {
    523       if (e.out_or_in) return this->graph->tail(e); else
    524         return this->graph->head(e); }
    525     Node bNode(const OutEdgeIt& e) const {
    526       if (e.out_or_in) return this->graph->head(e); else
    527         return this->graph->tail(e); }
    528   };
    529  
    530   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    531 
    532   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    533   template<typename Graph, typename Number,
    534            typename CapacityMap, typename FlowMap>
    535   class ResGraphWrapper : public GraphWrapper<Graph> {
    536   protected:
    537     const CapacityMap* capacity;
    538     FlowMap* flow;
    539   public:
    540 
    541     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
    542                     FlowMap& _flow) :
    543       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
    544 
    545     class Edge;
    546     class OutEdgeIt;
    547     friend class Edge;
    548     friend class OutEdgeIt;
    549 
    550     typedef typename GraphWrapper<Graph>::Node Node;
    551     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    552     class Edge : public Graph::Edge {
    553       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    554     protected:
    555       bool forward; //true, iff forward
    556 //      typename Graph::Edge e;
    557     public:
    558       Edge() { }
    559       Edge(const typename Graph::Edge& _e, bool _forward) :
    560         Graph::Edge(_e), forward(_forward) { }
    561       Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
    562 //the unique invalid iterator
    563       friend bool operator==(const Edge& u, const Edge& v) {
    564         return (v.forward==u.forward &&
    565                 static_cast<typename Graph::Edge>(u)==
    566                 static_cast<typename Graph::Edge>(v));
    567       }
    568       friend bool operator!=(const Edge& u, const Edge& v) {
    569         return (v.forward!=u.forward ||
    570                 static_cast<typename Graph::Edge>(u)!=
    571                 static_cast<typename Graph::Edge>(v));
    572       }
    573     };
    574 
    575     class OutEdgeIt {
    576       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    577     protected:
    578       typename Graph::OutEdgeIt out;
    579       typename Graph::InEdgeIt in;
    580       bool forward;
    581     public:
    582       OutEdgeIt() { }
    583       //FIXME
    584 //      OutEdgeIt(const Edge& e) : Edge(e) { }
    585       OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
    586 //the unique invalid iterator
    587       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
    588         forward=true;
    589         resG.graph->first(out, v);
    590         while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
    591         if (!resG.graph->valid(out)) {
    592           forward=false;
    593           resG.graph->first(in, v);
    594           while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
    595         }
    596       }
    597       operator Edge() const {
    598 //      Edge e;
    599 //      e.forward=this->forward;
    600 //      if (this->forward) e=out; else e=in;
    601 //      return e;
    602         if (this->forward)
    603           return Edge(out, this->forward);
    604         else
    605           return Edge(in, this->forward);
    606       }
    607     };
    608 
    609     class InEdgeIt {
    610       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    611     protected:
    612       typename Graph::OutEdgeIt out;
    613       typename Graph::InEdgeIt in;
    614       bool forward;
    615     public:
    616       InEdgeIt() { }
    617       //FIXME
    618 //      OutEdgeIt(const Edge& e) : Edge(e) { }
    619       InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
    620 //the unique invalid iterator
    621       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
    622         forward=true;
    623         resG.graph->first(in, v);
    624         while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
    625         if (!resG.graph->valid(in)) {
    626           forward=false;
    627           resG.graph->first(out, v);
    628           while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
    629         }
    630       }
    631       operator Edge() const {
    632 //      Edge e;
    633 //      e.forward=this->forward;
    634 //      if (this->forward) e=out; else e=in;
    635 //      return e;
    636         if (this->forward)
    637           return Edge(in, this->forward);
    638         else
    639           return Edge(out, this->forward);
    640       }
    641     };
    642 
    643     class EdgeIt {
    644       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    645     protected:
    646       typename Graph::EdgeIt e;
    647       bool forward;
    648     public:
    649       EdgeIt() { }
    650       EdgeIt(const Invalid& i) : e(i), forward(false) { }
    651       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
    652         forward=true;
    653         resG.graph->first(e);
    654         while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
    655         if (!resG.graph->valid(e)) {
    656           forward=false;
    657           resG.graph->first(e);
    658           while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
    659         }
    660       }
    661       operator Edge() const {
    662         return Edge(e, this->forward);
    663       }
    664     };
    665 
    666     using GraphWrapper<Graph>::first;
    667 //     NodeIt& first(NodeIt& i) const {
    668 //       i=NodeIt(*this); return i;
    669 //     }
    670     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    671       i=OutEdgeIt(*this, p); return i;
    672     }
    673 //    FIXME not tested
    674     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    675       i=InEdgeIt(*this, p); return i;
    676     }
    677     EdgeIt& first(EdgeIt& i) const {
    678       i=EdgeIt(*this); return i;
    679     }
    680  
    681     using GraphWrapper<Graph>::next;
    682 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    683     OutEdgeIt& next(OutEdgeIt& e) const {
    684       if (e.forward) {
    685         Node v=this->graph->aNode(e.out);
    686         this->graph->next(e.out);
    687         while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
    688           this->graph->next(e.out); }
    689         if (!this->graph->valid(e.out)) {
    690           e.forward=false;
    691           this->graph->first(e.in, v);
    692           while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
    693             this->graph->next(e.in); }
    694         }
    695       } else {
    696         this->graph->next(e.in);
    697         while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
    698           this->graph->next(e.in); }
    699       }
    700       return e;
    701     }
    702 //     FIXME Not tested
    703     InEdgeIt& next(InEdgeIt& e) const {
    704       if (e.forward) {
    705         Node v=this->graph->aNode(e.in);
    706         this->graph->next(e.in);
    707         while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
    708           this->graph->next(e.in); }
    709         if (!this->graph->valid(e.in)) {
    710           e.forward=false;
    711           this->graph->first(e.out, v);
    712           while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
    713             this->graph->next(e.out); }
    714         }
    715       } else {
    716         this->graph->next(e.out);
    717         while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
    718           this->graph->next(e.out); }
    719       }
    720       return e;
    721     }
    722     EdgeIt& next(EdgeIt& e) const {
    723       if (e.forward) {
    724         this->graph->next(e.e);
    725         while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
    726           this->graph->next(e.e); }
    727         if (!this->graph->valid(e.e)) {
    728           e.forward=false;
    729           this->graph->first(e.e);
    730           while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
    731             this->graph->next(e.e); }
    732         }
    733       } else {
    734         this->graph->next(e.e);
    735         while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
    736           this->graph->next(e.e); }
    737       }
    738       return e;
    739     }
    740 
    741     Node tail(Edge e) const {
    742       return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
    743     Node head(Edge e) const {
    744       return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
    745 
    746     Node aNode(OutEdgeIt e) const {
    747       return ((e.forward) ? this->graph->aNode(e.out) :
    748               this->graph->aNode(e.in)); }
    749     Node bNode(OutEdgeIt e) const {
    750       return ((e.forward) ? this->graph->bNode(e.out) :
    751               this->graph->bNode(e.in)); }
    752 
    753     Node aNode(InEdgeIt e) const {
    754       return ((e.forward) ? this->graph->aNode(e.in) :
    755               this->graph->aNode(e.out)); }
    756     Node bNode(InEdgeIt e) const {
    757       return ((e.forward) ? this->graph->bNode(e.in) :
    758               this->graph->bNode(e.out)); }
    759 
    760 //    int nodeNum() const { return graph->nodeNum(); }
    761     //FIXME
    762     void edgeNum() const { }
    763     //int edgeNum() const { return graph->edgeNum(); }
    764 
    765 
    766 //    int id(Node v) const { return graph->id(v); }
    767 
    768     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    769     bool valid(Edge e) const {
    770       return this->graph->valid(e);
    771         //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
    772     }
    773 
    774     void augment(const Edge& e, Number a) const {
    775       if (e.forward) 
    776 //      flow->set(e.out, flow->get(e.out)+a);
    777         flow->set(e, (*flow)[e]+a);
    778       else 
    779 //      flow->set(e.in, flow->get(e.in)-a);
    780         flow->set(e, (*flow)[e]-a);
    781     }
    782 
    783     Number resCap(const Edge& e) const {
    784       if (e.forward)
    785 //      return (capacity->get(e.out)-flow->get(e.out));
    786         return ((*capacity)[e]-(*flow)[e]);
    787       else
    788 //      return (flow->get(e.in));
    789         return ((*flow)[e]);
    790     }
    791 
    792 //     Number resCap(typename Graph::OutEdgeIt out) const {
    793 // //      return (capacity->get(out)-flow->get(out));
    794 //       return ((*capacity)[out]-(*flow)[out]);
    795 //     }
    796    
    797 //     Number resCap(typename Graph::InEdgeIt in) const {
    798 // //      return (flow->get(in));
    799 //       return ((*flow)[in]);
    800 //     }
    801 
    802     template <typename T>
    803     class EdgeMap {
    804       typename Graph::template EdgeMap<T> forward_map, backward_map;
    805     public:
    806       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
    807       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
    808       void set(Edge e, T a) {
    809         if (e.forward)
    810           forward_map.set(e.out, a);
    811         else
    812           backward_map.set(e.in, a);
    813       }
    814       T operator[](Edge e) const {
    815         if (e.forward)
    816           return forward_map[e.out];
    817         else
    818           return backward_map[e.in];
    819       }
    820 //       T get(Edge e) const {
    821 //      if (e.out_or_in)
    822 //        return forward_map.get(e.out);
    823 //      else
    824 //        return backward_map.get(e.in);
    825 //       }
    826     };
    827   };
    828 
    829   /// ErasingFirstGraphWrapper for blocking flows.
    830 
    831   /// ErasingFirstGraphWrapper for blocking flows.
    832   ///
    833   ///\author Marton Makai
    834   template<typename Graph, typename FirstOutEdgesMap>
    835   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
    836   protected:
    837     FirstOutEdgesMap* first_out_edges;
    838   public:
    839     ErasingFirstGraphWrapper(Graph& _graph,
    840                              FirstOutEdgesMap& _first_out_edges) :
    841       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
    842 
    843     typedef typename GraphWrapper<Graph>::Node Node;
    844 //     class NodeIt {
    845 //       friend class GraphWrapper<Graph>;
    846 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    847 //       typename Graph::NodeIt n;
    848 //      public:
    849 //       NodeIt() { }
    850 //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    851 //       NodeIt(const Invalid& i) : n(i) { }
    852 //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    853 //      n(*(_G.graph)) { }
    854 //       operator Node() const { return Node(typename Graph::Node(n)); }
    855 //     };
    856     typedef typename GraphWrapper<Graph>::Edge Edge;
    857     class OutEdgeIt {
    858       friend class GraphWrapper<Graph>;
    859       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    860 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    861       typename Graph::OutEdgeIt e;
    862     public:
    863       OutEdgeIt() { }
    864       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    865       OutEdgeIt(const Invalid& i) : e(i) { }
    866       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    867                 const Node& _n) :
    868         e((*_G.first_out_edges)[_n]) { }
    869       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    870     };
    871     class InEdgeIt {
    872       friend class GraphWrapper<Graph>;
    873       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    874 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
    875       typename Graph::InEdgeIt e;
    876     public:
    877       InEdgeIt() { }
    878       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    879       InEdgeIt(const Invalid& i) : e(i) { }
    880       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    881                const Node& _n) :
    882         e(*(_G.graph), typename Graph::Node(_n)) { }
    883       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    884     };
    885     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    886     class EdgeIt {
    887       friend class GraphWrapper<Graph>;
    888       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    889 //      typedef typename Graph::EdgeIt GraphEdgeIt;
    890       typename Graph::EdgeIt e;
    891     public:
    892       EdgeIt() { }
    893       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    894       EdgeIt(const Invalid& i) : e(i) { }
    895       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    896         e(*(_G.graph)) { }
    897       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    898     };
    899 
    900     using GraphWrapper<Graph>::first;
    901 //     NodeIt& first(NodeIt& i) const {
    902 //       i=NodeIt(*this); return i;
    903 //     }
    904     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    905       i=OutEdgeIt(*this, p); return i;
    906     }
    907     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    908       i=InEdgeIt(*this, p); return i;
    909     }
    910     EdgeIt& first(EdgeIt& i) const {
    911       i=EdgeIt(*this); return i;
    912     }
    913 
    914     using GraphWrapper<Graph>::next;
    915 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    916     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    917     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    918     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
    919    
    920     Node aNode(const OutEdgeIt& e) const {
    921       return Node(this->graph->aNode(e.e)); }
    922     Node aNode(const InEdgeIt& e) const {
    923       return Node(this->graph->aNode(e.e)); }
    924     Node bNode(const OutEdgeIt& e) const {
    925       return Node(this->graph->bNode(e.e)); }
    926     Node bNode(const InEdgeIt& e) const {
    927       return Node(this->graph->bNode(e.e)); }
    928 
    929     void erase(const OutEdgeIt& e) const {
    930       OutEdgeIt f=e;
    931       this->next(f);
    932       first_out_edges->set(this->tail(e), f.e);
    933     }
    934   };
    93518
    93619  /// A wrapper for composing a bipartite graph.
Note: See TracChangeset for help on using the changeset viewer.