Bug fixes.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BPUGRAPH_ADAPTOR_H
20 #define LEMON_BPUGRAPH_ADAPTOR_H
22 #include <lemon/bits/invalid.h>
23 #include <lemon/maps.h>
25 #include <lemon/bits/graph_adaptor_extender.h>
27 #include <lemon/bits/traits.h>
31 ///\ingroup graph_adaptors
33 ///\brief Several graph adaptors.
35 ///This file contains several useful bpugraph adaptor functions.
37 ///\author Balazs Dezso
41 /// \ingroup graph_adaptors
43 /// \brief Base type for the Bipartite Undirected Graph Adaptors
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.
53 /// \author Balazs Dezso
54 template<typename _BpUGraph>
55 class BpUGraphAdaptorBase {
57 typedef _BpUGraph Graph;
58 typedef Graph ParentGraph;
63 BpUGraphAdaptorBase() : graph(0) {}
65 void setGraph(Graph& _graph) { graph = &_graph; }
67 Graph& getGraph() { return *graph; }
68 const Graph& getGraph() const { return *graph; }
72 BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
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;
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);
90 void firstFromANode(UEdge& i, const Node& n) const {
91 graph->firstFromANode(i, n);
93 void firstFromBNode(UEdge& i, const Node& n) const {
94 graph->firstFromBNode(i, n);
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); }
108 Node source(const UEdge& e) const { return graph->source(e); }
109 Node target(const UEdge& e) const { return graph->target(e); }
111 Node source(const Edge& e) const { return graph->source(e); }
112 Node target(const Edge& e) const { return graph->target(e); }
114 Node aNode(const UEdge& e) const { return graph->aNode(e); }
115 Node bNode(const UEdge& e) const { return graph->bNode(e); }
117 bool aNode(const Node& n) const { return graph->aNode(n); }
118 bool bNode(const Node& n) const { return graph->bNode(n); }
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(); }
125 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
126 int edgeNum() const { return graph->edgeNum(); }
127 int uEdgeNum() const { return graph->uEdgeNum(); }
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);
134 UEdge findUEdge(const Node& u, const Node& v,
135 const UEdge& prev = INVALID) {
136 return graph->findUEdge(u, v, prev);
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);
145 void erase(const Node& i) const { graph->erase(i); }
146 void erase(const UEdge& i) const { graph->erase(i); }
148 void clear() const { graph->clear(); }
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); }
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); }
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); }
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(); }
171 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
172 NodeNotifier& notifier(Node) const {
173 return graph->notifier(Node());
176 typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
177 ANodeNotifier& notifier(ANode) const {
178 return graph->notifier(ANode());
181 typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
182 BNodeNotifier& notifier(BNode) const {
183 return graph->notifier(BNode());
186 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
187 EdgeNotifier& notifier(Edge) const {
188 return graph->notifier(Edge());
191 typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
192 UEdgeNotifier& notifier(UEdge) const {
193 return graph->notifier(UEdge());
196 template <typename _Value>
197 class NodeMap : public Graph::template NodeMap<_Value> {
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) {}
205 NodeMap& operator=(const NodeMap& cmap) {
206 return operator=<NodeMap>(cmap);
209 template <typename CMap>
210 NodeMap& operator=(const CMap& cmap) {
211 Parent::operator=(cmap);
216 template <typename _Value>
217 class ANodeMap : public Graph::template ANodeMap<_Value> {
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) {}
225 ANodeMap& operator=(const ANodeMap& cmap) {
226 return operator=<ANodeMap>(cmap);
229 template <typename CMap>
230 ANodeMap& operator=(const CMap& cmap) {
231 Parent::operator=(cmap);
236 template <typename _Value>
237 class BNodeMap : public Graph::template BNodeMap<_Value> {
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) {}
245 BNodeMap& operator=(const BNodeMap& cmap) {
246 return operator=<BNodeMap>(cmap);
249 template <typename CMap>
250 BNodeMap& operator=(const CMap& cmap) {
251 Parent::operator=(cmap);
256 template <typename _Value>
257 class EdgeMap : public Graph::template EdgeMap<_Value> {
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) {}
265 EdgeMap& operator=(const EdgeMap& cmap) {
266 return operator=<EdgeMap>(cmap);
269 template <typename CMap>
270 EdgeMap& operator=(const CMap& cmap) {
271 Parent::operator=(cmap);
276 template <typename _Value>
277 class UEdgeMap : public Graph::template UEdgeMap<_Value> {
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) {}
285 UEdgeMap& operator=(const UEdgeMap& cmap) {
286 return operator=<UEdgeMap>(cmap);
289 template <typename CMap>
290 UEdgeMap& operator=(const CMap& cmap) {
291 Parent::operator=(cmap);
298 /// \ingroup graph_adaptors
300 /// \brief Trivial Bipartite Undirected Graph Adaptor
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> > {
308 typedef _BpUGraph Graph;
309 typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
311 BpUGraphAdaptor() : Parent() {}
314 explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
317 template <typename _BpUGraph>
318 class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
321 typedef _BpUGraph Graph;
322 typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
326 SwapBpUGraphAdaptorBase() {}
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;
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); }
339 Node aNode(const UEdge& e) const { return Parent::bNode(e); }
340 Node bNode(const UEdge& e) const { return Parent::aNode(e); }
342 bool aNode(const Node& n) const { return Parent::bNode(n); }
343 bool bNode(const Node& n) const { return Parent::aNode(n); }
345 void firstANode(Node& i) const { Parent::firstBNode(i); }
346 void firstBNode(Node& i) const { Parent::firstANode(i); }
348 void nextANode(Node& i) const { Parent::nextBNode(i); }
349 void nextBNode(Node& i) const { Parent::nextANode(i); }
351 void firstFromANode(UEdge& i, const Node& n) const {
352 Parent::firstFromBNode(i, n);
354 void firstFromBNode(UEdge& i, const Node& n) const {
355 Parent::firstFromANode(i, n);
358 void nextFromANode(UEdge& i) const { Parent::nextFromBNode(i); }
359 void nextFromBNode(UEdge& i) const { Parent::nextFromANode(i); }
361 int id(const ANode& v) const { return Parent::id(v); }
362 int id(const BNode& v) const { return Parent::id(v); }
364 ANode nodeFromANodeId(int ix) const { return Parent::nodeFromBNodeId(ix); }
365 BNode nodeFromBNodeId(int ix) const { return Parent::nodeFromANodeId(ix); }
367 int maxANodeId() const { return Parent::maxBNodeId(); }
368 int maxBNodeId() const { return Parent::maxANodeId(); }
370 int aNodeNum() const { return Parent::bNodeNum(); }
371 int bNodeNum() const { return Parent::aNodeNum(); }
373 typedef typename Parent::BNodeNotifier ANodeNotifier;
374 ANodeNotifier& notifier(ANode) const {
375 return Parent::notifier(typename Parent::BNode());
378 typedef typename Parent::ANodeNotifier BNodeNotifier;
379 BNodeNotifier& notifier(BNode) const {
380 return Parent::notifier(typename Parent::ANode());
383 template <typename _Value>
384 class ANodeMap : public Graph::template BNodeMap<_Value> {
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) {}
392 ANodeMap& operator=(const ANodeMap& cmap) {
393 return operator=<ANodeMap>(cmap);
396 template <typename CMap>
397 ANodeMap& operator=(const CMap& cmap) {
398 Parent::operator=(cmap);
403 template <typename _Value>
404 class BNodeMap : public Graph::template ANodeMap<_Value> {
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) {}
412 BNodeMap& operator=(const BNodeMap& cmap) {
413 return operator=<BNodeMap>(cmap);
416 template <typename CMap>
417 BNodeMap& operator=(const CMap& cmap) {
418 Parent::operator=(cmap);
425 /// \ingroup graph_adaptors
427 /// \brief Bipartite graph adaptor which swaps the two nodeset.
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.
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
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.
449 /// \image html swap_test.png
450 /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
452 /// The next part shows how can we swap the two nodeset:
455 /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
456 /// SBpUGraph sbpugraph(bpugraph);
457 /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
459 template <typename _BpUGraph>
460 class SwapBpUGraphAdaptor
461 : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
464 typedef _BpUGraph Graph;
465 typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
469 SwapBpUGraphAdaptor() : Parent() {}
473 /// \brief Construct a swapped graph.
475 /// Construct a swapped graph.
476 explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
481 template <typename _BpUGraph,
482 typename _ANMatchingMap, typename _BNMatchingMap>
483 class MatchingBpUGraphAdaptorBase
484 : public BpUGraphAdaptorBase<const _BpUGraph>
488 typedef _BpUGraph Graph;
489 typedef _ANMatchingMap ANodeMatchingMap;
490 typedef _BNMatchingMap BNodeMatchingMap;
492 typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
496 MatchingBpUGraphAdaptorBase() {}
498 void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
499 anode_matching = &_anode_matching;
502 void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
503 bnode_matching = &_bnode_matching;
508 typedef typename Parent::Node Node;
509 typedef typename Parent::Edge Edge;
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);
518 edge = (*bnode_matching)[node] != INVALID ?
519 Parent::direct((*bnode_matching)[node], false) : INVALID;
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);
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;
539 Parent::firstIn(edge, node);
540 if (edge != INVALID && (*bnode_matching)[node] == edge) {
541 Parent::nextIn(edge);
546 void nextIn(Edge& edge) const {
547 if (Parent::aNode(Parent::target(edge))) {
550 Parent::nextIn(edge);
551 if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
552 Parent::nextIn(edge);
558 ANodeMatchingMap* anode_matching;
559 BNodeMatchingMap* bnode_matching;
563 /// \ingroup graph_adaptors
565 /// \brief Bipartite graph adaptor to implement matching algorithms.
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> >
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> >
590 MatchingBpUGraphAdaptor() : Parent() {}
594 MatchingBpUGraphAdaptor(const Graph& _graph,
595 ANodeMatchingMap& _anode_matching,
596 BNodeMatchingMap& _bnode_matching) {
598 setANodeMatchingMap(_anode_matching);
599 setBNodeMatchingMap(_bnode_matching);