|
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 |
|
39 namespace 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 |