///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BIPARTITEMATCHER_H
#define BIPARTITEMATCHER_H
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <limits.h>
#include <vector>
#include <iostream>
#include <LEDA/graph/graph.h>
#include <LEDA/graph/graph_alg.h>
#include <LEDA/graph/mcb_matching.h>
//using namespace leda;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using std::vector;
using std::cerr;
using std::endl;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
typedef leda::GRAPH< unsigned int, short> BipartiteGraph;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
CLASS
	BipartiteMatcher
	
	Implements bipartite matching using LEDA.
	Given a model, a target, edges of possible matches, and a transformation, 
	it will find the best bipartite match.
	
	NOTE: 	HausdorffExtension proves faster and better then BipartiteMatcher.
	
KEYWORDS
 	Bipartite, Match, RMSD, LEDA, RigidTrans3.

AUTHORS
	Ofer Chay (oferchay@yahoo.com).
	Copyright: Structural Bioinfo group, Tel-Aviv Univ. Israel, 2009.

CHANGES LOG

GOALS
	Implements bipartite matching using LEDA.
	Given a model, a target, edges of possible matches, and a transformation, 
	it will find the best bipartitem match.

USAGE
	here are 2 usage examples taken from the TriangleMatch program:
	EXAMPLE
 void TriangleMatch::BipartiteMatchExtension(	const float 			maxAtomDistance,
												const RigidTrans3& 		rigidTrans3,
												Match& 					newMatch)
{
	const register  float maxAtomDistanceSquare = maxAtomDistance*maxAtomDistance;
	BipartiteMatcher bpm(m_sizeModel,m_sizeTarget);
	
	// copy and transform the scene
	Molecule<Atom> transformedScene = m_molTarget;  
	transformedScene.rigidTrans(rigidTrans3);
	
	for(register unsigned int i = 0 ; i < m_sizeModel ; i++)
		for(register unsigned int j = 0 ; j <  transformedScene.size(); j++)
		{
			if (m_molModel[i].dist2(transformedScene[j]) < maxAtomDistanceSquare)
				bpm.addEdge(i,j);
		}

	bpm.update();
	bpm.calculateMatch(newMatch);

	if (newMatch.size() == 0)
	{
		//cout << "BipartiteMatchExtension: Match.size(): == 0; break"<< endl;
		return;
	}
		
	// Implementation Note: Calculating the best fit is necessary for setting the rigid transformation and the rmsd of the match
	newMatch.calculateBestFit(m_molModel,m_molTarget);//newMatch.calculateBestFit(*model, *scene);
#ifdef dbgConsistency
  CheckConsistencyOfMatch(newMatch);
#endif
} 

void TriangleMatch::BipartiteMatchOneVoteList(	const TVectVotes& vVotes ,const RigidTrans3& rigidTrans3,Match& newMatch)
{
	BipartiteMatcher bpm(m_sizeModel,m_sizeTarget);
	
	// copy and transform the scene
	Molecule<Atom> transformedScene = m_molTarget;  
	transformedScene.rigidTrans(rigidTrans3);
	
	TVectVotes::const_iterator it, itend = vVotes.end();
	for(it = vVotes.begin(); it != itend ; it++)
		bpm.addEdge((*it).iModel,(*it).iTarget);

	bpm.update();
	bpm.calculateMatch(newMatch);

	if (newMatch.size() == 0)
		return;
		
	// Implementation Note: Calculating the best fit is necessary for setting the rigid transformation and the rmsd of the match
	newMatch.calculateBestFit(m_molModel,m_molTarget);//newMatch.calculateBestFit(*model, *scene);		
#ifdef dbgConsistency
  CheckConsistencyOfMatch(newMatch);
#endif	
}
END
END
 */

class BipartiteMatcher 
{
public:
	//// m,n are the sizes of each set
	BipartiteMatcher(unsigned int m, unsigned int n) : isMatchUpdated_(false) { init(m, n); }

	////	
	inline void addEdge(unsigned int ai, unsigned int bj);
	//inline void removeEdge(unsigned int ai, unsigned int bj);
	
	////	
	template<class MatchT> 
	inline void calculateMatch(MatchT& match);
	
	////
	inline void update();

	//unsigned int calculateMatch() 
	//{
	//  update();
	//  return matchEdges_.size();
	//}

private:
	inline void init(unsigned int m, unsigned int n);

protected:
	////  
  BipartiteGraph			bipartiteGraph_;
  	////
  leda::list< leda::node>	setA_, setB_;
  	////
  vector< leda::node>		id2nodeSetA_, id2nodeSetB_;
  	////
  unsigned int				sizeA_, sizeB_;
  	////
  leda::list< leda::edge>	matchEdges_;
  	////
  bool 						isMatchUpdated_;
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template< class MatchT>
inline void BipartiteMatcher::calculateMatch(MatchT& match) 
{
  if( !isMatchUpdated_) 
    update();
  
  for(leda::list< leda::edge>::iterator it = matchEdges_.begin(); it != matchEdges_.end(); it++) 
  {
    unsigned int setANode = bipartiteGraph_.inf(source(*it));
    unsigned int setBNode = bipartiteGraph_.inf(target(*it));
    match.add(setANode, setBNode);//match.addMatchingPair(setANode, setBNode);// ofer chay changed code here
  } 
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void BipartiteMatcher::init(unsigned int m, unsigned int n) 
{
  sizeA_ = m;
  sizeB_ = n;
  id2nodeSetA_ = vector< leda::node>(sizeA_);
  id2nodeSetB_ = vector< leda::node>(sizeB_);

  // create all nodes of setA
  for(unsigned int i=0; i<sizeA_; i++) 
  {
    leda::node v = bipartiteGraph_.new_node(i);
    id2nodeSetA_[i] = v; 
    setA_.push_back(v);
  }

  // create all nodes of setB
  for(unsigned int i=0; i<sizeB_; i++) 
  {
    leda::node v = bipartiteGraph_.new_node(i);
    id2nodeSetB_[i] = v;
    setB_.push_back(v);
  }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void BipartiteMatcher::addEdge(unsigned int ai, unsigned int bj) 
{
  isMatchUpdated_ = false;
  leda::node u = id2nodeSetA_[ai];  
  leda::node v = id2nodeSetB_[bj];
  bipartiteGraph_.new_edge(u, v, 0);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void BipartiteMatcher::update() 
{
  if(!isMatchUpdated_) 
  {
    matchEdges_ = MAX_CARD_BIPARTITE_MATCHING(bipartiteGraph_, setA_, setB_);
    
    //leda::node_array<bool> NC(bipartiteGraph_);
    //if (CHECK_MCB(bipartiteGraph_,matchEdges_,NC) == false)
    //	std::cout << "CHECK_MCB(bipartiteGraph_,matchEdges_,NC) == false)" << endl;
  }
  
  isMatchUpdated_ = true;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#endif //BIPARTITEMATCHER_H
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////