/**------------------------------------------------------------------------
 * @file
 *
 * Copyright 2001 by the University of Toronto (UT).
 *
 *                       All Rights Reserved
 * 
 * Permission to copy and modify this software and its documentation 
 * only for internal use in your organization is hereby granted, 
 * provided that this notice is retained thereon and on all copies.  
 * UT makes no representations as to the suitability and operability 
 * of this software for any purpose.  It is provided "as is" without 
 * express or implied warranty.
 *
 * UT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
 * SHALL UT BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA
 * OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 *
 * No other rights, including for example, the right to redistribute 
 * this software and its documentation or the right to prepare 
 * derivative works, are granted unless specifically provided in a 
 * separate license agreement.
 *
 * Author: Diego Macrini based on Ali Shokoufandeh's original code
 * 
 * $Log: DAG.h,v $
 * Revision 1.6  2002/06/17 23:09:11  dmac
 * Matching algorithm updated.
 *
 * Revision 1.5  2002/06/14 23:13:03  dmac
 * Matching algorithm updated.
 *
 * Revision 1.4  2002/06/13 21:46:37  dmac
 * Matching algorithm updated.
 *
 * Revision 1.3  2002/06/10 18:37:33  dmac
 * New class that handles the node distance function added.
 *
 * Revision 1.2  2002/05/16 22:48:56  dmac
 * Several bugs fixed and a new DAG-derived class added
 *
 * Revision 1.1.1.1  2002/03/10 07:38:07  dmac
 * Imported sources
 *
 *
 *-----------------------------------------------------------------------*/

#ifndef __DAG_H__
#define __DAG_H__

#include <fstream>
#include <LEDA/graph/graph_alg.h>

// Add the line bellow AFTER graph_alg.h!
#include <LEDA/core/d_array.h>

#include "DAGNode.h"
#include "DMLString.h"

#include <newmatap.h>
#include <newmatio.h>

namespace dml {

//#define Matrix NEWMAT::Matrix
typedef NEWMAT::Matrix Matrix;

typedef leda::list<leda::edge> EdgeList;
typedef leda::list<leda::node> NodeList;
typedef leda::d_array<leda::node, leda::node> NodeMap;
typedef leda::d_array<leda::edge, leda::node> EdgeNodeMap;
typedef leda::d_array<leda::node, leda::list_item> NodeListItemMap;
typedef leda::d_array<leda::node, int> NodeIndexMap;

typedef leda::list<DAGNodePtr> DAGNodeList;
typedef leda::d_array<DAGNodePtr, DAGNodePtr> DAGNodeMap;

typedef SmartMatrix<double> SimMatrix;
typedef SmartArray<int> NodeIdxArray;
typedef SmartArray<NodeIdxArray> NodeIdxMatrix;

typedef LEDA_GRAPH<DAGNodePtr, double> DAG_BASE_CLASS;

class DistMeasurer;
class MatchedNodePair;
class DAG;

//! /see template<class T> SmartPtr.
typedef SmartPtr<DAG> DAGPtr;


/*! 
	\brief This class represents the DAG ADT.

	DAG is an abstract class derived from the parameterized LEDA graph. 
	This class can only be used by deriving a new class from it and overwriting
	its abstract functions.

	The information contained in each node is a pointer to a DAGNode, which 
	in turn is another abstract class. In order to handle the destruction of the
	objects referenced by these pointers, the class DAGNodePtr was created to keep
	track of the references to DAGNode's and delete them when no pointer points to
	them anymore.

	The information in each edge is a 'double' that represents its weigth. 

	/see DAGNode and DAGNodePtr.
*/

class DAG : public DAG_BASE_CLASS
{
public:
	//! Possible similarity functions.
    enum SF {EXP_NEG_SUM, INV_NODE_DIST, INV_NODE_DIST_AND_TSV, ID_NODE_DIST};
	typedef double distance_type;

