COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bpugraph_adaptor.h @ 2562:27c54b7f4f1d

Last change on this file since 2562:27c54b7f4f1d was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 19.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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    void firstFromANode(UEdge& i, const Node& n) const {
91      graph->firstFromANode(i, n);
92    }
93    void firstFromBNode(UEdge& i, const Node& n) const {
94      graph->firstFromBNode(i, n);
95    }
96
97    void next(Node& i) const { graph->next(i); }
98    void nextANode(Node& i) const { graph->nextANode(i); }
99    void nextBNode(Node& i) const { graph->nextBNode(i); }
100    void next(Edge& i) const { graph->next(i); }
101    void next(UEdge& i) const { graph->next(i); }
102    void nextIn(Edge& i) const { graph->nextIn(i); }
103    void nextOut(Edge& i) const { graph->nextOut(i); }
104    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
105    void nextFromANode(UEdge& i) const { graph->nextFromANode(i); }
106    void nextFromBNode(UEdge& i) const { graph->nextFromBNode(i); }
107
108    Node source(const UEdge& e) const { return graph->source(e); }
109    Node target(const UEdge& e) const { return graph->target(e); }
110
111    Node source(const Edge& e) const { return graph->source(e); }
112    Node target(const Edge& e) const { return graph->target(e); }
113
114    Node aNode(const UEdge& e) const { return graph->aNode(e); }
115    Node bNode(const UEdge& e) const { return graph->bNode(e); }
116
117    bool aNode(const Node& n) const { return graph->aNode(n); }
118    bool bNode(const Node& n) const { return graph->bNode(n); }
119
120    typedef NodeNumTagIndicator<Graph> NodeNumTag;
121    int nodeNum() const { return graph->nodeNum(); }
122    int aNodeNum() const { return graph->aNodeNum(); }
123    int bNodeNum() const { return graph->bNodeNum(); }
124   
125    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
126    int edgeNum() const { return graph->edgeNum(); }
127    int uEdgeNum() const { return graph->uEdgeNum(); }
128
129    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
130    Edge findEdge(const Node& u, const Node& v,
131                  const Edge& prev = INVALID) {
132      return graph->findEdge(u, v, prev);
133    }
134    UEdge findUEdge(const Node& u, const Node& v,
135                    const UEdge& prev = INVALID) {
136      return graph->findUEdge(u, v, prev);
137    }
138 
139    Node addANode() const { return graph->addANode(); }
140    Node addBNode() const { return graph->addBNode(); }
141    UEdge addEdge(const Node& u, const Node& v) const {
142      return graph->addEdge(u, v);
143    }
144
145    void erase(const Node& i) const { graph->erase(i); }
146    void erase(const UEdge& i) const { graph->erase(i); }
147 
148    void clear() const { graph->clear(); }
149
150    bool direction(const Edge& e) const { return graph->direction(e); }
151    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
152   
153    int id(const Node& v) const { return graph->id(v); }
154    int id(const ANode& v) const { return graph->id(v); }
155    int id(const BNode& v) const { return graph->id(v); }
156    int id(const Edge& e) const { return graph->id(e); }
157    int id(const UEdge& e) const { return graph->id(e); }
158
159    Node fromNodeId(int ix) const { return graph->fromNodeId(ix); }
160    ANode nodeFromANodeId(int ix) const { return graph->nodeFromANodeId(ix); }
161    BNode nodeFromBNodeId(int ix) const { return graph->nodeFromBNodeId(ix); }
162    Edge fromEdgeId(int ix) const { return graph->fromEdgeId(ix); }
163    UEdge fromUEdgeId(int ix) const { return graph->fromUEdgeId(ix); }
164
165    int maxNodeId() const { return graph->maxNodeId(); }
166    int maxANodeId() const { return graph->maxANodeId(); }
167    int maxBNodeId() const { return graph->maxBNodeId(); }
168    int maxEdgeId() const { return graph->maxEdgeId(); }
169    int maxUEdgeId() const { return graph->maxEdgeId(); }
170
171    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
172    NodeNotifier& notifier(Node) const {
173      return graph->notifier(Node());
174    }
175
176    typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
177    ANodeNotifier& notifier(ANode) const {
178      return graph->notifier(ANode());
179    }
180
181    typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
182    BNodeNotifier& notifier(BNode) const {
183      return graph->notifier(BNode());
184    }
185
186    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
187    EdgeNotifier& notifier(Edge) const {
188      return graph->notifier(Edge());
189    }
190
191    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
192    UEdgeNotifier& notifier(UEdge) const {
193      return graph->notifier(UEdge());
194    }
195
196    template <typename _Value>
197    class NodeMap : public Graph::template NodeMap<_Value> {
198    public:
199      typedef typename Graph::template NodeMap<_Value> Parent;
200      explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga)
201        : Parent(*ga.graph) {}
202      NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
203        : Parent(*ga.graph, value) {}
204
205      NodeMap& operator=(const NodeMap& cmap) {
206        return operator=<NodeMap>(cmap);
207      }
208
209      template <typename CMap>
210      NodeMap& operator=(const CMap& cmap) {
211        Parent::operator=(cmap);
212        return *this;
213      }
214    };
215
216    template <typename _Value>
217    class ANodeMap : public Graph::template ANodeMap<_Value> {
218    public:
219      typedef typename Graph::template ANodeMap<_Value> Parent;
220      explicit ANodeMap(const BpUGraphAdaptorBase& ga)
221        : Parent(*ga.graph) {}
222      ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
223        : Parent(*ga.graph, value) {}
224
225      ANodeMap& operator=(const ANodeMap& cmap) {
226        return operator=<ANodeMap>(cmap);
227      }
228
229      template <typename CMap>
230      ANodeMap& operator=(const CMap& cmap) {
231        Parent::operator=(cmap);
232        return *this;
233      }
234    };
235
236    template <typename _Value>
237    class BNodeMap : public Graph::template BNodeMap<_Value> {
238    public:
239      typedef typename Graph::template BNodeMap<_Value> Parent;
240      explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga)
241        : Parent(*ga.graph) {}
242      BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
243        : Parent(*ga.graph, value) {}
244
245      BNodeMap& operator=(const BNodeMap& cmap) {
246        return operator=<BNodeMap>(cmap);
247      }
248
249      template <typename CMap>
250      BNodeMap& operator=(const CMap& cmap) {
251        Parent::operator=(cmap);
252        return *this;
253      }
254    };
255
256    template <typename _Value>
257    class EdgeMap : public Graph::template EdgeMap<_Value> {
258    public:
259      typedef typename Graph::template EdgeMap<_Value> Parent;
260      explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
261        : Parent(*ga.graph) {}
262      EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
263        : Parent(*ga.graph, value) {}
264
265      EdgeMap& operator=(const EdgeMap& cmap) {
266        return operator=<EdgeMap>(cmap);
267      }
268
269      template <typename CMap>
270      EdgeMap& operator=(const CMap& cmap) {
271        Parent::operator=(cmap);
272        return *this;
273      }
274    };
275
276    template <typename _Value>
277    class UEdgeMap : public Graph::template UEdgeMap<_Value> {
278    public:
279      typedef typename Graph::template UEdgeMap<_Value> Parent;
280      explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
281        : Parent(*ga.graph) {}
282      UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
283        : Parent(*ga.graph, value) {}
284
285      UEdgeMap& operator=(const UEdgeMap& cmap) {
286        return operator=<UEdgeMap>(cmap);
287      }
288
289      template <typename CMap>
290      UEdgeMap& operator=(const CMap& cmap) {
291        Parent::operator=(cmap);
292        return *this;
293      }
294    };
295
296  };
297
298  /// \ingroup graph_adaptors
299  ///
300  /// \brief Trivial Bipartite Undirected Graph Adaptor
301  ///
302  /// Trivial Bipartite Undirected Graph Adaptor. It does not change
303  /// the functionality of the adapted graph.
304  template <typename _BpUGraph>
305  class BpUGraphAdaptor
306    : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > {
307  public:
308    typedef _BpUGraph Graph;
309    typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
310  protected:
311    BpUGraphAdaptor() : Parent() {}
312
313  public:
314    explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
315  };
316
317  template <typename _BpUGraph>
318  class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
319  public:
320   
321    typedef _BpUGraph Graph;
322    typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
323
324  protected:
325   
326    SwapBpUGraphAdaptorBase() {}
327
328  public:
329
330    typedef typename Parent::Node Node;
331    typedef typename Parent::BNode ANode;
332    typedef typename Parent::ANode BNode;
333    typedef typename Parent::Edge Edge;
334    typedef typename Parent::UEdge UEdge;
335
336    bool direction(const Edge& e) const { return !Parent::direction(e); }
337    Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }
338
339    Node aNode(const UEdge& e) const { return Parent::bNode(e); }
340    Node bNode(const UEdge& e) const { return Parent::aNode(e); }
341
342    bool aNode(const Node& n) const { return Parent::bNode(n); }
343    bool bNode(const Node& n) const { return Parent::aNode(n); }
344
345    void firstANode(Node& i) const { Parent::firstBNode(i); }
346    void firstBNode(Node& i) const { Parent::firstANode(i); }
347
348    void nextANode(Node& i) const { Parent::nextBNode(i); }
349    void nextBNode(Node& i) const { Parent::nextANode(i); }
350
351    void firstFromANode(UEdge& i, const Node& n) const {
352      Parent::firstFromBNode(i, n);
353    }
354    void firstFromBNode(UEdge& i, const Node& n) const {
355      Parent::firstFromANode(i, n);
356    }
357
358    void nextFromANode(UEdge& i) const { Parent::nextFromBNode(i); }
359    void nextFromBNode(UEdge& i) const { Parent::nextFromANode(i); }
360
361    int id(const ANode& v) const { return Parent::id(v); }
362    int id(const BNode& v) const { return Parent::id(v); }
363
364    ANode nodeFromANodeId(int ix) const { return Parent::nodeFromBNodeId(ix); }
365    BNode nodeFromBNodeId(int ix) const { return Parent::nodeFromANodeId(ix); }
366
367    int maxANodeId() const { return Parent::maxBNodeId(); }
368    int maxBNodeId() const { return Parent::maxANodeId(); }
369
370    int aNodeNum() const { return Parent::bNodeNum(); }
371    int bNodeNum() const { return Parent::aNodeNum(); }
372
373    typedef typename Parent::BNodeNotifier ANodeNotifier;
374    ANodeNotifier& notifier(ANode) const {
375      return Parent::notifier(typename Parent::BNode());
376    }
377
378    typedef typename Parent::ANodeNotifier BNodeNotifier;
379    BNodeNotifier& notifier(BNode) const {
380      return Parent::notifier(typename Parent::ANode());
381    }
382
383    template <typename _Value>
384    class ANodeMap : public Graph::template BNodeMap<_Value> {
385    public:
386      typedef typename Graph::template BNodeMap<_Value> Parent;
387      explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga)
388        : Parent(*ga.graph) {}
389      ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
390        : Parent(*ga.graph, value) {}
391
392      ANodeMap& operator=(const ANodeMap& cmap) {
393        return operator=<ANodeMap>(cmap);
394      }
395
396      template <typename CMap>
397      ANodeMap& operator=(const CMap& cmap) {
398        Parent::operator=(cmap);
399        return *this;
400      }
401    };
402
403    template <typename _Value>
404    class BNodeMap : public Graph::template ANodeMap<_Value> {
405    public:
406      typedef typename Graph::template ANodeMap<_Value> Parent;
407      explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga)
408        : Parent(*ga.graph) {}
409      BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
410        : Parent(*ga.graph, value) {}
411
412      BNodeMap& operator=(const BNodeMap& cmap) {
413        return operator=<BNodeMap>(cmap);
414      }
415
416      template <typename CMap>
417      BNodeMap& operator=(const CMap& cmap) {
418        Parent::operator=(cmap);
419        return *this;
420      }
421    };
422   
423  };
424
425  /// \ingroup graph_adaptors
426  ///
427  /// \brief Bipartite graph adaptor which swaps the two nodeset.
428  ///
429  /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
430  /// anode-set will be the original graph's bnode-set and the adaptor's
431  /// bnode-set will be the original graph's anode-set.
432  ///
433  /// As example look at an algorithm what can be sped up with the
434  /// swap bipartite undirected graph adaptor. If we want to find the
435  /// maximum matching in the bipartite graph then it will be not changed
436  /// if we swap the two nodesets. But the algorithm use the two nodeset
437  /// different way. If we swap the nodesets it provides different
438  /// running time. We run a test on random bipartite graphs with
439  /// different rate of the anode-set size and bnode-set size.
440  /// We always made graphs with 10000 nodes and 20000 edges and we
441  /// computed the maximum cardinality matching with the Hopcroft-Karp
442  /// algorithm.
443  ///
444  /// The next diagram shows the running time of the tests. If the anode-set
445  /// is smaller than the bnode-set the running time is better than with
446  /// the swapped graph. Other conclusion is that the running time
447  /// is greater when the two nodesets size are nearly equal.
448  ///
449  /// \image html swap_test.png
450  /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
451  ///
452  /// The next part shows how can we swap the two nodeset:
453  ///
454  ///\code
455  /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
456  /// SBpUGraph sbpugraph(bpugraph);
457  /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
458  ///\endcode
459  template <typename _BpUGraph>
460  class SwapBpUGraphAdaptor
461    : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
462  public:
463
464    typedef _BpUGraph Graph;
465    typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
466    Parent;
467
468  protected:
469    SwapBpUGraphAdaptor() : Parent() {}
470
471  public:
472
473    /// \brief Construct a swapped graph.
474    ///
475    /// Construct a swapped graph.
476    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
477
478  };
479
480
481  template <typename _BpUGraph,
482            typename _ANMatchingMap, typename _BNMatchingMap>
483  class MatchingBpUGraphAdaptorBase
484    : public BpUGraphAdaptorBase<const _BpUGraph>
485  {
486  public:
487   
488    typedef _BpUGraph Graph;
489    typedef _ANMatchingMap ANodeMatchingMap;
490    typedef _BNMatchingMap BNodeMatchingMap;
491
492    typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
493
494  protected:
495   
496    MatchingBpUGraphAdaptorBase() {}
497
498    void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
499      anode_matching = &_anode_matching;
500    }
501
502    void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
503      bnode_matching = &_bnode_matching;
504    }
505
506  public:
507
508    typedef typename Parent::Node Node;
509    typedef typename Parent::Edge Edge;
510
511    void firstOut(Edge& edge, const Node& node) const {
512      if (Parent::aNode(node)) {
513        Parent::firstOut(edge, node);
514        if (edge != INVALID && (*anode_matching)[node] == edge) {
515          Parent::nextOut(edge);
516        }
517      } else {
518        edge = (*bnode_matching)[node] != INVALID ?
519          Parent::direct((*bnode_matching)[node], false) : INVALID;
520      }
521    }
522
523    void nextOut(Edge& edge) const {
524      if (Parent::aNode(Parent::source(edge))) {
525        Parent::nextOut(edge);
526        if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
527          Parent::nextOut(edge);
528        }
529      } else {
530        edge = INVALID;
531      }
532    }
533 
534    void firstIn(Edge& edge, const Node& node) const {
535      if (Parent::aNode(node)) {
536        edge = (*bnode_matching)[node] != INVALID ?
537          Parent::direct((*anode_matching)[node], false) : INVALID;
538      } else {
539        Parent::firstIn(edge, node);
540        if (edge != INVALID && (*bnode_matching)[node] == edge) {
541          Parent::nextIn(edge);
542        }
543      }
544    }
545
546    void nextIn(Edge& edge) const {
547      if (Parent::aNode(Parent::target(edge))) {
548        edge = INVALID;
549      } else {
550        Parent::nextIn(edge);
551        if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
552          Parent::nextIn(edge);
553        }
554      }
555    }
556
557  private:
558    ANodeMatchingMap* anode_matching;
559    BNodeMatchingMap* bnode_matching;
560  };
561
562
563  /// \ingroup graph_adaptors
564  ///
565  /// \brief Bipartite graph adaptor to implement matching algorithms.
566  ///
567  /// Bipartite graph adaptor to implement matchings. It implements
568  /// the residual graph of the matching.
569  template <typename _BpUGraph,
570            typename _ANMatchingMap =
571            typename _BpUGraph::template ANodeMap<typename _BpUGraph::UEdge>,
572            typename _BNMatchingMap =
573            typename _BpUGraph::template BNodeMap<typename _BpUGraph::UEdge> >
574  class MatchingBpUGraphAdaptor
575    : public BpUGraphAdaptorExtender<
576    MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> >
577  {
578  public:
579
580    typedef _BpUGraph BpUGraph;
581    typedef _BpUGraph Graph;
582    typedef _ANMatchingMap ANodeMatchingMap;
583    typedef _BNMatchingMap BNodeMatchingMap;
584    typedef BpUGraphAdaptorExtender<
585      MatchingBpUGraphAdaptorBase<BpUGraph,
586                                  ANodeMatchingMap, BNodeMatchingMap> >
587    Parent;
588
589  protected:
590    MatchingBpUGraphAdaptor() : Parent() {}
591
592  public:
593
594    MatchingBpUGraphAdaptor(const Graph& _graph,
595                            ANodeMatchingMap& _anode_matching,
596                            BNodeMatchingMap& _bnode_matching) {
597      setGraph(_graph);
598      setANodeMatchingMap(_anode_matching);
599      setBNodeMatchingMap(_bnode_matching);
600    }
601
602  };
603
604}
605
606#endif
Note: See TracBrowser for help on using the repository browser.