/*
????emd.c

????Last?update:?3/14/98

????An?implementation?of?the?Earth?Movers?Distance.
????based?of?the?solution?for?the?Transportation?problem?as?described?in
????“Introduction?to?Mathematical?Programming“?by?F.?S.?Hillier?and?
????G.?J.?Lieberman?McGraw-Hill?1990.

????Copyright?（C）?1998?Yossi?Rubner
????Computer?Science?Department?Stanford?University
????E-Mail:?rubner@cs.stanford.edu???URL:?http://vision.stanford.edu/~rubner
*/

#include?
#include?
#include?

#include?“emd.h“

#define?DEBUG_LEVEL?0
/*
?DEBUG_LEVEL:
???0?=?NO?MESSAGES
???1?=?PRINT?THE?NUMBER?OF?ITERATIONS?AND?THE?FINAL?RESULT
???2?=?PRINT?THE?RESULT?AFTER?EVERY?ITERATION
???3?=?PRINT?ALSO?THE?FLOW?AFTER?EVERY?ITERATION
???4?=?PRINT?A?LOT?OF?INFORMATION?（PROBABLY?USEFUL?ONLY?FOR?THE?AUTHOR）
*/


#define?MAX_SIG_SIZE1??（MAX_SIG_SIZE+1）??/*?FOR?THE?POSIBLE?DUMMY?FEATURE?*/

/*?NEW?TYPES?DEFINITION?*/

/*?node1_t?IS?USED?FOR?SINGLE-linkED?LISTS?*/
typedef?struct?node1_t?{
??int?i;
??double?val;
??struct?node1_t?*Next;
}?node1_t;

/*?node1_t?IS?USED?FOR?DOUBLE-linkED?LISTS?*/
typedef?struct?node2_t?{
??int?i?j;
??double?val;
??struct?node2_t?*NextC;???????????????/*?NEXT?COLUMN?*/
??struct?node2_t?*NextR;???????????????/*?NEXT?ROW?*/
}?node2_t;



/*?GLOBAL?VARIABLE?DECLARATION?*/
static?int?_n1?_n2;??????????????????????????/*?SIGNATURES?SIZES?*/
static?float?_C[MAX_SIG_SIZE1][MAX_SIG_SIZE1];/*?THE?COST?MATRIX?*/
static?node2_t?_X[MAX_SIG_SIZE1*2];????????????/*?THE?BASIC?VARIABLES?VECTOR?*/
/*?VARIABLES?TO?HANDLE?_X?EFFICIENTLY?*/
static?node2_t?*_EndX?*_EnterX;
static?char?_IsX[MAX_SIG_SIZE1][MAX_SIG_SIZE1];
static?node2_t?*_RowsX[MAX_SIG_SIZE1]?*_ColsX[MAX_SIG_SIZE1];
static?double?_maxW;
static?float?_maxC;

/*?DECLARATION?OF?FUNCTIONS?*/
static?float?init（signature_t?*Signature1?signature_t?*Signature2
		??float?（*Dist）（feature_t?*?feature_t?*））;
static?void?findBasicVariables（node1_t?*U?node1_t?*V）;
static?int?isOptimal（node1_t?*U?node1_t?*V）;
static?int?findLoop（node2_t?**Loop）;
static?void?newSol（）;
static?void?russel（double?*S?double?*D）;
static?void?addBasicVariable（int?minI?int?minJ?double?*S?double?*D?
			?????node1_t?*PrevUMinI?node1_t?*PrevVMinJ
			?????node1_t?*UHead）;
#if?DEBUG_LEVEL?>?0
static?void?printSolution（）;
#endif


/******************************************************************************
float?emd（signature_t?*Signature1?signature_t?*Signature2
	??float?（*Dist）（feature_t?*?feature_t?*）?flow_t?*Flow?int?*FlowSize）
??
where

???Signature1?Signature2??Pointers?to?signatures?that?their?distance?we?want
??????????????to?compute.
???Dist???????Pointer?to?the?ground?distance.?i.e.?the?function?that?computes
??????????????the?distance?between?two?features.
???Flow???????（Optional）?Pointer?to?a?vector?of?flow_t?（defined?in?emd.h）?
??????????????where?the?resulting?flow?will?be?stored.?Flow?must?have?n1+n2-1
??????????????elements?where?n1?and?n2?are?the?sizes?of?the?two?signatures
??????????????respec

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-02-25?09:28??python-emd-master\
?????文件????????1826??2015-08-17?21:12??python-emd-master\Makefile
?????文件????????5018??2015-05-24?22:28??python-emd-master\README.md
?????目錄???????????0??2015-11-30?23:14??python-emd-master\SolutionConverter_demo\
?????文件???????17920??2010-05-07?15:24??python-emd-master\SolutionConverter_demo\SolutionConverter.exe
?????文件???????13824??2010-05-07?15:24??python-emd-master\SolutionConverter_demo\SolutionConverterLib.dll
?????文件????????5120??2010-04-17?17:41??python-emd-master\SolutionConverter_demo\StringValueAttribute.dll
?????目錄???????????0??2015-11-30?23:14??python-emd-master\_emd\
?????目錄???????????0??2015-11-30?23:14??python-emd-master\_emd\_emd\
?????目錄???????????0??2015-11-30?23:14??python-emd-master\_emd\_emd\Debug\
?????文件????????1281??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\_emd.log
?????目錄???????????0??2015-11-30?23:14??python-emd-master\_emd\_emd\Debug\_emd.tlog\
?????文件????????1452??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\_emd.tlog\CL.read.1.tlog
?????文件?????????762??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\_emd.tlog\CL.write.1.tlog
?????文件?????????167??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\_emd.tlog\_emd.lastbuildstate
?????文件????????1318??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\_emd.tlog\cl.command.1.tlog
?????文件???????????0??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\_emd.tlog\unsuccessfulbuild
?????文件???????19456??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\vc120.idb
?????文件???????53248??2015-08-21?19:53??python-emd-master\_emd\_emd\Debug\vc120.pdb
?????目錄???????????0??2015-11-30?23:14??python-emd-master\_emd\_emd\Release\
?????文件????????5680??2015-08-21?19:58??python-emd-master\_emd\_emd\Release\_emd.log
?????目錄???????????0??2015-11-30?23:14??python-emd-master\_emd\_emd\Release\_emd.tlog\
?????文件?????????169??2015-08-21?19:58??python-emd-master\_emd\_emd\Release\_emd.tlog\_emd.lastbuildstate
?????文件????????1526??2015-08-21?19:56??python-emd-master\_emd\_emd\Release\_emd.tlog\cl.command.1.tlog
?????文件???????20736??2015-08-21?19:56??python-emd-master\_emd\_emd\Release\_emd.tlog\cl.read.1.tlog
?????文件?????????936??2015-08-21?19:56??python-emd-master\_emd\_emd\Release\_emd.tlog\cl.write.1.tlog
?????文件???????????2??2015-08-21?19:58??python-emd-master\_emd\_emd\Release\_emd.tlog\link.command.1.tlog
?????文件???????????2??2015-08-21?19:58??python-emd-master\_emd\_emd\Release\_emd.tlog\link.read.1.tlog
?????文件???????????2??2015-08-21?19:58??python-emd-master\_emd\_emd\Release\_emd.tlog\link.write.1.tlog
?????文件???????????0??2015-08-21?19:58??python-emd-master\_emd\_emd\Release\_emd.tlog\unsuccessfulbuild
?????文件???????54809??2015-08-21?19:56??python-emd-master\_emd\_emd\Release\emd.obj
............此處省略5782個文件信息