	struct MatchParams
	{
		SF nSimFuncType;		//!< Node similarity function used when matching DAGs
		int nNodeDistFunc;		//!< Node distance function
		double dTSVSimWeight;		//!< TSV similarity weight
		double dSimilMassWeight;	//!< Similarity vs node's relative mass weight
		double dRelMassWeight;		//!< Relative mass weight for query vs model
		double dMinNodeSim;		//!< Minimum node similarity allowed
		double dBreakSibRelPen;		//!< Breaking siblings relationship penalty
		int nPreserveAncestorRel;	//!< Preserve the ancestor relations when matching

		//Indexing params
		int nUseNewVoteWeightFunc;	//!< Indexing: use new vote weighting function
		int nUseMOOVC;			//!< Indexing: use multiple one-to-one vote counting

		MatchParams();
		void Print(std::ostream& os) const;
	};

private:
	String strGraphLbl;			//!< Graph label. e.g. the source image file name.
	int nFileOffset;			//!< file offset where this DAG is located.
	int nDAGId;				//!< Id of the DAG in the DB. Is transitory so mustn't be saved.
	int nCumulativeMass;			//!< Sum of all the nodes' masses

	// Derived values
	int nMaxBFactor;			//!< Maximum branching factor of the DAG.
	double dTotalTSVSum;			//!< sume of all the node's TSV magnitudes.
	TSV eigenVals;				//!< All the DAG's adj matrix eigen values (experimental)
	SmartMatrix<int> transClosMat;		//!< The adjacency matrix of the transitive closure graph

protected:
	int nViewNumber;
	String strObjectName;

	DistMeasurer* pDistMeasurer;

	static MatchParams s_matchParams;
	static bool s_bDbgMode;

protected:
	TSV& GetNodeTSV(leda::node v)				{ return operator[](v)->GetTSV(); }
	const TSV& GetNodeTSV(leda::node v) const		{ return inf(v)->GetTSV(); }
	void SetEigenVals(const Matrix& adj);

public:
// Virtual functions:
	virtual ~DAG() { }	//!< Necessary virtual destructor.
	virtual DAG& operator=(const DAG& rhs);
	virtual void Clear();
	virtual double NodeSimilarity(leda::node g1Node, const DAG& g2, leda::node g2Node) const;
	virtual double  EigenDistance(leda::node g1Node, const DAG& g2, leda::node g2Node) const;
	virtual void Print(std::ostream& os = std::cout) const;
	virtual std::istream& Read(std::istream& is, bool bOnlyDataForMatching = false);
	virtual std::ostream& Write(std::ostream& os) const;
	virtual void ComputeDerivedValues();

// Pure virtual functions:
	virtual double NodeDistance(leda::node g1Node, const DAG& g2, leda::node g2Node) const = 0;
	virtual bool AreNodesRelated(leda::node g1Node, const DAG& g2, leda::node g2Node) const = 0;
	virtual DAG* CreateObject() const = 0;
	virtual DAGNodePtr CreateNodeObject(NODE_LABEL lbl) const = 0;
	virtual DAGNodePtr ReadNode(std::istream& is) const = 0;
	virtual String ClassName() const = 0;
	virtual int NodeType(leda::node v) const = 0;

#ifdef XML_READING
	virtual bool ReadFromXMLFile(const char* szFileName, bool bCompEigenLbl = true) = 0;
#endif //XML_READING

// Inline functions:
	DAG ()							{ Clear(); pDistMeasurer = NULL;}
	leda::node NewNode(DAGNodePtr ptr)			{ return DAG_BASE_CLASS::new_node(ptr); }
	leda::edge NewEdge(leda::node u, leda::node v, double dVal = 1.0)				
								{ return DAG_BASE_CLASS::new_edge(u, v, dVal); }
	void DelEdge(leda::edge e)				{ del_edge(e); }
	int GetNodeCount() const				{ return number_of_nodes(); }
	int GetEdgeCount() const				{ return number_of_edges(); }
	double GetEdgeWeight(leda::edge e) const			{ return inf(e); }
	NODE_LABEL GetNodeLbl(leda::node v) const		{ return inf(v)->GetNodeLbl(); }
	double GetEigenLbl(leda::node v) const			{ return inf(v)->GetEigenLbl(); }

