COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bpugraph_adaptor.h @ 2085:1970a93dfaa8

Last change on this file since 2085:1970a93dfaa8 was 2084:59769591eb60, checked in by Balazs Dezso, 18 years ago

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

SwapBpUGraphAdaptor

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

File size: 18.6 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  /// anode-set will be the original graph's bnode-set and the adaptor's
413  /// bnode-set will be the original graph's anode-set.
414  ///
415  /// As example look at an algorithm what can be sped up with the
416  /// swap bipartite undirected graph adaptor. If we want to find the
417  /// maximum matching in the bipartite graph then it will be not changed
418  /// if we swap the two nodesets. But the algorithm use the two nodeset
419  /// different way. If we swap the nodesets it provides different
420  /// running time. We run a test on random bipartite graphs with
421  /// different rate of the anode-set size and bnode-set size.
422  /// We always made graphs with 10000 nodes and 20000 edges and we
423  /// computed the maximum cardinality matching with the Hopcroft-Karp
424  /// algorithm.
425  ///
426  /// The next diagram shows the running time of the tests. If the anode-set
427  /// is smaller than the bnode-set the running time is better than with
428  /// the swapped graph. Other conclusion is that the running time
429  /// is greater when the two nodesets size are nearly equal.
430  ///
431  /// \image html swap_test.png
432  /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
433  ///
434  /// The next part shows how can we swap the two nodeset:
435  ///
436  ///\code
437  /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
438  /// SBpUGraph sbpugraph(bpugraph);
439  /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
440  ///\endcode
441  template <typename _BpUGraph>
442  class SwapBpUGraphAdaptor
443    : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
444  public:
445
446    typedef _BpUGraph Graph;
447    typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
448    Parent;
449
450  protected:
451    SwapBpUGraphAdaptor() : Parent() {}
452
453  public:
454
455    /// \brief Construct a swapped graph.
456    ///
457    /// Construct a swapped graph.
458    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
459
460  };
461
462
463  template <typename _BpUGraph,
464            typename _ANMatchingMap, typename _BNMatchingMap>
465  class MatchingBpUGraphAdaptorBase
466    : public BpUGraphAdaptorBase<const _BpUGraph>
467  {
468  public:
469   
470    typedef _BpUGraph Graph;
471    typedef _ANMatchingMap ANodeMatchingMap;
472    typedef _BNMatchingMap BNodeMatchingMap;
473
474    typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
475
476  protected:
477   
478    MatchingBpUGraphAdaptorBase() {}
479
480    void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
481      anode_matching = &_anode_matching;
482    }
483
484    void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
485      bnode_matching = &_bnode_matching;
486    }
487
488  public:
489
490    typedef typename Parent::Node Node;
491    typedef typename Parent::Edge Edge;
492
493    void firstOut(Edge& edge, const Node& node) const {
494      if (Parent::aNode(node)) {
495        Parent::firstOut(edge, node);
496        if (edge != INVALID && (*anode_matching)[node] == edge) {
497          Parent::nextOut(edge);
498        }
499      } else {
500        edge = (*bnode_matching)[node] != INVALID ?
501          Parent::direct((*bnode_matching)[node], false) : INVALID;
502      }
503    }
504
505    void nextOut(Edge& edge) const {
506      if (Parent::aNode(Parent::source(edge))) {
507        Parent::nextOut(edge);
508        if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
509          Parent::nextOut(edge);
510        }
511      } else {
512        edge = INVALID;
513      }
514    }
515 
516    void firstIn(Edge& edge, const Node& node) const {
517      if (Parent::aNode(node)) {
518        edge = (*bnode_matching)[node] != INVALID ?
519          Parent::direct((*anode_matching)[node], false) : INVALID;
520      } else {
521        Parent::firstIn(edge, node);
522        if (edge != INVALID && (*bnode_matching)[node] == edge) {
523          Parent::nextIn(edge);
524        }
525      }
526    }
527
528    void nextIn(Edge& edge) const {
529      if (Parent::aNode(Parent::target(edge))) {
530        edge = INVALID;
531      } else {
532        Parent::nextIn(edge);
533        if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
534          Parent::nextIn(edge);
535        }
536      }
537    }
538
539  private:
540    ANodeMatchingMap* anode_matching;
541    BNodeMatchingMap* bnode_matching;
542  };
543
544
545  /// \ingroup graph_adaptors
546  ///
547  /// \brief Bipartite graph adaptor to implement matching algorithms.
548  ///
549  /// Bipartite graph adaptor to implement matchings. It implements
550  /// the residual graph of the matching.
551  template <typename _BpUGraph,
552            typename _ANMatchingMap, typename _BNMatchingMap>
553  class MatchingBpUGraphAdaptor
554    : public BpUGraphAdaptorExtender<
555    MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> >
556  {
557  public:
558
559    typedef _BpUGraph BpUGraph;
560    typedef _BpUGraph Graph;
561    typedef _ANMatchingMap ANodeMatchingMap;
562    typedef _BNMatchingMap BNodeMatchingMap;
563    typedef BpUGraphAdaptorExtender<
564      MatchingBpUGraphAdaptorBase<BpUGraph,
565                                  ANodeMatchingMap, BNodeMatchingMap> >
566    Parent;
567
568  protected:
569    MatchingBpUGraphAdaptor() : Parent() {}
570
571  public:
572
573    MatchingBpUGraphAdaptor(const Graph& _graph,
574                            ANodeMatchingMap& _anode_matching,
575                            BNodeMatchingMap& _bnode_matching) {
576      setGraph(_graph);
577      setANodeMatchingMap(_anode_matching);
578      setBNodeMatchingMap(_bnode_matching);
579    }
580
581  };
582
583}
584
585#endif
Note: See TracBrowser for help on using the repository browser.