COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 496:7c463a7635d4 in lemon-0.x


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

Location:
src/work/marci
Files:
6 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.

  • src/work/marci/bipartite_graph_wrapper_test.cc

    r480 r496  
    1111#include <bfs_iterator.h>
    1212#include <graph_wrapper.h>
     13#include <bipartite_graph_wrapper.h>
    1314#include <maps.h>
    1415#include <max_flow.h>

  • src/work/marci/bipartite_matching_try.cc

    r480 r496  
    1212#include <bfs_iterator.h>
    1313#include <graph_wrapper.h>
     14#include <bipartite_graph_wrapper.h>
    1415#include <maps.h>
    1516#include <max_flow.h>

  • src/work/marci/graph_wrapper.h

    r491 r496  
    934934  };
    935935
    936   /// A wrapper for composing a bipartite graph.
    937   /// \c _graph have to be a reference to a graph of type \c Graph
    938   /// and \c _s_false_t_true_map is an \c IterableBoolMap
    939   /// reference containing the elements for the
    940   /// color classes S and T. \c _graph is to be referred to an undirected
    941   /// graph or a directed graph with edges oriented from S to T.
    942   ///
    943   ///\author Marton Makai
    944   template<typename Graph>
    945   class BipartiteGraphWrapper : public GraphWrapper<Graph> {
    946     typedef IterableBoolMap< typename Graph::template NodeMap<int> >
    947     SFalseTTrueMap;
    948     SFalseTTrueMap* s_false_t_true_map;
    949 
    950   public:
    951     //marci
    952     //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
    953     //static const bool S_CLASS=false;
    954     //static const bool T_CLASS=true;
    955    
    956     bool S_CLASS;
    957     bool T_CLASS;
    958 
    959     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
    960       : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),
    961       S_CLASS(false), T_CLASS(true) { }
    962     typedef typename GraphWrapper<Graph>::Node Node;
    963     //using GraphWrapper<Graph>::NodeIt;
    964     typedef typename GraphWrapper<Graph>::Edge Edge;
    965     //using GraphWrapper<Graph>::EdgeIt;
    966     class ClassNodeIt;
    967     friend class ClassNodeIt;
    968     class OutEdgeIt;
    969     friend class OutEdgeIt;
    970     class InEdgeIt;
    971     friend class InEdgeIt;
    972     class ClassNodeIt {
    973       friend class BipartiteGraphWrapper<Graph>;
    974     protected:
    975       Node n;
    976     public:
    977       ClassNodeIt() { }
    978       ClassNodeIt(const Invalid& i) : n(i) { }
    979       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
    980         _G.s_false_t_true_map->first(n, _class);
    981       }
    982       //FIXME needed in new concept, important here
    983       ClassNodeIt(const Node& _n) : n(_n) { }
    984       operator Node() const { return n; }
    985     };
    986 //     class SNodeIt {
    987 //       Node n;
    988 //     public:
    989 //       SNodeIt() { }
    990 //       SNodeIt(const Invalid& i) : n(i) { }
    991 //       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
    992 //      _G.s_false_t_true_map->first(n, false);
    993 //       }
    994 //       operator Node() const { return n; }
    995 //     };
    996 //     class TNodeIt {
    997 //       Node n;
    998 //     public:
    999 //       TNodeIt() { }
    1000 //       TNodeIt(const Invalid& i) : n(i) { }
    1001 //       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
    1002 //      _G.s_false_t_true_map->first(n, true);
    1003 //       }
    1004 //       operator Node() const { return n; }
    1005 //     };
    1006     class OutEdgeIt {
    1007       friend class BipartiteGraphWrapper<Graph>;
    1008     protected:
    1009       typename Graph::OutEdgeIt e;
    1010     public:
    1011       OutEdgeIt() { }
    1012       OutEdgeIt(const Invalid& i) : e(i) { }
    1013       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    1014         if (!(*(_G.s_false_t_true_map))[_n])
    1015           e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
    1016         else
    1017           e=INVALID;
    1018       }
    1019       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1020     };
    1021     class InEdgeIt {
    1022       friend class BipartiteGraphWrapper<Graph>;
    1023     protected:
    1024       typename Graph::InEdgeIt e;
    1025     public:
    1026       InEdgeIt() { }
    1027       InEdgeIt(const Invalid& i) : e(i) { }
    1028       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    1029         if ((*(_G.s_false_t_true_map))[_n])
    1030           e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
    1031         else
    1032           e=INVALID;
    1033       }
    1034       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1035     };
    1036 
    1037     using GraphWrapper<Graph>::first;
    1038     ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
    1039       n=ClassNodeIt(*this, _class) ; return n; }
    1040 //    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
    1041 //    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
    1042     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    1043       i=OutEdgeIt(*this, p); return i;
    1044     }
    1045     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    1046       i=InEdgeIt(*this, p); return i;
    1047     }
    1048 
    1049     using GraphWrapper<Graph>::next;
    1050     ClassNodeIt& next(ClassNodeIt& n) const {
    1051       this->s_false_t_true_map->next(n.n); return n;
    1052     }
    1053 //     SNodeIt& next(SNodeIt& n) const {
    1054 //       this->s_false_t_true_map->next(n); return n;
    1055 //     }
    1056 //     TNodeIt& next(TNodeIt& n) const {
    1057 //       this->s_false_t_true_map->next(n); return n;
    1058 //     }
    1059     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    1060     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    1061 
    1062     Node tail(const Edge& e) {
    1063       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
    1064         return Node(this->graph->tail(e));
    1065       else
    1066         return Node(this->graph->head(e));     
    1067     }
    1068     Node head(const Edge& e) {
    1069       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
    1070         return Node(this->graph->head(e));
    1071       else
    1072         return Node(this->graph->tail(e));     
    1073     }
    1074 
    1075     Node aNode(const OutEdgeIt& e) const {
    1076       return Node(this->graph->aNode(e.e));
    1077     }
    1078     Node aNode(const InEdgeIt& e) const {
    1079       return Node(this->graph->aNode(e.e));
    1080     }
    1081     Node bNode(const OutEdgeIt& e) const {
    1082       return Node(this->graph->bNode(e.e));
    1083     }
    1084     Node bNode(const InEdgeIt& e) const {
    1085       return Node(this->graph->bNode(e.e));
    1086     }
    1087 
    1088     bool inSClass(const Node& n) const {
    1089       return !(*(this->s_false_t_true_map))[n];
    1090     }
    1091     bool inTClass(const Node& n) const {
    1092       return (*(this->s_false_t_true_map))[n];
    1093     }
    1094   };
    1095 
    1096   template<typename Graph>
    1097   class stGraphWrapper;
    1098 
    1099 //   template<typename Graph>
    1100 //   std::ostream&
    1101 //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {
    1102 //     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
    1103 //     return os;
    1104 //   }
    1105 //   template<typename Graph>
    1106 //   std::ostream&
    1107 //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {
    1108 //     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
    1109 //       " node: " << i.n << ")";
    1110 //     return os;
    1111 //   }
    1112 
    1113   /// experimentral, do not try it.
    1114   /// It eats a bipartite graph, oriented from S to T.
    1115   /// Such one can be made e.g. by the above wrapper.
    1116   ///
    1117   ///\author Marton Makai
    1118   template<typename Graph>
    1119   class stGraphWrapper : public GraphWrapper<Graph> {
    1120   public:
    1121     class Node;
    1122     friend class Node;
    1123 //GN, int
    1124 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
    1125 //es a vege a false azaz (invalid, 3)   
    1126     class NodeIt;
    1127     friend class NodeIt;
    1128 //GNI, int
    1129     class Edge;
    1130     friend class Edge;
    1131 //GE, int, GN
    1132 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
    1133 //invalid: (invalid, 3, invalid)
    1134     class OutEdgeIt;
    1135     friend class OutEdgeIt;
    1136 //GO, int, GNI
    1137 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
    1138 //s-bol (invalid, 1, first), ... (invalid, 3, invalid)
    1139 //t-bol (invalid, 3, invalid)
    1140     class InEdgeIt;
    1141     friend class InEdgeIt;
    1142 //GI, int, GNI
    1143 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
    1144 //s-be (invalid, 3, invalid)
    1145 //t-be (invalid, 2, first), ... (invalid, 3, invalid)
    1146     class EdgeIt;
    1147     friend class EdgeIt;
    1148 //(first, 0, invalid) ...
    1149 //(invalid, 1, vmi)
    1150 //(invalid, 2, vmi)
    1151 //invalid, 3, invalid)
    1152     template <typename T> class NodeMap;
    1153     template <typename T, typename Parent> class EdgeMap;
    1154 
    1155 //    template <typename T> friend class NodeMap;
    1156 //    template <typename T> friend class EdgeMap;
    1157 
    1158     const Node S_NODE;
    1159     const Node T_NODE;
    1160 
    1161     static const bool S_CLASS=false;
    1162     static const bool T_CLASS=true;
    1163 
    1164     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
    1165                                     S_NODE(INVALID, 1),
    1166                                     T_NODE(INVALID, 2) { }
    1167 
    1168    
    1169 //    std::ostream&
    1170 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
    1171 //    friend std::ostream&
    1172 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
    1173 //    friend std::ostream&
    1174 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
    1175 
    1176     class Node : public Graph::Node {
    1177     protected:
    1178       friend class GraphWrapper<Graph>;
    1179       friend class stGraphWrapper<Graph>;
    1180       template <typename T> friend class NodeMap;
    1181       friend class Edge;
    1182       friend class OutEdgeIt;
    1183       friend class InEdgeIt;
    1184       friend class EdgeIt;
    1185       int spec;
    1186     public:
    1187       Node() { }
    1188       Node(const typename Graph::Node& _n, int _spec=0) :
    1189         Graph::Node(_n), spec(_spec) { }
    1190       Node(const Invalid& i) : Graph::Node(i), spec(3) { }
    1191       friend bool operator==(const Node& u, const Node& v) {
    1192         return (u.spec==v.spec &&
    1193                 static_cast<typename Graph::Node>(u)==
    1194                 static_cast<typename Graph::Node>(v));
    1195       }
    1196       friend bool operator!=(const Node& u, const Node& v) {
    1197         return (v.spec!=u.spec ||
    1198                 static_cast<typename Graph::Node>(u)!=
    1199                 static_cast<typename Graph::Node>(v));
    1200       }
    1201 //      template<typename G>
    1202 //      friend std::ostream&
    1203 //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);
    1204       friend std::ostream& operator<< (std::ostream& os, const Node& i);
    1205       int getSpec() const { return spec; }
    1206     };
    1207 
    1208     class NodeIt {
    1209       friend class GraphWrapper<Graph>;
    1210       friend class stGraphWrapper<Graph>;
    1211       typename Graph::NodeIt n;
    1212       int spec;
    1213      public:
    1214       NodeIt() { }
    1215       NodeIt(const typename Graph::NodeIt& _n, int _spec) :
    1216         n(_n), spec(_spec) { }
    1217       NodeIt(const Invalid& i) : n(i), spec(3) { }
    1218       NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
    1219         if (!_G.graph->valid(n)) spec=1;
    1220       }
    1221       operator Node() const { return Node(n, spec); }
    1222     };
    1223 
    1224     class Edge : public Graph::Edge {
    1225       friend class GraphWrapper<Graph>;
    1226       friend class stGraphWrapper<Graph>;
    1227       template <typename T, typename Parent> friend class EdgeMap;
    1228       int spec;
    1229       typename Graph::Node n;
    1230     public:
    1231       Edge() { }
    1232       Edge(const typename Graph::Edge& _e, int _spec,
    1233            const typename Graph::Node& _n) :
    1234         Graph::Edge(_e), spec(_spec), n(_n) {
    1235       }
    1236       Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
    1237       friend bool operator==(const Edge& u, const Edge& v) {
    1238         return (u.spec==v.spec &&
    1239                 static_cast<typename Graph::Edge>(u)==
    1240                 static_cast<typename Graph::Edge>(v) &&
    1241                 u.n==v.n);
    1242       }
    1243       friend bool operator!=(const Edge& u, const Edge& v) {
    1244         return (v.spec!=u.spec ||
    1245                 static_cast<typename Graph::Edge>(u)!=
    1246                 static_cast<typename Graph::Edge>(v) ||
    1247                 u.n!=v.n);
    1248       }
    1249 //      template<typename G>
    1250 //      friend std::ostream&
    1251 //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
    1252       friend std::ostream& operator<< (std::ostream& os, const Edge& i);
    1253       int getSpec() const { return spec; }
    1254     };
    1255 
    1256     class OutEdgeIt {
    1257       friend class GraphWrapper<Graph>;
    1258       friend class stGraphWrapper<Graph>;
    1259       typename Graph::OutEdgeIt e;
    1260       int spec;
    1261       typename Graph::ClassNodeIt n;
    1262     public:
    1263       OutEdgeIt() { }
    1264       OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
    1265                 const typename Graph::ClassNodeIt& _n) :
    1266         e(_e), spec(_spec), n(_n) {
    1267       }
    1268       OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
    1269       OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
    1270         switch (_n.spec) {
    1271           case 0 :
    1272             if (_G.graph->inSClass(_n)) { //S, van normalis kiel
    1273               e=typename Graph::OutEdgeIt(*(_G.graph),
    1274                                           typename Graph::Node(_n));
    1275               spec=0;
    1276               n=INVALID;
    1277               if (!_G.graph->valid(e)) spec=3;
    1278             } else { //T, specko kiel van
    1279               e=INVALID;
    1280               spec=2;
    1281               n=_n;
    1282             }
    1283             break;
    1284           case 1:
    1285             e=INVALID;
    1286             spec=1;
    1287             _G.graph->first(n, S_CLASS); //s->vmi;
    1288             if (!_G.graph->valid(n)) spec=3; //Ha S ures
    1289             break;
    1290           case 2:
    1291             e=INVALID;
    1292             spec=3;
    1293             n=INVALID;
    1294             break;
    1295         }
    1296       }
    1297       operator Edge() const { return Edge(e, spec, n); }
    1298     };
    1299 
    1300     class InEdgeIt {
    1301       friend class GraphWrapper<Graph>;
    1302       friend class stGraphWrapper<Graph>;
    1303       typename Graph::InEdgeIt e;
    1304       int spec;
    1305       typename Graph::ClassNodeIt n;
    1306     public:
    1307       InEdgeIt() { }
    1308       InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
    1309                const typename Graph::ClassNodeIt& _n) :
    1310         e(_e), spec(_spec), n(_n) {
    1311       }
    1312       InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
    1313       InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
    1314         switch (_n.spec) {
    1315           case 0 :
    1316             if (_G.graph->inTClass(_n)) { //T, van normalis beel
    1317               e=typename Graph::InEdgeIt(*(_G.graph),
    1318                                          typename Graph::Node(_n));
    1319               spec=0;
    1320               n=INVALID;
    1321               if (!_G.graph->valid(e)) spec=3;
    1322             } else { //S, specko beel van
    1323               e=INVALID;
    1324               spec=1;
    1325               n=_n;
    1326             }
    1327             break;
    1328           case 1:
    1329             e=INVALID;
    1330             spec=3;
    1331             n=INVALID;
    1332             break;
    1333           case 2:
    1334             e=INVALID;
    1335             spec=2;
    1336             _G.graph->first(n, T_CLASS); //vmi->t;
    1337             if (!_G.graph->valid(n)) spec=3; //Ha T ures
    1338             break;
    1339         }
    1340       }
    1341       operator Edge() const { return Edge(e, spec, n); }
    1342     };
    1343 
    1344     class EdgeIt {
    1345       friend class GraphWrapper<Graph>;
    1346       friend class stGraphWrapper<Graph>;
    1347       typename Graph::EdgeIt e;
    1348       int spec;
    1349       typename Graph::ClassNodeIt n;
    1350     public:
    1351       EdgeIt() { }
    1352       EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
    1353              const typename Graph::ClassNodeIt& _n) :
    1354         e(_e), spec(_spec), n(_n) { }
    1355       EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
    1356       EdgeIt(const stGraphWrapper<Graph>& _G) :
    1357         e(*(_G.graph)), spec(0), n(INVALID) {
    1358         if (!_G.graph->valid(e)) {
    1359           spec=1;
    1360           _G.graph->first(n, S_CLASS);
    1361           if (!_G.graph->valid(n)) { //Ha S ures
    1362             spec=2;
    1363             _G.graph->first(n, T_CLASS);
    1364             if (!_G.graph->valid(n)) { //Ha T ures
    1365               spec=3;
    1366             }
    1367           }
    1368         }
    1369       }
    1370       operator Edge() const { return Edge(e, spec, n); }
    1371     };
    1372    
    1373     NodeIt& first(NodeIt& i) const {
    1374       i=NodeIt(*this); return i;
    1375     }
    1376     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    1377       i=OutEdgeIt(*this, p); return i;
    1378     }
    1379     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    1380       i=InEdgeIt(*this, p); return i;
    1381     }
    1382     EdgeIt& first(EdgeIt& i) const {
    1383       i=EdgeIt(*this); return i;
    1384     }
    1385 
    1386     NodeIt& next(NodeIt& i) const {
    1387       switch (i.spec) {
    1388         case 0:
    1389           this->graph->next(i.n);
    1390           if (!this->graph->valid(i.n)) {
    1391             i.spec=1;
    1392           }
    1393           break;
    1394         case 1:
    1395           i.spec=2;
    1396           break;
    1397         case 2:
    1398           i.spec=3;
    1399           break;
    1400       }
    1401       return i;
    1402     }
    1403     OutEdgeIt& next(OutEdgeIt& i) const {
    1404       typename Graph::Node v;
    1405       switch (i.spec) {
    1406         case 0: //normal edge
    1407           v=this->graph->aNode(i.e);
    1408           this->graph->next(i.e);
    1409           if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
    1410             if (this->graph->inSClass(v)) { //S, nincs kiel
    1411               i.spec=3;
    1412               i.n=INVALID;
    1413             } else { //T, van kiel
    1414               i.spec=2;
    1415               i.n=v;
    1416             }
    1417           }
    1418           break;
    1419         case 1: //s->vmi
    1420           this->graph->next(i.n);
    1421           if (!this->graph->valid(i.n)) i.spec=3;
    1422           break;
    1423         case 2: //vmi->t
    1424           i.spec=3;
    1425           i.n=INVALID;
    1426           break;
    1427       }
    1428       return i;
    1429     }
    1430     InEdgeIt& next(InEdgeIt& i) const {
    1431       typename Graph::Node v;
    1432       switch (i.spec) {
    1433         case 0: //normal edge
    1434           v=this->graph->aNode(i.e);
    1435           this->graph->next(i.e);
    1436           if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
    1437             if (this->graph->inTClass(v)) { //S, nincs beel
    1438               i.spec=3;
    1439               i.n=INVALID;
    1440             } else { //S, van beel
    1441               i.spec=1;
    1442               i.n=v;
    1443             }
    1444           }
    1445           break;
    1446         case 1: //s->vmi
    1447           i.spec=3;
    1448           i.n=INVALID;
    1449           break;
    1450         case 2: //vmi->t
    1451           this->graph->next(i.n);
    1452           if (!this->graph->valid(i.n)) i.spec=3;
    1453           break;
    1454       }
    1455       return i;
    1456     }
    1457 
    1458     EdgeIt& next(EdgeIt& i) const {
    1459       switch (i.spec) {
    1460         case 0:
    1461           this->graph->next(i.e);
    1462           if (!this->graph->valid(i.e)) {
    1463             i.spec=1;
    1464             this->graph->first(i.n, S_CLASS);
    1465             if (!this->graph->valid(i.n)) {
    1466               i.spec=2;
    1467               this->graph->first(i.n, T_CLASS);
    1468               if (!this->graph->valid(i.n)) i.spec=3;
    1469             }
    1470           }
    1471           break;
    1472         case 1:
    1473           this->graph->next(i.n);
    1474           if (!this->graph->valid(i.n)) {
    1475             i.spec=2;
    1476             this->graph->first(i.n, T_CLASS);
    1477             if (!this->graph->valid(i.n)) i.spec=3;
    1478           }
    1479           break;
    1480         case 2:
    1481           this->graph->next(i.n);
    1482           if (!this->graph->valid(i.n)) i.spec=3;
    1483           break;
    1484       }
    1485       return i;
    1486     }   
    1487 
    1488     Node tail(const Edge& e) const {
    1489       switch (e.spec) {
    1490       case 0:
    1491         return Node(this->graph->tail(e));
    1492         break;
    1493       case 1:
    1494         return S_NODE;
    1495         break;
    1496       case 2:
    1497       default:
    1498         return Node(e.n);
    1499         break;
    1500       }
    1501     }
    1502     Node head(const Edge& e) const {
    1503       switch (e.spec) {
    1504       case 0:
    1505         return Node(this->graph->head(e));
    1506         break;
    1507       case 1:
    1508         return Node(e.n);
    1509         break;
    1510       case 2:
    1511       default:
    1512         return T_NODE;
    1513         break;
    1514       }
    1515     }
    1516 
    1517     bool valid(const Node& n) const { return (n.spec<3); }
    1518     bool valid(const Edge& e) const { return (e.spec<3); }
    1519 
    1520     int nodeNum() const { return this->graph->nodeNum()+2; }
    1521     int edgeNum() const {
    1522       return this->graph->edgeNum()+this->graph->nodeNum();
    1523     }
    1524  
    1525     Node aNode(const OutEdgeIt& e) const { return tail(e); }
    1526     Node aNode(const InEdgeIt& e) const { return head(e); }
    1527     Node bNode(const OutEdgeIt& e) const { return head(e); }
    1528     Node bNode(const InEdgeIt& e) const { return tail(e); }
    1529 
    1530     void addNode() const { }
    1531     void addEdge() const { }
    1532    
    1533 //    Node addNode() const { return Node(this->graph->addNode()); }
    1534 //    Edge addEdge(const Node& tail, const Node& head) const {
    1535 //      return Edge(this->graph->addEdge(tail, head)); }
    1536 
    1537 //    void erase(const Node& i) const { this->graph->erase(i); }
    1538 //    void erase(const Edge& i) const { this->graph->erase(i); }
    1539  
    1540 //    void clear() const { this->graph->clear(); }
    1541    
    1542     template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
    1543       typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
    1544       T s_value, t_value;
    1545     public:
    1546       NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G),
    1547                                                   s_value(),
    1548                                                   t_value() { }
    1549       NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
    1550                                                       s_value(a),
    1551                                                       t_value(a) { }
    1552       T operator[](const Node& n) const {
    1553         switch (n.spec) {
    1554         case 0:
    1555           return Parent::operator[](n);
    1556           break;
    1557         case 1:
    1558           return s_value;
    1559           break;
    1560         case 2:
    1561         default:
    1562           return t_value;
    1563           break;
    1564         }
    1565       }
    1566       void set(const Node& n, T t) {
    1567         switch (n.spec) {
    1568         case 0:
    1569           GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
    1570           break;
    1571         case 1:
    1572           s_value=t;
    1573           break;
    1574         case 2:
    1575         default:
    1576           t_value=t;
    1577           break;
    1578         }
    1579       }
    1580     };
    1581 
    1582     template<typename T,
    1583              typename Parent=
    1584              typename GraphWrapper<Graph>::template EdgeMap<T> >
    1585     class EdgeMap : public Parent {
    1586       //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
    1587       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
    1588     public:
    1589       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
    1590                                                  node_value(_G) { }
    1591       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
    1592                                                       node_value(_G, a) { }
    1593       T operator[](const Edge& e) const {
    1594         switch (e.spec) {
    1595         case 0:
    1596           return Parent::operator[](e);
    1597           break;
    1598         case 1:
    1599           return node_value[e.n];
    1600           break;
    1601         case 2:
    1602         default:
    1603           return node_value[e.n];
    1604           break;
    1605         }
    1606       }
    1607       void set(const Edge& e, T t) {
    1608         switch (e.spec) {
    1609         case 0:
    1610           Parent::set(e, t);
    1611           break;
    1612         case 1:
    1613           node_value.set(e.n, t);
    1614           break;
    1615         case 2:
    1616         default:
    1617           node_value.set(e.n, t);
    1618           break;
    1619         }
    1620       }
    1621     };
    1622 
    1623 //     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
    1624 //       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
    1625 //       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
    1626 //     public:
    1627 //       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
    1628 //                                               node_value(_G) { }
    1629 //       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
    1630 //                                                    node_value(_G, a) { }
    1631 //       T operator[](const Edge& e) const {
    1632 //      switch (e.spec) {
    1633 //      case 0:
    1634 //        return Parent::operator[](e);
    1635 //        break;
    1636 //      case 1:
    1637 //        return node_value[e.n];
    1638 //        break;
    1639 //      case 2:
    1640 //      default:
    1641 //        return node_value[e.n];
    1642 //        break;
    1643 //      }
    1644 //       }
    1645 //       void set(const Edge& e, T t) {
    1646 //      switch (e.spec) {
    1647 //      case 0:
    1648 //        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
    1649 //        break;
    1650 //      case 1:
    1651 //        node_value.set(e.n, t);
    1652 //        break;
    1653 //      case 2:
    1654 //      default:
    1655 //        node_value.set(e.n, t);
    1656 //        break;
    1657 //      }
    1658 //       }
    1659 //     };
    1660 
    1661 //  template<typename G>
    1662     friend std::ostream&
    1663     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
    1664       os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
    1665       return os;
    1666     }
    1667 //  template<typename G>
    1668     friend std::ostream&
    1669     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
    1670       os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
    1671         " node: " << i.n << ")";
    1672       return os;
    1673     }
    1674 
    1675   };
    1676 
    1677936  ///@}
    1678937

  • src/work/marci/leda/bipartite_matching_leda.cc

    r482 r496  
    1818//#include <bfs_iterator.h>
    1919#include <graph_wrapper.h>
     20#include <bipartite_graph_wrapper.h>
    2021#include <maps.h>
    2122#include <max_flow.h>

  • src/work/marci/leda/bipartite_matching_leda_gen.cc

    r482 r496  
    1717#include <for_each_macros.h>
    1818#include <graph_wrapper.h>
     19#include <bipartite_graph_wrapper.h>
    1920#include <maps.h>
    2021#include <max_flow.h>
Note: See TracChangeset for help on using the changeset viewer.