	TSV GetNodeTSV(leda::node v, int nDim) const 		{ return inf(v)->GetTSV(nDim); }
	double GetNodeTSVNorm(leda::node v) const		{ return inf(v)->GetTSVNorm(); }

	const DAGNodePtr GetNode(leda::node v) const		{ return inf(v); }
	DAGNodePtr& GetNode(leda::node v)			{ return operator[](v); }
	leda::node GetNode(int nIndex);

	void SetNodeLbl(leda::node v, NODE_LABEL lbl)		{ operator[](v)->SetNodeLbl(lbl); }
	void SetEigenLbl(leda::node v, double lbl)		{ operator[](v)->SetEigenLbl(lbl); }

	int GetNodeIndex(leda::node v) const			{ return index(v); }

	String GetDAGLbl()	const				{ return strGraphLbl; }
	void SetDAGLbl(const char* szLbl)			{ strGraphLbl = szLbl; }

	int GetDAGId() const 					{ return nDAGId; }
	void SetDAGId(int nId) 					{ nDAGId = nId; }

	int GetFileOffset()	const				{ return nFileOffset; }
	
	int GetMaxTSVDimension() const				{ return nMaxBFactor + 1; }
	double GetTotalTSVSum() const				{ return dTotalTSVSum; }
	int GetViewNumber() const				{ return nViewNumber; }
	const String& GetObjName() const			{ return strObjectName; }
	
	void SetViewNumber(int n) 				{ nViewNumber = n; }
	void SetObjName(char *str) 				{ strObjectName = str; }

	int GetNodeMass(leda::node v) const 			{ return GetNode(v)->GetMass(); }
	int GetNodeLevel(leda::node v) const 			{ return GetNode(v)->GetLevel(); }
	int GetNodeDFSIndex(leda::node v) const 			{ return GetNode(v)->GetDFSIndex(); }
	bool IsNodeVisited(leda::node v) const 			{ return GetNode(v)->Visited(); }

	leda::node GetFirstParent(leda::node v) const		{ return source(first_in_edge(v)); }
	leda::node GetSecondParent(leda::node v) const		{ return source(in_succ(first_in_edge(v))); }

	leda::node GetFirstChild(leda::node v) const		{ return target(first_adj_edge(v)); }
	leda::node GetSecondChild(leda::node v) const		{ return target(adj_succ(first_adj_edge(v))); }

	double Similarity(const DAG& model, DAGNodeMap& nodeMap, bool bRecomputeTSVs = false) const
	{
		return DAG::Similarity(*this, model, nodeMap, bRecomputeTSVs);
	}

	void DeleteSubDAG(leda::node v);

	double ComputeTSVs(leda::node root);
	double ComputeTSVs(leda::node v, int& j, Matrix& adj, NodeIndexMap& loopyNodeMap);
	//double ComputeTSVs(leda::node v, Matrix& adj);
	int AddTreeToMatrix(leda::node r, int i, Matrix& adj);

// Static functions:
	static void SetMatchParams(const MatchParams& matchParams) { s_matchParams = matchParams; }

	static double ComputeEigenSum(const Matrix& adj, int nVals);
	static double ComputeLaplacian(const Matrix& adj);
	static void ComputeHeights(const Matrix& adj, Matrix& m);

	static double Match(DAG& g1, DAG& g2, SimMatrix& simMat,
		DAGNodeMap& paired1, DAGNodeMap& paired2, MatchedNodePair* pMatchedPair = NULL);

	static leda::edge ComputeBipartiteGraph(LEDA_GRAPH<leda::node, double>& G, 
		const DAG& g1, const DAG& g2, SimMatrix& simMat,
		const DAGNodeMap& paired1, const DAGNodeMap& paired2, 
		MatchedNodePair* pMatchedPair = NULL);
	
