COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bpugraph_adaptor.h @ 2078:123f08422c14

Last change on this file since 2078:123f08422c14 was 2040:c7bd55c0d820, checked in by Balazs Dezso, 18 years ago

Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
Test for it

Some BpUgraph? improvments

File size: 17.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BPUGRAPH_ADAPTOR_H
20#define LEMON_BPUGRAPH_ADAPTOR_H
21
22#include <lemon/bits/invalid.h>
23#include <lemon/maps.h>
24
25#include <lemon/bits/graph_adaptor_extender.h>
26
27#include <lemon/bits/traits.h>
28
29#include <iostream>
30
31///\ingroup graph_adaptors
32///\file
33///\brief Several graph adaptors.
34///
35///This file contains several useful bpugraph adaptor functions.
36///
37///\author Balazs Dezso
38
39namespace lemon {
40
41  /// \ingroup graph_adaptors
42  ///
43  /// \brief Base type for the Bipartite Undirected Graph Adaptors
44  ///
45  /// This is the base type for most of LEMON bpugraph adaptors.
46  /// This class implements a trivial graph adaptor i.e. it only wraps the
47  /// functions and types of the graph. The purpose of this class is to
48  /// make easier implementing graph adaptors. E.g. if an adaptor is
49  /// considered which differs from the wrapped graph only in some of its
50  /// functions or types, then it can be derived from BpUGraphAdaptor, and
51  /// only the differences should be implemented.
52  ///
53  /// \author Balazs Dezso
54  template<typename _BpUGraph>
55  class BpUGraphAdaptorBase {
56  public:
57    typedef _BpUGraph Graph;
58    typedef Graph ParentGraph;
59
60  protected:
61    Graph* graph;
62
63    BpUGraphAdaptorBase() : graph(0) {}
64
65    void setGraph(Graph& _graph) { graph = &_graph; }
66
67    Graph& getGraph() { return *graph; }
68    const Graph& getGraph() const { return *graph; }
69
70  public:
71
72    BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
73 
74    typedef typename Graph::Node Node;
75    typedef typename Graph::ANode ANode;
76    typedef typename Graph::BNode BNode;
77    typedef typename Graph::Edge Edge;
78    typedef typename Graph::UEdge UEdge;
79   
80    void first(Node& i) const { graph->first(i); }
81    void firstANode(Node& i) const { graph->firstANode(i); }
82    void firstBNode(Node& i) const { graph->firstBNode(i); }
83    void first(Edge& i) const { graph->first(i); }
84    void first(UEdge& i) const { graph->first(i); }
85    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
86    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
87    void firstInc(UEdge &i, bool &d, const Node &n) const {
88      graph->firstInc(i, d, n);
89    }
90
91    void next(Node& i) const { graph->next(i); }
92    void nextANode(Node& i) const { graph->nextANode(i); }
93    void nextBNode(Node& i) const { graph->nextBNode(i); }
94    void next(Edge& i) const { graph->next(i); }
95    void next(UEdge& i) const { graph->next(i); }
96    void nextIn(Edge& i) const { graph->nextIn(i); }
97    void nextOut(Edge& i) const { graph->nextOut(i); }
98    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
99
100    Node source(const UEdge& e) const { return graph->source(e); }
101    Node target(const UEdge& e) const { return graph->target(e); }
102
103    Node source(const Edge& e) const { return graph->source(e); }
104    Node target(const Edge& e) const { return graph->target(e); }
105
106    Node aNode(const UEdge& e) const { return graph->aNode(e); }
107    Node bNode(const UEdge& e) const { return graph->bNode(e); }
108
109    bool aNode(const Node& n) const { return graph->aNode(n); }
110    bool bNode(const Node& n) const { return graph->bNode(n); }
111
112    typedef NodeNumTagIndicator<Graph> NodeNumTag;
113    int nodeNum() const { return graph->nodeNum(); }
114    int aNodeNum() const { return graph->aNodeNum(); }
115    int bNodeNum() const { return graph->bNodeNum(); }
116   
117    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
118    int edgeNum() const { return graph->edgeNum(); }
119    int uEdgeNum() const { return graph->uEdgeNum(); }
120
121    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
122    Edge findEdge(const Node& source, const Node& target,
123                  const Edge& prev = INVALID) {
124      return graph->findEdge(source, target, prev);
125    }
126    UEdge findUEdge(const Node& source, const Node& target,
127                    const UEdge& prev = INVALID) {
128      return graph->findUEdge(source, target, prev);
129    }
130 
131    Node addANode() const { return graph->addANode(); }
132    Node addBNode() const { return graph->addBNode(); }
133    UEdge addEdge(const Node& source, const Node& target) const {
134      return graph->addEdge(source, target);
135    }
136
137    void erase(const Node& i) const { graph->erase(i); }
138    void erase(const UEdge& i) const { graph->erase(i); }
139 
140    void clear() const { graph->clear(); }
141
142    bool direction(const Edge& e) const { return graph->direction(e); }
143    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
144   
145    int id(const Node& v) const { return graph->id(v); }
146    int id(const ANode& v) const { return graph->id(v); }
147    int id(const BNode& v) const { return graph->id(v); }
148    int id(const Edge& e) const { return graph->id(e); }
149    int id(const UEdge& e) const { return graph->id(e); }
150
151    Node fromNodeId(int id) const { return graph->fromNodeId(id); }
152    ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
153    BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
154    Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
155    UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
156
157    int maxNodeId() const { return graph->maxNodeId(); }
158    int maxANodeId() const { return graph->maxANodeId(); }
159    int maxBNodeId() const { return graph->maxBNodeId(); }
160    int maxEdgeId() const { return graph->maxEdgeId(); }
161    int maxUEdgeId() const { return graph->maxEdgeId(); }
162
163    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
164    NodeNotifier& getNotifier(Node) const {
165      return graph->getNotifier(Node());
166    }
167
168    typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
169    ANodeNotifier& getNotifier(ANode) const {
170      return graph->getNotifier(ANode());
171    }
172
173    typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
174    BNodeNotifier& getNotifier(BNode) const {
175      return graph->getNotifier(BNode());
176    }
177
178    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
179    EdgeNotifier& getNotifier(Edge) const {
180      return graph->getNotifier(Edge());
181    }
182
183    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
184    UEdgeNotifier& getNotifier(UEdge) const {
185      return graph->getNotifier(UEdge());
186    }
187
188    template <typename _Value>
189    class NodeMap : public Graph::template NodeMap<_Value> {
190    public:
191      typedef typename Graph::template NodeMap<_Value> Parent;
192      explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga)
193        : Parent(*ga.graph) {}
194      NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
195        : Parent(*ga.graph, value) {}
196
197      NodeMap& operator=(const NodeMap& cmap) {
198        return operator=<NodeMap>(cmap);
199      }
200
201      template <typename CMap>
202      NodeMap& operator=(const CMap& cmap) {
203        Parent::operator=(cmap);
204        return *this;
205      }
206    };
207
208    template <typename _Value>
209    class ANodeMap : public Graph::template ANodeMap<_Value> {
210    public:
211      typedef typename Graph::template ANodeMap<_Value> Parent;
212      explicit ANodeMap(const BpUGraphAdaptorBase& ga)
213        : Parent(*ga.graph) {}
214      ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
215        : Parent(*ga.graph, value) {}
216
217      ANodeMap& operator=(const ANodeMap& cmap) {
218        return operator=<ANodeMap>(cmap);
219      }
220
221      template <typename CMap>
222      ANodeMap& operator=(const CMap& cmap) {
223        Parent::operator=(cmap);
224        return *this;
225      }
226    };
227
228    template <typename _Value>
229    class BNodeMap : public Graph::template BNodeMap<_Value> {
230    public:
231      typedef typename Graph::template BNodeMap<_Value> Parent;
232      explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga)
233        : Parent(*ga.graph) {}
234      BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
235        : Parent(*ga.graph, value) {}
236
237      BNodeMap& operator=(const BNodeMap& cmap) {
238        return operator=<BNodeMap>(cmap);
239      }
240
241      template <typename CMap>
242      BNodeMap& operator=(const CMap& cmap) {
243        Parent::operator=(cmap);
244        return *this;
245      }
246    };
247
248    template <typename _Value>
249    class EdgeMap : public Graph::template EdgeMap<_Value> {
250    public:
251      typedef typename Graph::template EdgeMap<_Value> Parent;
252      explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
253        : Parent(*ga.graph) {}
254      EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
255        : Parent(*ga.graph, value) {}
256
257      EdgeMap& operator=(const EdgeMap& cmap) {
258        return operator=<EdgeMap>(cmap);
259      }
260
261      template <typename CMap>
262      EdgeMap& operator=(const CMap& cmap) {
263        Parent::operator=(cmap);
264        return *this;
265      }
266    };
267
268    template <typename _Value>
269    class UEdgeMap : public Graph::template UEdgeMap<_Value> {
270    public:
271      typedef typename Graph::template UEdgeMap<_Value> Parent;
272      explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
273        : Parent(*ga.graph) {}
274      UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
275        : Parent(*ga.graph, value) {}
276
277      UEdgeMap& operator=(const UEdgeMap& cmap) {
278        return operator=<UEdgeMap>(cmap);
279      }
280
281      template <typename CMap>
282      UEdgeMap& operator=(const CMap& cmap) {
283        Parent::operator=(cmap);
284        return *this;
285      }
286    };
287
288  };
289
290  /// \ingroup graph_adaptors
291  ///
292  /// \brief Trivial Bipartite Undirected Graph Adaptor
293  ///
294  /// Trivial Bipartite Undirected Graph Adaptor. It does not change
295  /// the functionality of the adapted graph.
296  template <typename _BpUGraph>
297  class BpUGraphAdaptor
298    : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > {
299  public:
300    typedef _BpUGraph Graph;
301    typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
302  protected:
303    BpUGraphAdaptor() : Parent() {}
304
305  public:
306    explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
307  };
308
309  template <typename _BpUGraph>
310  class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
311  public:
312   
313    typedef _BpUGraph Graph;
314    typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
315
316  protected:
317   
318    SwapBpUGraphAdaptorBase() {}
319
320  public:
321
322    typedef typename Parent::Node Node;
323    typedef typename Parent::BNode ANode;
324    typedef typename Parent::ANode BNode;
325    typedef typename Parent::Edge Edge;
326    typedef typename Parent::UEdge UEdge;
327
328    bool direction(const Edge& e) const { return !Parent::direction(e); }
329    Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }
330
331    Node aNode(const UEdge& e) const { return Parent::bNode(e); }
332    Node bNode(const UEdge& e) const { return Parent::aNode(e); }
333
334    bool aNode(const Node& n) const { return Parent::bNode(n); }
335    bool bNode(const Node& n) const { return Parent::aNode(n); }
336
337    void firstANode(Node& i) const { Parent::firstBNode(i); }
338    void firstBNode(Node& i) const { Parent::firstANode(i); }
339
340    void nextANode(Node& i) const { Parent::nextBNode(i); }
341    void nextBNode(Node& i) const { Parent::nextANode(i); }
342
343    int id(const ANode& v) const { return Parent::id(v); }
344    int id(const BNode& v) const { return Parent::id(v); }
345
346    ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
347    BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
348
349    int maxANodeId() const { return Parent::maxBNodeId(); }
350    int maxBNodeId() const { return Parent::maxANodeId(); }
351
352    int aNodeNum() const { return Parent::bNodeNum(); }
353    int bNodeNum() const { return Parent::aNodeNum(); }
354
355    typedef typename Parent::BNodeNotifier ANodeNotifier;
356    ANodeNotifier& getNotifier(ANode) const {
357      return Parent::getNotifier(typename Parent::BNode());
358    }
359
360    typedef typename Parent::ANodeNotifier BNodeNotifier;
361    BNodeNotifier& getNotifier(BNode) const {
362      return Parent::getNotifier(typename Parent::ANode());
363    }
364
365    template <typename _Value>
366    class ANodeMap : public Graph::template BNodeMap<_Value> {
367    public:
368      typedef typename Graph::template BNodeMap<_Value> Parent;
369      explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga)
370        : Parent(*ga.graph) {}
371      ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
372        : Parent(*ga.graph, value) {}
373
374      ANodeMap& operator=(const ANodeMap& cmap) {
375        return operator=<ANodeMap>(cmap);
376      }
377
378      template <typename CMap>
379      ANodeMap& operator=(const CMap& cmap) {
380        Parent::operator=(cmap);
381        return *this;
382      }
383    };
384
385    template <typename _Value>
386    class BNodeMap : public Graph::template ANodeMap<_Value> {
387    public:
388      typedef typename Graph::template ANodeMap<_Value> Parent;
389      explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga)
390        : Parent(*ga.graph) {}
391      BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
392        : Parent(*ga.graph, value) {}
393
394      BNodeMap& operator=(const BNodeMap& cmap) {
395        return operator=<BNodeMap>(cmap);
396      }
397
398      template <typename CMap>
399      BNodeMap& operator=(const CMap& cmap) {
400        Parent::operator=(cmap);
401        return *this;
402      }
403    };
404   
405  };
406
407  /// \ingroup graph_adaptors
408  ///
409  /// \brief Bipartite graph adaptor which swaps the two nodeset.
410  ///
411  /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
412  /// a-nodeset will be the original graph's b-nodeset and the adaptor's
413  /// b-nodeset will be the original graph's a-nodeset.
414  template <typename _BpUGraph>
415  class SwapBpUGraphAdaptor
416    : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
417  public:
418
419    typedef _BpUGraph Graph;
420    typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
421    Parent;
422
423  protected:
424    SwapBpUGraphAdaptor() : Parent() {}
425
426  public:
427
428    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
429
430  };
431
432
433  template <typename _BpUGraph,
434            typename _ANMatchingMap, typename _BNMatchingMap>
435  class MatchingBpUGraphAdaptorBase
436    : public BpUGraphAdaptorBase<const _BpUGraph>
437  {
438  public:
439   
440    typedef _BpUGraph Graph;
441    typedef _ANMatchingMap ANodeMatchingMap;
442    typedef _BNMatchingMap BNodeMatchingMap;
443
444    typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
445
446  protected:
447   
448    MatchingBpUGraphAdaptorBase() {}
449
450    void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
451      anode_matching = &_anode_matching;
452    }
453
454    void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
455      bnode_matching = &_bnode_matching;
456    }
457
458  public:
459
460    typedef typename Parent::Node Node;
461    typedef typename Parent::Edge Edge;
462
463    void firstOut(Edge& edge, const Node& node) const {
464      if (Parent::aNode(node)) {
465        Parent::firstOut(edge, node);
466        if (edge != INVALID && (*anode_matching)[node] == edge) {
467          Parent::nextOut(edge);
468        }
469      } else {
470        edge = (*bnode_matching)[node] != INVALID ?
471          Parent::direct((*bnode_matching)[node], false) : INVALID;
472      }
473    }
474
475    void nextOut(Edge& edge) const {
476      if (Parent::aNode(Parent::source(edge))) {
477        Parent::nextOut(edge);
478        if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
479          Parent::nextOut(edge);
480        }
481      } else {
482        edge = INVALID;
483      }
484    }
485 
486    void firstIn(Edge& edge, const Node& node) const {
487      if (Parent::aNode(node)) {
488        edge = (*bnode_matching)[node] != INVALID ?
489          Parent::direct((*anode_matching)[node], false) : INVALID;
490      } else {
491        Parent::firstIn(edge, node);
492        if (edge != INVALID && (*bnode_matching)[node] == edge) {
493          Parent::nextIn(edge);
494        }
495      }
496    }
497
498    void nextIn(Edge& edge) const {
499      if (Parent::aNode(Parent::target(edge))) {
500        edge = INVALID;
501      } else {
502        Parent::nextIn(edge);
503        if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
504          Parent::nextIn(edge);
505        }
506      }
507    }
508
509  private:
510    ANodeMatchingMap* anode_matching;
511    BNodeMatchingMap* bnode_matching;
512  };
513
514
515  /// \ingroup graph_adaptors
516  ///
517  /// \brief Bipartite graph adaptor to implement matching algorithms.
518  ///
519  /// Bipartite graph adaptor to implement matchings. It implements
520  /// the residual graph of the matching.
521  template <typename _BpUGraph,
522            typename _ANMatchingMap, typename _BNMatchingMap>
523  class MatchingBpUGraphAdaptor
524    : public BpUGraphAdaptorExtender<
525    MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> >
526  {
527  public:
528
529    typedef _BpUGraph BpUGraph;
530    typedef _BpUGraph Graph;
531    typedef _ANMatchingMap ANodeMatchingMap;
532    typedef _BNMatchingMap BNodeMatchingMap;
533    typedef BpUGraphAdaptorExtender<
534      MatchingBpUGraphAdaptorBase<BpUGraph,
535                                  ANodeMatchingMap, BNodeMatchingMap> >
536    Parent;
537
538  protected:
539    MatchingBpUGraphAdaptor() : Parent() {}
540
541  public:
542
543    MatchingBpUGraphAdaptor(const Graph& _graph,
544                            ANodeMatchingMap& _anode_matching,
545                            BNodeMatchingMap& _bnode_matching) {
546      setGraph(_graph);
547      setANodeMatchingMap(_anode_matching);
548      setBNodeMatchingMap(_bnode_matching);
549    }
550
551  };
552
553}
554
555#endif
Note: See TracBrowser for help on using the repository browser.