/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_BPUGRAPH_ADAPTOR_H
#define LEMON_BPUGRAPH_ADAPTOR_H

#include <lemon/bits/invalid.h>
#include <lemon/maps.h>

#include <lemon/bits/graph_adaptor_extender.h>

#include <lemon/bits/traits.h>

#include <iostream>

///\ingroup graph_adaptors
///\file
///\brief Several graph adaptors.
///
///This file contains several useful bpugraph adaptor functions.
///
///\author Balazs Dezso

namespace lemon {

  /// \ingroup graph_adaptors
  ///
  /// \brief Base type for the Bipartite Undirected Graph Adaptors
  ///
  /// This is the base type for most of LEMON bpugraph adaptors. 
  /// This class implements a trivial graph adaptor i.e. it only wraps the 
  /// functions and types of the graph. The purpose of this class is to 
  /// make easier implementing graph adaptors. E.g. if an adaptor is 
  /// considered which differs from the wrapped graph only in some of its 
  /// functions or types, then it can be derived from BpUGraphAdaptor, and 
  /// only the differences should be implemented.
  ///
  /// \author Balazs Dezso 
  template<typename _BpUGraph>
  class BpUGraphAdaptorBase {
  public:
    typedef _BpUGraph Graph;
    typedef Graph ParentGraph;

  protected:
    Graph* graph;

    BpUGraphAdaptorBase() : graph(0) {}

    void setGraph(Graph& _graph) { graph = &_graph; }

    Graph& getGraph() { return *graph; }
    const Graph& getGraph() const { return *graph; }

  public:

    BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
 
    typedef typename Graph::Node Node;
    typedef typename Graph::ANode ANode;
    typedef typename Graph::BNode BNode;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::UEdge UEdge;
   
    void first(Node& i) const { graph->first(i); }
    void firstANode(Node& i) const { graph->firstANode(i); }
    void firstBNode(Node& i) const { graph->firstBNode(i); }
    void first(Edge& i) const { graph->first(i); }
    void first(UEdge& i) const { graph->first(i); }
    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
    void firstInc(UEdge &i, bool &d, const Node &n) const {
      graph->firstInc(i, d, n);
    }

    void next(Node& i) const { graph->next(i); }
    void nextANode(Node& i) const { graph->nextANode(i); }
    void nextBNode(Node& i) const { graph->nextBNode(i); }
    void next(Edge& i) const { graph->next(i); }
    void next(UEdge& i) const { graph->next(i); }
    void nextIn(Edge& i) const { graph->nextIn(i); }
    void nextOut(Edge& i) const { graph->nextOut(i); }
    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }

    Node source(const UEdge& e) const { return graph->source(e); }
    Node target(const UEdge& e) const { return graph->target(e); }

    Node source(const Edge& e) const { return graph->source(e); }
    Node target(const Edge& e) const { return graph->target(e); }

    Node aNode(const UEdge& e) const { return graph->aNode(e); }
    Node bNode(const UEdge& e) const { return graph->bNode(e); }

    bool aNode(const Node& n) const { return graph->aNode(n); }
    bool bNode(const Node& n) const { return graph->bNode(n); }

    typedef NodeNumTagIndicator<Graph> NodeNumTag;
    int nodeNum() const { return graph->nodeNum(); }
    int aNodeNum() const { return graph->aNodeNum(); }
    int bNodeNum() const { return graph->bNodeNum(); }
    
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    int edgeNum() const { return graph->edgeNum(); }
    int uEdgeNum() const { return graph->uEdgeNum(); }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    Edge findEdge(const Node& source, const Node& target, 
		  const Edge& prev = INVALID) {
      return graph->findEdge(source, target, prev);
    }
    UEdge findUEdge(const Node& source, const Node& target, 
                    const UEdge& prev = INVALID) {
      return graph->findUEdge(source, target, prev);
    }
  
    Node addANode() const { return graph->addANode(); }
    Node addBNode() const { return graph->addBNode(); }
    UEdge addEdge(const Node& source, const Node& target) const { 
      return graph->addEdge(source, target); 
    }