	static double Similarity(const DAG& image, const DAG& model, 
		DAGNodeMap& nodeMap, bool bRecomputeTSVs = false);

	static double Distance(const DAG& image, const DAG& model, 
		DAGNodeMap& nodeMap, bool bRecomputeTSVs = false);


// Non-virtual const functions:
	void AddEdge(Matrix& adj, leda::edge e, int sourceNodeLbl, int targetNodeLbl) const;
	void DelEdge(Matrix& adj, int sourceNodeLbl, int targetNodeLbl) const;
	leda::node GetFirstRootNode() const;
	leda::node GetNextRootNode(leda::node v) const;
	SmartArray<leda::node> GetAllRoots() const;
	void PrintTSVs(std::ostream& os = std::cout) const;
	double NodeTSVSimilarity(leda::node u, const DAG& from, leda::node v) const;
	void PrintAdjMatrix(std::ostream& os = std::cout);
	leda::node DFSGetNext(leda::node v, EdgeList& l, bool bVisitNode = true) const;
	leda::node BFSGetNext(leda::node v, EdgeList& l, bool bVisitNode = true) const;

	const SmartMatrix<int>& GetTransClosMat() const { return transClosMat; }

// Non-virtual non-const functions:
	DAGPtr SplitSubGraph(leda::node v, bool bRecomputeTSVs = false);
	leda::node SplitSubGraph(leda::node v, DAGPtr& ptrDag, NodeMap& nodeParentMap, leda::edge inEdge);
	void ComputeTransiveClosure();
	int ComputeNodesInfo(leda::node v, int nLevel, int nDFSIndex);
	void ResetNodesInfo();
	void ComputeNodesMass();

	friend std::ostream& operator<<(std::ostream &os, const DAG& dag)		{ return dag.Write(os); }
	friend std::istream& operator>>(std::istream &is, DAG& dag)		{ return dag.Read(is); }

	//! Lower case version of Read()
	std::istream& read(std::istream& is) { return Read(is); }

	//! Lower case version of Write()
	std::ostream& write(std::ostream& os) const { return Write(os); }

private:
	//! Base class' function that should not be called.
	leda::node new_node(DAGNodePtr ptr = (DAGNode*)NULL)		{ return NewNode(ptr); }

	//! Base class' function that should not be called.
	leda::edge new_edge(leda::node u, leda::node v, double dVal = 0.0) { return NewEdge(u, v, dVal); }

public:
	static void EnterDbgMode() { s_bDbgMode = true; }
	static void LeaveDbgMode() { s_bDbgMode = false; }
	static bool IsDbgMode()	{ return s_bDbgMode; }
	static const MatchParams& GetMatchParams() 			{ return s_matchParams; }
};

/*! Generic Distance Measuring class. */

class DistMeasurer
{
protected:
	virtual double CompDistance() const = 0;

public:
	virtual ~DistMeasurer() {}

	virtual double GetDistance(const DAG& dag1, leda::node u, 
		const DAG& dag2, leda::node v) = 0;
};

/*! Generic Distance Measuring class for a given graph class and
	node class. */

template <class G, class V> class DistMeasurerT : public DistMeasurer
{
 protected:
	 const G* pG1, *pG2;
	 const V* pNode1, *pNode2;
	 leda::node v1, v2;
	 
 public:
	 DistMeasurerT()
	 {
		 pG1 = NULL;
		 pG2 = NULL;
		 pNode1 = NULL;
		 pNode2 = NULL;
		 v1 = nil;
		 v2 = nil;
	 }
	 
	 double GetDistance(const DAG& dag1, leda::node u, const DAG& dag2, leda::node v)
	 {
		 pG1 = dynamic_cast<const G*>(&dag1);
		 pG2 = dynamic_cast<const G*>(&dag2);
		 pNode1 = dynamic_cast<const V*>((const DAGNode*) dag1.GetNode(u));
		 pNode2 = dynamic_cast<const V*>((const DAGNode*) dag2.GetNode(v));
		 
		 ASSERT(pG1 && pG2 && pNode1 && pNode2);
		 
		 v1 = u;
		 v2 = v;
		 
		 return CompDistance();
	 }
};

class MatchedNodePair
{
	int q, m; //<! indices of query and model nodes that were just matched
	
