deba@2031: /* -*- C++ -*-
deba@2031:  *
deba@2031:  * This file is a part of LEMON, a generic C++ optimization library
deba@2031:  *
alpar@2553:  * Copyright (C) 2003-2008
deba@2031:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2031:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2031:  *
deba@2031:  * Permission to use, modify and distribute this software is granted
deba@2031:  * provided that this copyright notice appears in all copies. For
deba@2031:  * precise terms see the accompanying LICENSE file.
deba@2031:  *
deba@2031:  * This software is provided "AS IS" with no warranty of any kind,
deba@2031:  * express or implied, and with no claim as to its suitability for any
deba@2031:  * purpose.
deba@2031:  *
deba@2031:  */
deba@2031: 
deba@2031: #ifndef LEMON_BPUGRAPH_ADAPTOR_H
deba@2031: #define LEMON_BPUGRAPH_ADAPTOR_H
deba@2031: 
deba@2031: #include <lemon/bits/invalid.h>
deba@2031: #include <lemon/maps.h>
deba@2031: 
deba@2031: #include <lemon/bits/graph_adaptor_extender.h>
deba@2031: 
deba@2031: #include <lemon/bits/traits.h>
deba@2031: 
deba@2031: #include <iostream>
deba@2031: 
deba@2031: ///\ingroup graph_adaptors
deba@2031: ///\file
deba@2031: ///\brief Several graph adaptors.
deba@2031: ///
deba@2031: ///This file contains several useful bpugraph adaptor functions.
deba@2031: ///
deba@2031: ///\author Balazs Dezso
deba@2031: 
deba@2031: namespace lemon {
deba@2031: 
deba@2031:   /// \ingroup graph_adaptors
deba@2031:   ///
deba@2031:   /// \brief Base type for the Bipartite Undirected Graph Adaptors
deba@2031:   ///
deba@2031:   /// This is the base type for most of LEMON bpugraph adaptors. 
deba@2031:   /// This class implements a trivial graph adaptor i.e. it only wraps the 
deba@2031:   /// functions and types of the graph. The purpose of this class is to 
deba@2031:   /// make easier implementing graph adaptors. E.g. if an adaptor is 
deba@2031:   /// considered which differs from the wrapped graph only in some of its 
deba@2031:   /// functions or types, then it can be derived from BpUGraphAdaptor, and 
deba@2031:   /// only the differences should be implemented.
deba@2031:   ///
deba@2031:   /// \author Balazs Dezso 
deba@2031:   template<typename _BpUGraph>
deba@2031:   class BpUGraphAdaptorBase {
deba@2031:   public:
deba@2031:     typedef _BpUGraph Graph;
deba@2031:     typedef Graph ParentGraph;
deba@2031: 
deba@2031:   protected:
deba@2031:     Graph* graph;
deba@2031: 
deba@2031:     BpUGraphAdaptorBase() : graph(0) {}
deba@2031: 
deba@2031:     void setGraph(Graph& _graph) { graph = &_graph; }
deba@2031: 
deba@2031:     Graph& getGraph() { return *graph; }
deba@2031:     const Graph& getGraph() const { return *graph; }
deba@2031: 
deba@2031:   public:
deba@2031: 
deba@2031:     BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
deba@2031:  
deba@2031:     typedef typename Graph::Node Node;
deba@2031:     typedef typename Graph::ANode ANode;
deba@2031:     typedef typename Graph::BNode BNode;
deba@2031:     typedef typename Graph::Edge Edge;
deba@2031:     typedef typename Graph::UEdge UEdge;
deba@2031:    
deba@2031:     void first(Node& i) const { graph->first(i); }
deba@2031:     void firstANode(Node& i) const { graph->firstANode(i); }
deba@2031:     void firstBNode(Node& i) const { graph->firstBNode(i); }
deba@2031:     void first(Edge& i) const { graph->first(i); }
deba@2031:     void first(UEdge& i) const { graph->first(i); }
deba@2031:     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
deba@2031:     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
deba@2031:     void firstInc(UEdge &i, bool &d, const Node &n) const {
deba@2031:       graph->firstInc(i, d, n);
deba@2031:     }
deba@2231:     void firstFromANode(UEdge& i, const Node& n) const {
deba@2231:       graph->firstFromANode(i, n);
deba@2231:     }
deba@2231:     void firstFromBNode(UEdge& i, const Node& n) const {
deba@2231:       graph->firstFromBNode(i, n);
deba@2231:     }
deba@2031: 
deba@2031:     void next(Node& i) const { graph->next(i); }
deba@2031:     void nextANode(Node& i) const { graph->nextANode(i); }
deba@2031:     void nextBNode(Node& i) const { graph->nextBNode(i); }
deba@2031:     void next(Edge& i) const { graph->next(i); }
deba@2031:     void next(UEdge& i) const { graph->next(i); }
deba@2031:     void nextIn(Edge& i) const { graph->nextIn(i); }
deba@2031:     void nextOut(Edge& i) const { graph->nextOut(i); }
deba@2031:     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
deba@2231:     void nextFromANode(UEdge& i) const { graph->nextFromANode(i); }
deba@2231:     void nextFromBNode(UEdge& i) const { graph->nextFromBNode(i); }
deba@2031: 
deba@2031:     Node source(const UEdge& e) const { return graph->source(e); }
deba@2031:     Node target(const UEdge& e) const { return graph->target(e); }
deba@2031: 
deba@2031:     Node source(const Edge& e) const { return graph->source(e); }
deba@2031:     Node target(const Edge& e) const { return graph->target(e); }
deba@2031: 
deba@2040:     Node aNode(const UEdge& e) const { return graph->aNode(e); }
deba@2040:     Node bNode(const UEdge& e) const { return graph->bNode(e); }
deba@2040: 
deba@2040:     bool aNode(const Node& n) const { return graph->aNode(n); }
deba@2040:     bool bNode(const Node& n) const { return graph->bNode(n); }
deba@2040: 
deba@2031:     typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@2031:     int nodeNum() const { return graph->nodeNum(); }
deba@2031:     int aNodeNum() const { return graph->aNodeNum(); }
deba@2031:     int bNodeNum() const { return graph->bNodeNum(); }
deba@2031:     
deba@2031:     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@2031:     int edgeNum() const { return graph->edgeNum(); }
deba@2031:     int uEdgeNum() const { return graph->uEdgeNum(); }
deba@2031: 
deba@2031:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@2386:     Edge findEdge(const Node& u, const Node& v, 
deba@2031: 		  const Edge& prev = INVALID) {
deba@2386:       return graph->findEdge(u, v, prev);
deba@2031:     }
deba@2386:     UEdge findUEdge(const Node& u, const Node& v, 
deba@2031:                     const UEdge& prev = INVALID) {
deba@2386:       return graph->findUEdge(u, v, prev);
deba@2031:     }
deba@2031:   
deba@2040:     Node addANode() const { return graph->addANode(); }
deba@2040:     Node addBNode() const { return graph->addBNode(); }
deba@2386:     UEdge addEdge(const Node& u, const Node& v) const { 
deba@2386:       return graph->addEdge(u, v); 
deba@2031:     }
deba@2031: 
deba@2031:     void erase(const Node& i) const { graph->erase(i); }
deba@2031:     void erase(const UEdge& i) const { graph->erase(i); }
deba@2031:   
deba@2031:     void clear() const { graph->clear(); }
deba@2031: 
deba@2031:     bool direction(const Edge& e) const { return graph->direction(e); }
deba@2031:     Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
deba@2031:     
deba@2031:     int id(const Node& v) const { return graph->id(v); }
deba@2031:     int id(const ANode& v) const { return graph->id(v); }
deba@2031:     int id(const BNode& v) const { return graph->id(v); }
deba@2031:     int id(const Edge& e) const { return graph->id(e); }
deba@2031:     int id(const UEdge& e) const { return graph->id(e); }
deba@2031: 
deba@2386:     Node fromNodeId(int ix) const { return graph->fromNodeId(ix); }
deba@2386:     ANode nodeFromANodeId(int ix) const { return graph->nodeFromANodeId(ix); }
deba@2386:     BNode nodeFromBNodeId(int ix) const { return graph->nodeFromBNodeId(ix); }
deba@2386:     Edge fromEdgeId(int ix) const { return graph->fromEdgeId(ix); }
deba@2386:     UEdge fromUEdgeId(int ix) const { return graph->fromUEdgeId(ix); }
deba@2031: 
deba@2031:     int maxNodeId() const { return graph->maxNodeId(); }
deba@2031:     int maxANodeId() const { return graph->maxANodeId(); }
deba@2031:     int maxBNodeId() const { return graph->maxBNodeId(); }
deba@2031:     int maxEdgeId() const { return graph->maxEdgeId(); }
deba@2031:     int maxUEdgeId() const { return graph->maxEdgeId(); }
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@2384:     NodeNotifier& notifier(Node) const {
deba@2384:       return graph->notifier(Node()); 
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
deba@2384:     ANodeNotifier& notifier(ANode) const {
deba@2384:       return graph->notifier(ANode());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
deba@2384:     BNodeNotifier& notifier(BNode) const {
deba@2384:       return graph->notifier(BNode());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@2384:     EdgeNotifier& notifier(Edge) const {
deba@2384:       return graph->notifier(Edge());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
deba@2384:     UEdgeNotifier& notifier(UEdge) const {
deba@2384:       return graph->notifier(UEdge());
deba@2031:     } 
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template NodeMap<_Value> Parent;
deba@2031:       explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031: 	return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class ANodeMap : public Graph::template ANodeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template ANodeMap<_Value> Parent;
deba@2031:       explicit ANodeMap(const BpUGraphAdaptorBase& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       ANodeMap& operator=(const ANodeMap& cmap) {
deba@2031: 	return operator=<ANodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       ANodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class BNodeMap : public Graph::template BNodeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template BNodeMap<_Value> Parent;
deba@2031:       explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       BNodeMap& operator=(const BNodeMap& cmap) {
deba@2031: 	return operator=<BNodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       BNodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class EdgeMap : public Graph::template EdgeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031:       explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031: 	return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class UEdgeMap : public Graph::template UEdgeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template UEdgeMap<_Value> Parent;
deba@2031:       explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031: 	return operator=<UEdgeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       UEdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:   };
deba@2031: 
deba@2031:   /// \ingroup graph_adaptors
deba@2040:   ///
deba@2040:   /// \brief Trivial Bipartite Undirected Graph Adaptor
deba@2040:   ///
deba@2040:   /// Trivial Bipartite Undirected Graph Adaptor. It does not change
deba@2040:   /// the functionality of the adapted graph.
deba@2031:   template <typename _BpUGraph>
deba@2031:   class BpUGraphAdaptor 
deba@2031:     : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > { 
deba@2031:   public:
deba@2031:     typedef _BpUGraph Graph;
deba@2031:     typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
deba@2031:   protected:
deba@2031:     BpUGraphAdaptor() : Parent() {}
deba@2031: 
deba@2031:   public:
deba@2031:     explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
deba@2031:   };
deba@2031: 
deba@2031:   template <typename _BpUGraph>
deba@2031:   class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
deba@2031:   public:
deba@2031:     
deba@2031:     typedef _BpUGraph Graph;
deba@2031:     typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
deba@2031: 
deba@2031:   protected:
deba@2031:     
deba@2031:     SwapBpUGraphAdaptorBase() {}
deba@2031: 
deba@2031:   public:
deba@2031: 
deba@2031:     typedef typename Parent::Node Node;
deba@2031:     typedef typename Parent::BNode ANode;
deba@2031:     typedef typename Parent::ANode BNode;
deba@2040:     typedef typename Parent::Edge Edge;
deba@2040:     typedef typename Parent::UEdge UEdge;
deba@2040: 
deba@2040:     bool direction(const Edge& e) const { return !Parent::direction(e); }
deba@2040:     Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }
deba@2040: 
deba@2040:     Node aNode(const UEdge& e) const { return Parent::bNode(e); }
deba@2040:     Node bNode(const UEdge& e) const { return Parent::aNode(e); }
deba@2040: 
deba@2040:     bool aNode(const Node& n) const { return Parent::bNode(n); }
deba@2040:     bool bNode(const Node& n) const { return Parent::aNode(n); }
deba@2031: 
deba@2031:     void firstANode(Node& i) const { Parent::firstBNode(i); }
deba@2031:     void firstBNode(Node& i) const { Parent::firstANode(i); }
deba@2031: 
deba@2031:     void nextANode(Node& i) const { Parent::nextBNode(i); }
deba@2031:     void nextBNode(Node& i) const { Parent::nextANode(i); }
deba@2031: 
deba@2231:     void firstFromANode(UEdge& i, const Node& n) const {
deba@2231:       Parent::firstFromBNode(i, n);
deba@2231:     }
deba@2231:     void firstFromBNode(UEdge& i, const Node& n) const {
deba@2231:       Parent::firstFromANode(i, n);
deba@2231:     }
deba@2231: 
deba@2231:     void nextFromANode(UEdge& i) const { Parent::nextFromBNode(i); }
deba@2231:     void nextFromBNode(UEdge& i) const { Parent::nextFromANode(i); }
deba@2231: 
deba@2031:     int id(const ANode& v) const { return Parent::id(v); }
deba@2031:     int id(const BNode& v) const { return Parent::id(v); }
deba@2031: 
deba@2386:     ANode nodeFromANodeId(int ix) const { return Parent::nodeFromBNodeId(ix); }
deba@2386:     BNode nodeFromBNodeId(int ix) const { return Parent::nodeFromANodeId(ix); }
deba@2031: 
deba@2031:     int maxANodeId() const { return Parent::maxBNodeId(); }
deba@2031:     int maxBNodeId() const { return Parent::maxANodeId(); }
deba@2031: 
deba@2031:     int aNodeNum() const { return Parent::bNodeNum(); }
deba@2031:     int bNodeNum() const { return Parent::aNodeNum(); }
deba@2031: 
deba@2031:     typedef typename Parent::BNodeNotifier ANodeNotifier;
deba@2384:     ANodeNotifier& notifier(ANode) const {
deba@2384:       return Parent::notifier(typename Parent::BNode());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename Parent::ANodeNotifier BNodeNotifier;
deba@2384:     BNodeNotifier& notifier(BNode) const {
deba@2384:       return Parent::notifier(typename Parent::ANode());
deba@2031:     } 
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class ANodeMap : public Graph::template BNodeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template BNodeMap<_Value> Parent;
deba@2031:       explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       ANodeMap& operator=(const ANodeMap& cmap) {
deba@2031: 	return operator=<ANodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       ANodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class BNodeMap : public Graph::template ANodeMap<_Value> {
deba@2031:     public:
deba@2031:       typedef typename Graph::template ANodeMap<_Value> Parent;
deba@2031:       explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031:       BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       BNodeMap& operator=(const BNodeMap& cmap) {
deba@2031: 	return operator=<BNodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       BNodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031:     
deba@2031:   };
deba@2031: 
deba@2031:   /// \ingroup graph_adaptors
deba@2031:   ///
deba@2031:   /// \brief Bipartite graph adaptor which swaps the two nodeset.
deba@2031:   ///
deba@2031:   /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
deba@2084:   /// anode-set will be the original graph's bnode-set and the adaptor's
deba@2084:   /// bnode-set will be the original graph's anode-set.
deba@2084:   ///
deba@2084:   /// As example look at an algorithm what can be sped up with the
deba@2084:   /// swap bipartite undirected graph adaptor. If we want to find the
deba@2084:   /// maximum matching in the bipartite graph then it will be not changed
deba@2084:   /// if we swap the two nodesets. But the algorithm use the two nodeset
deba@2084:   /// different way. If we swap the nodesets it provides different
deba@2084:   /// running time. We run a test on random bipartite graphs with
deba@2084:   /// different rate of the anode-set size and bnode-set size.
deba@2084:   /// We always made graphs with 10000 nodes and 20000 edges and we
deba@2084:   /// computed the maximum cardinality matching with the Hopcroft-Karp 
deba@2084:   /// algorithm.
deba@2084:   ///
deba@2084:   /// The next diagram shows the running time of the tests. If the anode-set
deba@2084:   /// is smaller than the bnode-set the running time is better than with 
deba@2084:   /// the swapped graph. Other conclusion is that the running time
deba@2084:   /// is greater when the two nodesets size are nearly equal. 
deba@2084:   ///
deba@2084:   /// \image html swap_test.png
deba@2084:   /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
deba@2084:   /// 
deba@2084:   /// The next part shows how can we swap the two nodeset:
deba@2084:   ///
deba@2084:   ///\code
deba@2084:   /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
deba@2084:   /// SBpUGraph sbpugraph(bpugraph);
deba@2084:   /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
deba@2084:   ///\endcode
deba@2031:   template <typename _BpUGraph>
deba@2031:   class SwapBpUGraphAdaptor 
deba@2031:     : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > { 
deba@2031:   public:
deba@2031: 
deba@2031:     typedef _BpUGraph Graph;
deba@2031:     typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > 
deba@2031:     Parent;
deba@2031: 
deba@2031:   protected:
deba@2031:     SwapBpUGraphAdaptor() : Parent() {}
deba@2031: 
deba@2031:   public:
deba@2031: 
deba@2084:     /// \brief Construct a swapped graph.
deba@2084:     ///
deba@2084:     /// Construct a swapped graph.
deba@2031:     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
deba@2031: 
deba@2031:   };
deba@2031: 
deba@2031: 
deba@2040:   template <typename _BpUGraph, 
deba@2040:             typename _ANMatchingMap, typename _BNMatchingMap>
deba@2040:   class MatchingBpUGraphAdaptorBase 
deba@2040:     : public BpUGraphAdaptorBase<const _BpUGraph>
deba@2040:   {
deba@2040:   public:
deba@2040:     
deba@2040:     typedef _BpUGraph Graph;
deba@2040:     typedef _ANMatchingMap ANodeMatchingMap;
deba@2040:     typedef _BNMatchingMap BNodeMatchingMap;
deba@2040: 
deba@2040:     typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
deba@2040: 
deba@2040:   protected:
deba@2040:     
deba@2040:     MatchingBpUGraphAdaptorBase() {}
deba@2040: 
deba@2040:     void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
deba@2040:       anode_matching = &_anode_matching;
deba@2040:     }
deba@2040: 
deba@2040:     void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
deba@2040:       bnode_matching = &_bnode_matching;
deba@2040:     }
deba@2040: 
deba@2040:   public:
deba@2040: 
deba@2040:     typedef typename Parent::Node Node;
deba@2040:     typedef typename Parent::Edge Edge;
deba@2040: 
deba@2040:     void firstOut(Edge& edge, const Node& node) const {
deba@2040:       if (Parent::aNode(node)) {
deba@2040:         Parent::firstOut(edge, node);
deba@2040:         if (edge != INVALID && (*anode_matching)[node] == edge) {
deba@2040:           Parent::nextOut(edge);
deba@2040:         }
deba@2040:       } else {
deba@2040:         edge = (*bnode_matching)[node] != INVALID ?
deba@2040:           Parent::direct((*bnode_matching)[node], false) : INVALID;
deba@2040:       }
deba@2040:     }
deba@2040: 
deba@2040:     void nextOut(Edge& edge) const {
deba@2040:       if (Parent::aNode(Parent::source(edge))) {
deba@2040:         Parent::nextOut(edge);
deba@2040:         if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
deba@2040:           Parent::nextOut(edge);
deba@2040:         }
deba@2040:       } else {
deba@2040:         edge = INVALID;
deba@2040:       }
deba@2040:     }
deba@2040:  
deba@2040:     void firstIn(Edge& edge, const Node& node) const {
deba@2040:       if (Parent::aNode(node)) {
deba@2040:         edge = (*bnode_matching)[node] != INVALID ?
deba@2040:           Parent::direct((*anode_matching)[node], false) : INVALID;
deba@2040:       } else {
deba@2040:         Parent::firstIn(edge, node);
deba@2040:         if (edge != INVALID && (*bnode_matching)[node] == edge) {
deba@2040:           Parent::nextIn(edge);
deba@2040:         }
deba@2040:       }
deba@2040:     }
deba@2040: 
deba@2040:     void nextIn(Edge& edge) const {
deba@2040:       if (Parent::aNode(Parent::target(edge))) {
deba@2040:         edge = INVALID;
deba@2040:       } else {
deba@2040:         Parent::nextIn(edge);
deba@2040:         if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
deba@2040:           Parent::nextIn(edge);
deba@2040:         }
deba@2040:       }
deba@2040:     } 
deba@2040: 
deba@2040:   private:
deba@2040:     ANodeMatchingMap* anode_matching;
deba@2040:     BNodeMatchingMap* bnode_matching;
deba@2040:   };
deba@2040: 
deba@2040: 
deba@2040:   /// \ingroup graph_adaptors
deba@2040:   ///
deba@2040:   /// \brief Bipartite graph adaptor to implement matching algorithms.
deba@2040:   ///
deba@2040:   /// Bipartite graph adaptor to implement matchings. It implements
deba@2040:   /// the residual graph of the matching.
deba@2040:   template <typename _BpUGraph, 
deba@2231:             typename _ANMatchingMap = 
deba@2231:             typename _BpUGraph::template ANodeMap<typename _BpUGraph::UEdge>, 
deba@2231:             typename _BNMatchingMap =
deba@2231:             typename _BpUGraph::template BNodeMap<typename _BpUGraph::UEdge> >
deba@2040:   class MatchingBpUGraphAdaptor 
deba@2040:     : public BpUGraphAdaptorExtender<
deba@2040:     MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> > 
deba@2040:   { 
deba@2040:   public:
deba@2040: 
deba@2040:     typedef _BpUGraph BpUGraph;
deba@2040:     typedef _BpUGraph Graph;
deba@2040:     typedef _ANMatchingMap ANodeMatchingMap;
deba@2040:     typedef _BNMatchingMap BNodeMatchingMap;
deba@2040:     typedef BpUGraphAdaptorExtender<
deba@2040:       MatchingBpUGraphAdaptorBase<BpUGraph, 
deba@2040:                                   ANodeMatchingMap, BNodeMatchingMap> > 
deba@2040:     Parent;
deba@2040: 
deba@2040:   protected:
deba@2040:     MatchingBpUGraphAdaptor() : Parent() {}
deba@2040: 
deba@2040:   public:
deba@2040: 
deba@2040:     MatchingBpUGraphAdaptor(const Graph& _graph, 
deba@2040:                             ANodeMatchingMap& _anode_matching,
deba@2040:                             BNodeMatchingMap& _bnode_matching) {
deba@2040:       setGraph(_graph);
deba@2040:       setANodeMatchingMap(_anode_matching);
deba@2040:       setBNodeMatchingMap(_bnode_matching);
deba@2040:     }
deba@2040: 
deba@2040:   };
deba@2040: 
deba@2031: }
deba@2031: 
deba@2031: #endif