deba@2031: /* -*- C++ -*-
deba@2031:  *
deba@2031:  * This file is a part of LEMON, a generic C++ optimization library
deba@2031:  *
deba@2031:  * Copyright (C) 2003-2006
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@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@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@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@2031:     Edge findEdge(const Node& source, const Node& target, 
deba@2031: 		  const Edge& prev = INVALID) {
deba@2031:       return graph->findEdge(source, target, prev);
deba@2031:     }
deba@2031:     UEdge findUEdge(const Node& source, const Node& target, 
deba@2031:                     const UEdge& prev = INVALID) {
deba@2031:       return graph->findUEdge(source, target, prev);
deba@2031:     }
deba@2031:   
deba@2031:     Node addNode() const { return graph->addNode(); }
deba@2031:     UEdge addEdge(const Node& source, const Node& target) const { 
deba@2031:       return graph->addEdge(source, target); 
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@2031:     Node fromNodeId(int id) const { return graph->fromNodeId(id); }
deba@2031:     ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
deba@2031:     BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
deba@2031:     Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
deba@2031:     UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
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@2031:     NodeNotifier& getNotifier(Node) const {
deba@2031:       return graph->getNotifier(Node()); 
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
deba@2031:     ANodeNotifier& getNotifier(ANode) const {
deba@2031:       return graph->getNotifier(ANode());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
deba@2031:     BNodeNotifier& getNotifier(BNode) const {
deba@2031:       return graph->getNotifier(BNode());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@2031:     EdgeNotifier& getNotifier(Edge) const {
deba@2031:       return graph->getNotifier(Edge());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
deba@2031:     UEdgeNotifier& getNotifier(UEdge) const {
deba@2031:       return graph->getNotifier(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@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@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@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@2031:     ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
deba@2031:     BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
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@2031:     ANodeNotifier& getNotifier(ANode) const {
deba@2031:       return Parent::getNotifier(typename Parent::BNode());
deba@2031:     } 
deba@2031: 
deba@2031:     typedef typename Parent::ANodeNotifier BNodeNotifier;
deba@2031:     BNodeNotifier& getNotifier(BNode) const {
deba@2031:       return Parent::getNotifier(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@2031:   /// a-nodeset will be the original graph's b-nodeset and the adaptor's
deba@2031:   /// b-nodeset will be the original graph's a-nodeset. 
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@2031:     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
deba@2031: 
deba@2031:   };
deba@2031: 
deba@2031: 
deba@2031: }
deba@2031: 
deba@2031: #endif