	const SmartMatrix<int>* pQueryTCM; //<! TCM for query
	const SmartMatrix<int>* pModelTCM; //<! TCM for model
	
	NodeIdxMatrix qparents, mparents;	//<! Adjacency matrix for query and model
	const DAG* pMG;

private:
	static bool IsAnsestor(int u, int v, const SmartMatrix<int>& tcm)
	{
		return tcm[u][v] != 0;
	}

	static bool IsSibling(int u, int v, const SmartMatrix<int>& tcm, const NodeIdxMatrix& parents)
	{
		const NodeIdxArray& vpar = parents[v];

		for (int i = 0; i < vpar.GetSize(); i++)
			if (IsAnsestor(vpar[i], u, tcm))
				return true;

		return false;
	}
	
	static NodeIdxArray GetSiblingsVector(int v, const SmartMatrix<int>& tcm, const NodeIdxMatrix& parents);

public:
	MatchedNodePair(const DAG& query, const DAG& model)
	{	
		pQueryTCM = &query.GetTransClosMat();
		pModelTCM = &model.GetTransClosMat();
		SetParents(query, qparents);
		SetParents(model, mparents);
		SetEmpty();
		pMG = &model;
	}
	
	void SetEmpty() { q = m = -1; }
	bool IsEmpty() const { return q == -1 && m == -1; }
	
	void SetNodes(int v1, int v2)
	{
		q = v1;
		m = v2;
	}
	
	void SetParents(const DAG& g, NodeIdxMatrix& parents);
	
	int GetQueryNode() const { return q; }
	int GetModelNode() const { return m; }

	bool AnsestorRelPreserved(int qq, int mm) const
	{
		bool aq = IsAnsestor(qq, q, *pQueryTCM), am = IsAnsestor(mm, m, *pModelTCM);
		return (aq && am) || (!aq && !am);
	}

	bool SiblingRelPreserved(int qq, int mm) const
	{
		bool sq = IsSibling(qq, q, *pQueryTCM, qparents), sm = IsSibling(mm, m, *pModelTCM, mparents);
		return  (sq && sm) || (!sq && !sm);
	}
	
	void UpdateSimMat(SimMatrix& simMat, const double& alpha) const;
};

enum METHOD {MWMC, MW};

class SimilarityGraph : public LEDA_GRAPH<leda::node, double>
{
	NodeMap g1Map, g2Map;
	EdgeNodeMap g1MatchedNodeMap, g2MatchedNodeMap;
	const DAG* pG1, *pG2;

public:
	SimilarityGraph(const DAG& g1, const DAG& g2)
	{
		pG1 = &g1;
		pG2 = &g2;
	}

	leda::node MapNode(NodeMap& map, leda::node v)
	{
		if (!map.defined(v))
			return map[v] = new_node(v);
		else
			return map[v];
	}

	bool IsG1NodeMapped(leda::node v) const
	{
		return g1Map.defined(v);
	}

	bool IsG2NodeMapped(leda::node v) const
	{
		return g2Map.defined(v);
	}

	void Add(leda::node g1Node, leda::node g2Node, double dSimilarity, 
		leda::node g1MatchedNode, leda::node g2MatchedNode);

	void Add(leda::node g1Node, leda::node g2Node, double dSimilarity);

	void MergeG2Nodes(leda::node remNode, leda::node delNode);

	double ComputeBestAssignment(METHOD nMethod, int* pnMatched, NodeMap* pNodeMap = NULL);
};

} //namespace dml

#endif //__DAG_H__