    void erase(const Node& i) const { graph->erase(i); }
    void erase(const UEdge& i) const { graph->erase(i); }
  
    void clear() const { graph->clear(); }

    bool direction(const Edge& e) const { return graph->direction(e); }
    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
    
    int id(const Node& v) const { return graph->id(v); }
    int id(const ANode& v) const { return graph->id(v); }
    int id(const BNode& v) const { return graph->id(v); }
    int id(const Edge& e) const { return graph->id(e); }
    int id(const UEdge& e) const { return graph->id(e); }

    Node fromNodeId(int id) const { return graph->fromNodeId(id); }
    ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
    BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
    Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
    UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }

    int maxNodeId() const { return graph->maxNodeId(); }
    int maxANodeId() const { return graph->maxANodeId(); }
    int maxBNodeId() const { return graph->maxBNodeId(); }
    int maxEdgeId() const { return graph->maxEdgeId(); }
    int maxUEdgeId() const { return graph->maxEdgeId(); }

    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
    NodeNotifier& getNotifier(Node) const {
      return graph->getNotifier(Node()); 
    } 

    typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
    ANodeNotifier& getNotifier(ANode) const {
      return graph->getNotifier(ANode());
    } 

    typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
    BNodeNotifier& getNotifier(BNode) const {
      return graph->getNotifier(BNode());
    } 

    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
    EdgeNotifier& getNotifier(Edge) const {
      return graph->getNotifier(Edge());
    } 

    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
    UEdgeNotifier& getNotifier(UEdge) const {
      return graph->getNotifier(UEdge());
    } 

    template <typename _Value>
    class NodeMap : public Graph::template NodeMap<_Value> {
    public:
      typedef typename Graph::template NodeMap<_Value> Parent;
      explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga) 
	: Parent(*ga.graph) {}
      NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      NodeMap& operator=(const NodeMap& cmap) {
	return operator=<NodeMap>(cmap);
      }

      template <typename CMap>
      NodeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };

    template <typename _Value>
    class ANodeMap : public Graph::template ANodeMap<_Value> {
    public:
      typedef typename Graph::template ANodeMap<_Value> Parent;
      explicit ANodeMap(const BpUGraphAdaptorBase& ga) 
	: Parent(*ga.graph) {}
      ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      ANodeMap& operator=(const ANodeMap& cmap) {
	return operator=<ANodeMap>(cmap);
      }

      template <typename CMap>
      ANodeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };

    template <typename _Value>
    class BNodeMap : public Graph::template BNodeMap<_Value> {
    public:
      typedef typename Graph::template BNodeMap<_Value> Parent;
      explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga) 
	: Parent(*ga.graph) {}
      BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      BNodeMap& operator=(const BNodeMap& cmap) {
	return operator=<BNodeMap>(cmap);
      }

      template <typename CMap>
      BNodeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };

    template <typename _Value>
    class EdgeMap : public Graph::template EdgeMap<_Value> {
    public:
      typedef typename Graph::template EdgeMap<_Value> Parent;
      explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga) 
	: Parent(*ga.graph) {}
      EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      EdgeMap& operator=(const EdgeMap& cmap) {
	return operator=<EdgeMap>(cmap);
      }

      template <typename CMap>
      EdgeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };

    template <typename _Value>
    class UEdgeMap : public Graph::template UEdgeMap<_Value> {
    public:
      typedef typename Graph::template UEdgeMap<_Value> Parent;
      explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga) 
	: Parent(*ga.graph) {}
      UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      UEdgeMap& operator=(const UEdgeMap& cmap) {
	return operator=<UEdgeMap>(cmap);
      }

      template <typename CMap>
      UEdgeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };

  };

  /// \ingroup graph_adaptors
  ///
  /// \brief Trivial Bipartite Undirected Graph Adaptor
  ///
  /// Trivial Bipartite Undirected Graph Adaptor. It does not change
  /// the functionality of the adapted graph.
  template <typename _BpUGraph>
  class BpUGraphAdaptor 
    : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > { 
  public:
    typedef _BpUGraph Graph;
    typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
  protected:
    BpUGraphAdaptor() : Parent() {}

  public:
    explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
  };

  template <typename _BpUGraph>
  class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
  public:
    
    typedef _BpUGraph Graph;
    typedef BpUGraphAdaptorBase<_BpUGraph> Parent;

  protected:
    
    SwapBpUGraphAdaptorBase() {}

  public:

    typedef typename Parent::Node Node;
    typedef typename Parent::BNode ANode;
    typedef typename Parent::ANode BNode;
    typedef typename Parent::Edge Edge;
    typedef typename Parent::UEdge UEdge;

    bool direction(const Edge& e) const { return !Parent::direction(e); }
    Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }

    Node aNode(const UEdge& e) const { return Parent::bNode(e); }
    Node bNode(const UEdge& e) const { return Parent::aNode(e); }

    bool aNode(const Node& n) const { return Parent::bNode(n); }
    bool bNode(const Node& n) const { return Parent::aNode(n); }

    void firstANode(Node& i) const { Parent::firstBNode(i); }
    void firstBNode(Node& i) const { Parent::firstANode(i); }

    void nextANode(Node& i) const { Parent::nextBNode(i); }
    void nextBNode(Node& i) const { Parent::nextANode(i); }

    int id(const ANode& v) const { return Parent::id(v); }
    int id(const BNode& v) const { return Parent::id(v); }

    ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
    BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }

    int maxANodeId() const { return Parent::maxBNodeId(); }
    int maxBNodeId() const { return Parent::maxANodeId(); }

    int aNodeNum() const { return Parent::bNodeNum(); }
    int bNodeNum() const { return Parent::aNodeNum(); }

    typedef typename Parent::BNodeNotifier ANodeNotifier;
    ANodeNotifier& getNotifier(ANode) const {
      return Parent::getNotifier(typename Parent::BNode());
    } 

    typedef typename Parent::ANodeNotifier BNodeNotifier;
    BNodeNotifier& getNotifier(BNode) const {
      return Parent::getNotifier(typename Parent::ANode());
    } 

    template <typename _Value>
    class ANodeMap : public Graph::template BNodeMap<_Value> {
    public:
      typedef typename Graph::template BNodeMap<_Value> Parent;
      explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga) 
	: Parent(*ga.graph) {}
      ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      ANodeMap& operator=(const ANodeMap& cmap) {
	return operator=<ANodeMap>(cmap);
      }

      template <typename CMap>
      ANodeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };

    template <typename _Value>
    class BNodeMap : public Graph::template ANodeMap<_Value> {
    public:
      typedef typename Graph::template ANodeMap<_Value> Parent;
      explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga) 
	: Parent(*ga.graph) {}
      BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
	: Parent(*ga.graph, value) {}

      BNodeMap& operator=(const BNodeMap& cmap) {
	return operator=<BNodeMap>(cmap);
      }

      template <typename CMap>
      BNodeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
	return *this;
      }
    };
    
  };

  /// \ingroup graph_adaptors
  ///
  /// \brief Bipartite graph adaptor which swaps the two nodeset.
  ///
  /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
  /// anode-set will be the original graph's bnode-set and the adaptor's
  /// bnode-set will be the original graph's anode-set.
  ///
  /// As example look at an algorithm what can be sped up with the
  /// swap bipartite undirected graph adaptor. If we want to find the
  /// maximum matching in the bipartite graph then it will be not changed
  /// if we swap the two nodesets. But the algorithm use the two nodeset
  /// different way. If we swap the nodesets it provides different
  /// running time. We run a test on random bipartite graphs with
  /// different rate of the anode-set size and bnode-set size.
  /// We always made graphs with 10000 nodes and 20000 edges and we
  /// computed the maximum cardinality matching with the Hopcroft-Karp 
  /// algorithm.
  ///
  /// The next diagram shows the running time of the tests. If the anode-set
  /// is smaller than the bnode-set the running time is better than with 
  /// the swapped graph. Other conclusion is that the running time
  /// is greater when the two nodesets size are nearly equal. 
  ///
  /// \image html swap_test.png
  /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
  /// 
  /// The next part shows how can we swap the two nodeset:
  ///
  ///\code
  /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
  /// SBpUGraph sbpugraph(bpugraph);
  /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
  ///\endcode
  template <typename _BpUGraph>
  class SwapBpUGraphAdaptor 
    : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > { 
  public:

    typedef _BpUGraph Graph;
    typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > 
    Parent;

  protected:
    SwapBpUGraphAdaptor() : Parent() {}

  public:

    /// \brief Construct a swapped graph.
    ///
    /// Construct a swapped graph.
    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }

  };


  template <typename _BpUGraph, 
            typename _ANMatchingMap, typename _BNMatchingMap>
  class MatchingBpUGraphAdaptorBase 
    : public BpUGraphAdaptorBase<const _BpUGraph>
  {
  public:
    
    typedef _BpUGraph Graph;
    typedef _ANMatchingMap ANodeMatchingMap;
    typedef _BNMatchingMap BNodeMatchingMap;

    typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;

  protected:
    
    MatchingBpUGraphAdaptorBase() {}

    void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
      anode_matching = &_anode_matching;
    }

    void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
      bnode_matching = &_bnode_matching;
    }

  public:

    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;

    void firstOut(Edge& edge, const Node& node) const {
      if (Parent::aNode(node)) {
        Parent::firstOut(edge, node);
        if (edge != INVALID && (*anode_matching)[node] == edge) {
          Parent::nextOut(edge);
        }
      } else {
        edge = (*bnode_matching)[node] != INVALID ?
          Parent::direct((*bnode_matching)[node], false) : INVALID;
      }
    }

    void nextOut(Edge& edge) const {
      if (Parent::aNode(Parent::source(edge))) {
        Parent::nextOut(edge);
        if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
          Parent::nextOut(edge);
        }
      } else {
        edge = INVALID;
      }
    }
 
    void firstIn(Edge& edge, const Node& node) const {
      if (Parent::aNode(node)) {
        edge = (*bnode_matching)[node] != INVALID ?
          Parent::direct((*anode_matching)[node], false) : INVALID;
      } else {
        Parent::firstIn(edge, node);
        if (edge != INVALID && (*bnode_matching)[node] == edge) {
          Parent::nextIn(edge);
        }
      }
    }

    void nextIn(Edge& edge) const {
      if (Parent::aNode(Parent::target(edge))) {
        edge = INVALID;
      } else {
        Parent::nextIn(edge);
        if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
          Parent::nextIn(edge);
        }
      }
    } 

  private:
    ANodeMatchingMap* anode_matching;
    BNodeMatchingMap* bnode_matching;
  };


  /// \ingroup graph_adaptors
  ///
  /// \brief Bipartite graph adaptor to implement matching algorithms.
  ///
  /// Bipartite graph adaptor to implement matchings. It implements
  /// the residual graph of the matching.
  template <typename _BpUGraph, 
            typename _ANMatchingMap, typename _BNMatchingMap>
  class MatchingBpUGraphAdaptor 
    : public BpUGraphAdaptorExtender<
    MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> > 
  { 
  public:

    typedef _BpUGraph BpUGraph;
    typedef _BpUGraph Graph;
    typedef _ANMatchingMap ANodeMatchingMap;
    typedef _BNMatchingMap BNodeMatchingMap;
    typedef BpUGraphAdaptorExtender<
      MatchingBpUGraphAdaptorBase<BpUGraph, 
                                  ANodeMatchingMap, BNodeMatchingMap> > 
    Parent;

  protected:
    MatchingBpUGraphAdaptor() : Parent() {}

  public:

    MatchingBpUGraphAdaptor(const Graph& _graph, 
                            ANodeMatchingMap& _anode_matching,
                            BNodeMatchingMap& _bnode_matching) {
      setGraph(_graph);
      setANodeMatchingMap(_anode_matching);
      setBNodeMatchingMap(_bnode_matching);
    }

  };

}

#endif