my_hamilton.h

哈密尔顿近似算法的语言实现及旅行商问题的实现

#ifndef		__MY_HAMILTON_H__
#define		__MY_HAMILTON_H__

//#define		__MY_HAMILTON_DEBUG__
#define		__MY_HAMILTON_RELEASE__

#define		N_NODE		20								/* node number */
#define		N_EDGE		(N_NODE)*((N_NODE)-1)/2			/* edge number = 4(4-1)/2, for it's undirected graph */

typedef struct EDGEWEIGHT_TP{
    unsigned int    edgeNum;                /* edge number, start from 1 */
    unsigned int    node1;                  /* related node1, start from 1 */
    unsigned int    node2;                  /* related node2, start from 2 */
    unsigned int	weight;					/* edge weight, non-negtive */
    unsigned int	deleted;				/* delete flag */
}EDGEWEIGHT;

int		szEdge;									/* edge number */
int		szNode;									/* node number */
EDGEWEIGHT	sqEdgeWeight[N_EDGE+1];				/* init edge weight sequence, [0] is unused */
int    	sqIndex = 1;							/* current index of sqEdgeWeight,start from 1 */
EDGEWEIGHT	stEdgeWeight[N_EDGE+1];				/* edge weight sequece set S, [0] is unused */
int		stIndex = 1;							/* current index of stEdgeWeight,start from 1 */
int		degree[N_NODE+1];						/* degree of nodes,[0] is unused */
int		cycle[N_NODE+1];						/* cycle node */

int GetInitEdgeWeight(void);					/* input edge info */
int SortInitEdgeWeight(void);					/* sort edge weight in ascend-method */
int	GreedySearch(void);							/* main body of greedy algorithm */
int	AddEdgeToSet(int);							/* add edge to S set */
int	IsDegreeAbove2(int);						/* check whether some vertex's degree larger than 2 */
int	DelSetEdge(int);       						/* delete edge from S set */
int	CountDegree(void);							/* count each node's degree */
int IsHamiltonCycle(void);						/* check whether S set can form a HC */
int	IsLocalCycle(void);							/* check whetcher S set have local cycle */
int	OutputHC(void);								/* output Hamilton-Cycle */

#ifdef	__MY_HAMILTON_DEBUG__
int PrintEdgeWeightInfo(void);					/* for debug */
int PrintEdgeWeightSetInfo(void);				/* for debug */
int PrintDegree(void);							/* print all nodes' degree info */
#endif

#endif	/* end __MY_HAMILTON_H__ */