COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bpugraph_adaptor.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 13.0 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    typedef NodeNumTagIndicator<Graph> NodeNumTag;
107    int nodeNum() const { return graph->nodeNum(); }
108    int aNodeNum() const { return graph->aNodeNum(); }
109    int bNodeNum() const { return graph->bNodeNum(); }
110   
111    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
112    int edgeNum() const { return graph->edgeNum(); }
113    int uEdgeNum() const { return graph->uEdgeNum(); }
114
115    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
116    Edge findEdge(const Node& source, const Node& target,
117                  const Edge& prev = INVALID) {
118      return graph->findEdge(source, target, prev);
119    }
120    UEdge findUEdge(const Node& source, const Node& target,
121                    const UEdge& prev = INVALID) {
122      return graph->findUEdge(source, target, prev);
123    }
124 
125    Node addNode() const { return graph->addNode(); }
126    UEdge addEdge(const Node& source, const Node& target) const {
127      return graph->addEdge(source, target);
128    }
129
130    void erase(const Node& i) const { graph->erase(i); }
131    void erase(const UEdge& i) const { graph->erase(i); }
132 
133    void clear() const { graph->clear(); }
134
135    bool direction(const Edge& e) const { return graph->direction(e); }
136    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
137   
138    int id(const Node& v) const { return graph->id(v); }
139    int id(const ANode& v) const { return graph->id(v); }
140    int id(const BNode& v) const { return graph->id(v); }
141    int id(const Edge& e) const { return graph->id(e); }
142    int id(const UEdge& e) const { return graph->id(e); }
143
144    Node fromNodeId(int id) const { return graph->fromNodeId(id); }
145    ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
146    BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
147    Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
148    UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
149
150    int maxNodeId() const { return graph->maxNodeId(); }
151    int maxANodeId() const { return graph->maxANodeId(); }
152    int maxBNodeId() const { return graph->maxBNodeId(); }
153    int maxEdgeId() const { return graph->maxEdgeId(); }
154    int maxUEdgeId() const { return graph->maxEdgeId(); }
155
156    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
157    NodeNotifier& getNotifier(Node) const {
158      return graph->getNotifier(Node());
159    }
160
161    typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
162    ANodeNotifier& getNotifier(ANode) const {
163      return graph->getNotifier(ANode());
164    }
165
166    typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
167    BNodeNotifier& getNotifier(BNode) const {
168      return graph->getNotifier(BNode());
169    }
170
171    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
172    EdgeNotifier& getNotifier(Edge) const {
173      return graph->getNotifier(Edge());
174    }
175
176    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
177    UEdgeNotifier& getNotifier(UEdge) const {
178      return graph->getNotifier(UEdge());
179    }
180
181    template <typename _Value>
182    class NodeMap : public Graph::template NodeMap<_Value> {
183    public:
184      typedef typename Graph::template NodeMap<_Value> Parent;
185      explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga)
186        : Parent(*ga.graph) {}
187      NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
188        : Parent(*ga.graph, value) {}
189
190      NodeMap& operator=(const NodeMap& cmap) {
191        return operator=<NodeMap>(cmap);
192      }
193
194      template <typename CMap>
195      NodeMap& operator=(const CMap& cmap) {
196        Parent::operator=(cmap);
197        return *this;
198      }
199    };
200
201    template <typename _Value>
202    class ANodeMap : public Graph::template ANodeMap<_Value> {
203    public:
204      typedef typename Graph::template ANodeMap<_Value> Parent;
205      explicit ANodeMap(const BpUGraphAdaptorBase& ga)
206        : Parent(*ga.graph) {}
207      ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
208        : Parent(*ga.graph, value) {}
209
210      ANodeMap& operator=(const ANodeMap& cmap) {
211        return operator=<ANodeMap>(cmap);
212      }
213
214      template <typename CMap>
215      ANodeMap& operator=(const CMap& cmap) {
216        Parent::operator=(cmap);
217        return *this;
218      }
219    };
220
221    template <typename _Value>
222    class BNodeMap : public Graph::template BNodeMap<_Value> {
223    public:
224      typedef typename Graph::template BNodeMap<_Value> Parent;
225      explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga)
226        : Parent(*ga.graph) {}
227      BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
228        : Parent(*ga.graph, value) {}
229
230      BNodeMap& operator=(const BNodeMap& cmap) {
231        return operator=<BNodeMap>(cmap);
232      }
233
234      template <typename CMap>
235      BNodeMap& operator=(const CMap& cmap) {
236        Parent::operator=(cmap);
237        return *this;
238      }
239    };
240
241    template <typename _Value>
242    class EdgeMap : public Graph::template EdgeMap<_Value> {
243    public:
244      typedef typename Graph::template EdgeMap<_Value> Parent;
245      explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
246        : Parent(*ga.graph) {}
247      EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
248        : Parent(*ga.graph, value) {}
249
250      EdgeMap& operator=(const EdgeMap& cmap) {
251        return operator=<EdgeMap>(cmap);
252      }
253
254      template <typename CMap>
255      EdgeMap& operator=(const CMap& cmap) {
256        Parent::operator=(cmap);
257        return *this;
258      }
259    };
260
261    template <typename _Value>
262    class UEdgeMap : public Graph::template UEdgeMap<_Value> {
263    public:
264      typedef typename Graph::template UEdgeMap<_Value> Parent;
265      explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
266        : Parent(*ga.graph) {}
267      UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
268        : Parent(*ga.graph, value) {}
269
270      UEdgeMap& operator=(const UEdgeMap& cmap) {
271        return operator=<UEdgeMap>(cmap);
272      }
273
274      template <typename CMap>
275      UEdgeMap& operator=(const CMap& cmap) {
276        Parent::operator=(cmap);
277        return *this;
278      }
279    };
280
281  };
282
283  /// \ingroup graph_adaptors
284  template <typename _BpUGraph>
285  class BpUGraphAdaptor
286    : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > {
287  public:
288    typedef _BpUGraph Graph;
289    typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
290  protected:
291    BpUGraphAdaptor() : Parent() {}
292
293  public:
294    explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
295  };
296
297  template <typename _BpUGraph>
298  class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
299  public:
300   
301    typedef _BpUGraph Graph;
302    typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
303
304  protected:
305   
306    SwapBpUGraphAdaptorBase() {}
307
308  public:
309
310    typedef typename Parent::Node Node;
311    typedef typename Parent::BNode ANode;
312    typedef typename Parent::ANode BNode;
313
314    void firstANode(Node& i) const { Parent::firstBNode(i); }
315    void firstBNode(Node& i) const { Parent::firstANode(i); }
316
317    void nextANode(Node& i) const { Parent::nextBNode(i); }
318    void nextBNode(Node& i) const { Parent::nextANode(i); }
319
320    int id(const ANode& v) const { return Parent::id(v); }
321    int id(const BNode& v) const { return Parent::id(v); }
322
323    ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
324    BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
325
326    int maxANodeId() const { return Parent::maxBNodeId(); }
327    int maxBNodeId() const { return Parent::maxANodeId(); }
328
329    int aNodeNum() const { return Parent::bNodeNum(); }
330    int bNodeNum() const { return Parent::aNodeNum(); }
331
332    typedef typename Parent::BNodeNotifier ANodeNotifier;
333    ANodeNotifier& getNotifier(ANode) const {
334      return Parent::getNotifier(typename Parent::BNode());
335    }
336
337    typedef typename Parent::ANodeNotifier BNodeNotifier;
338    BNodeNotifier& getNotifier(BNode) const {
339      return Parent::getNotifier(typename Parent::ANode());
340    }
341
342    template <typename _Value>
343    class ANodeMap : public Graph::template BNodeMap<_Value> {
344    public:
345      typedef typename Graph::template BNodeMap<_Value> Parent;
346      explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga)
347        : Parent(*ga.graph) {}
348      ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
349        : Parent(*ga.graph, value) {}
350
351      ANodeMap& operator=(const ANodeMap& cmap) {
352        return operator=<ANodeMap>(cmap);
353      }
354
355      template <typename CMap>
356      ANodeMap& operator=(const CMap& cmap) {
357        Parent::operator=(cmap);
358        return *this;
359      }
360    };
361
362    template <typename _Value>
363    class BNodeMap : public Graph::template ANodeMap<_Value> {
364    public:
365      typedef typename Graph::template ANodeMap<_Value> Parent;
366      explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga)
367        : Parent(*ga.graph) {}
368      BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
369        : Parent(*ga.graph, value) {}
370
371      BNodeMap& operator=(const BNodeMap& cmap) {
372        return operator=<BNodeMap>(cmap);
373      }
374
375      template <typename CMap>
376      BNodeMap& operator=(const CMap& cmap) {
377        Parent::operator=(cmap);
378        return *this;
379      }
380    };
381   
382  };
383
384  /// \ingroup graph_adaptors
385  ///
386  /// \brief Bipartite graph adaptor which swaps the two nodeset.
387  ///
388  /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
389  /// a-nodeset will be the original graph's b-nodeset and the adaptor's
390  /// b-nodeset will be the original graph's a-nodeset.
391  template <typename _BpUGraph>
392  class SwapBpUGraphAdaptor
393    : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
394  public:
395
396    typedef _BpUGraph Graph;
397    typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
398    Parent;
399
400  protected:
401    SwapBpUGraphAdaptor() : Parent() {}
402
403  public:
404
405    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
406
407  };
408
409
410}
411
412#endif
Note: See TracBrowser for help on using the repository browser.