#ifndef _GRAPH_H_
#define _GRAPH_H_

#include "Mesh.h"

#define SIMPLE_WEIGHTING //define this to weight graph edges by simply averaging the distortions at endpoint graph vertices (gvert represents a map permutation)

struct GVertex
{
	//each graph vertex represents a map and its isometric distortion and ground-truth distortion (grd-truth for evaluation purposes only)
	vector< int > map;
	float distortion, grdTruthDistortion;

	//this vert represents a map b/w 2 meshes; idx of the source (sidx) and target (tidx) meshes in meshes[]
	int sidx, tidx;

	//dSpanningUnn[j] gives the distance of the shortest path b/w this vert and a target vert j
	float* dSpanningUnn, dSpanned;
	FibHeapNode* heapNode;
	//idx to graph edges incident to this vertex, that is directed graph edges whose start gvert is this one
	vector< int > gedgeList;
	//idx to predecessor of this graph vertex in the shortest path from the source to this graph vertex
	int predecessor;

	GVertex(vector< int > m, float d, int src, int tar) : map(m), distortion(d), sidx(src), tidx(tar) {};
};

struct GEdge
{
	//idx to endpnt graph verts of this directed edge, from gv1 to gv2
	int gv1, gv2;

	//weight/cost of connecting graph vertices gv1 and gv2
	float length;

	GEdge(int i1, int i2, float l) : gv1(i1), gv2(i2), length(l) {};
};

struct GPath //path of maps (= gverts)
{
	//maps[] provides an idx to gverts[] to retrieve a gvert/map on this path
	vector< int > maps;
	//overall isometric distorion of all C(maps.size+1, 2) pairwise maps = the ones b/w consecutive meshes (maps[]) plus all other maps implied/composed by maps[]
	float overallDistortion;
};

class Graph
{
private:
	//meshes forming the collection of shapes
	Mesh** meshes;
	int startIdx, stopIdx, middleIdx, nMeshes;
	//output file for 2 consecutive meshes in collection
	FILE** outFiles;	
	int topK, //# of graph vertices to put on a graph between 2 consecutive meshes; these vertices are related to maps and we use just first topK of all N! maps in the graph
		P; //# of best-fit paths for the current map to be appended; when P=1 computePaths3() works same as computePaths2()

	//graph's vertices and edges where each vert/node is one of N! 1-to-1 maps b/w N extremes (not all N! in use) and each edge is the average distortion of the connected 1-to-1 maps
	vector< GVertex* > gverts;
	vector< GEdge* > gedges;
	//output of our algorithm as idxs to gverts to get the desired maps; using these maps b/w consecutive pairs, one may also compose the remaining maps as in the bottom of solve()
	vector< int > mapsOnTheOptimalPath;
	//N! pathes from meshes[0] to meshes[target-1] in computePaths()
	vector< GPath* >* pathsTo;

	//is ground-truth info available for theInput to be used in evaluation only?
	bool grdTruth;
	
	void addGVertices(int m1, int m2, bool spectralInitToMatchMore);
	void extractMapsOnTheShortestPath(int virtualSource, int v, int virtualTarget);
	void printMap(int fIdx, int mIdx, bool toCmdPrompt = false);

	void computePaths(int target);
	void computePaths2(int target);
/*	//no cost of keeping these unused functions 'cos nearly every compiler will skip non-used code when compiling with optimizations turned on; if the compiler misses it, a tiny penalty comes 'cos the code/binary is bigger and gives cache misses	
	void computePaths3(int target);//*/
	void findTheOptimalPath(bool evalAllPairwiseDistortions, bool interpCoarseToDense);
	inline float getGrdTruthDistortion(int m1, int m2, vector< int > tmpSafeCorrespTry);
	inline bool symFlipped(float grdTruthDistortion);
public:
	int N; //# of extremes on meshes b/w which maps will be formed (naming as extremes sucks if SPECTRAL_INIT_TO_MATCH_MORE defined 'cos i match evenly-spaced samples, not extremes, in that case)
	//evaluate these quantities over all mesh triplets if MESH_TRIPLETS_ONLY is defined
	float overallIsoDistOfTriplet, overallGrdTruthDistOfTriplet;
	int overallSymFlips;

	Graph(int start, int stop) : startIdx(start), stopIdx(stop), N(9), topK(16), P(10) {}; //if topK is increased to huge values, e.g. 30+, go change tooBigDistortion to 1+ to prevent dummy map additions; N'll be overwritten in MAIN.cpp in this public release
	Graph(int start, int mid, int stop) : startIdx(start), middleIdx(mid), stopIdx(stop), N(9), topK(16), P(10) {}; //for 3 shapes use this constructor

	void loadMeshes(char* fileFormat, bool dynamicProgramming, int version, bool spectralInitToMatchMore = false);
	void loadMeshTriplets(char* fileFormat, bool dynamicProgramming, int version, bool spectralInitToMatchMore = false);
	//void deleteMeshTriplets();
	void build(bool dynamicProgramming, bool spectralInitToMatchMore = false);
	bool solve();
	void computeOptimalMultipleCorrespondence(int version, bool interpCoarseToDense);
	void bruteForceMultipleCorrespondence();
};

#endif
