my_hamilton.c

算法分析及哈密尔顿问题 算法分析及哈密尔顿问题

/*
  Name: my_hamilton.c
  Copyright: all copyright reserved by rockins
  Author: rockins
  Date: 05-03-06 19:54
  Description: this procedure implements an algorithm for undirected complete hamilton graph
  Note: 
      1.the max dimense size of array is 100
      2.the adjoin-matrix's data is stored in text file,eg,data.txt
      3.the format of data is like this:
            6 4
            1 1 2 1
            2 2 3 2
            3 3 4 3
            4 4 1 4
            5 1 3 5
            6 2 4 6
  Format:edge#,node1,node2,weight
          here the first line means the dimense of the array is 3,and
          following is the real data
  Test result:
      		(abbreviate)
*/

#include <stdio.h>
#include <stdlib.h>
#include "my_hamilton.h"

#ifdef __MY_HAMILTON_DEBUG__
/* feature: print edge info, just for debug */
int PrintEdgeWeightInfo(void)
{
    int	i;
    for (i=1; i<=szEdge; i++)
    {
		printf("edgeNum:%d,node1:%d,node2:%d,weight:%d,deleted:%d\n",
				sqEdgeWeight[i].edgeNum,
				sqEdgeWeight[i].node1,
				sqEdgeWeight[i].node2,
				sqEdgeWeight[i].weight,
    			sqEdgeWeight[i].deleted);
    }
}

/* feature: print edge set S info,just for debugging */
int PrintEdgeWeightSetInfo(void)
{
    int	i;
    for (i=1; i<stIndex; i++)
    {
		printf("edgeNum:%d,node1:%d,node2:%d,weight:%d,deleted:%d\n",
				stEdgeWeight[i].edgeNum,
				stEdgeWeight[i].node1,
				stEdgeWeight[i].node2,
				stEdgeWeight[i].weight,
    			stEdgeWeight[i].deleted);
    }
}

/* feature:print all nodes' degree info */
int PrintDegree(void)
{
    int	i;
    for (i=1; i<=szNode; i++)
    {
        printf("degree of %d:%d\n", i, degree[i]);
    }
}
#endif

/* 	feature: read edge weight data from file
	param: (none)
	retval:	-1,error
			positive value, edge number
*/
int GetInitEdgeWeight(void)
{
    int    i,j;
    FILE   *fp;
    int    n;                   			// edge-weigth array size
#if    defined(__MY_HAMILTON_DEBUG__)
	char   file_name[40]="array2.txt";      	// file path
#elif	defined(__MY_HAMILTON_RELEASE__)
   	char   file_name[40];
    printf("Input the file path:");
    scanf("%s%*c", file_name);         		// read path, but ignore \r(RETURN)
#endif

    fp=fopen(file_name, "r");
    while(fp==NULL)
    {
        printf("cannot open the file,please re-input:");
        scanf("%s%*c", file_name);
        fp=fopen(file_name, "r");
    }
    
    fscanf(fp, "%d", &n);          // first data of first line is the dimense size of matrix
    if (n>N_EDGE)
    {
    	fprintf(stderr, "error: too large graph,please check\n");
    	return(-1);
   	}
   	fscanf(fp, "%d", &szNode);		// second data of first line is node number */
   	if (szNode>N_NODE)
   	{
    	fprintf(stderr, "error: too large graph,please check\n");
    	return(-1);
   	}
#ifdef __MY_HAMILTON_DEBUG__
    printf("in function:%s\n", __func__);
#endif
    for (i=1; i<=n; i++)
    {
        fscanf(fp, "%d", &sqEdgeWeight[i].edgeNum);
        fscanf(fp, "%d", &sqEdgeWeight[i].node1);
        fscanf(fp, "%d", &sqEdgeWeight[i].node2);
        fscanf(fp, "%d", &sqEdgeWeight[i].weight);
        sqEdgeWeight[i].deleted = 0;
#ifdef __MY_HAMILTON_DEBUG__
		printf("edgeNum:%d,node1:%d,node2:%d,weight:%d,deleted:%d\n",
				sqEdgeWeight[i].edgeNum,
				sqEdgeWeight[i].node1,
				sqEdgeWeight[i].node2,
				sqEdgeWeight[i].weight,
    			sqEdgeWeight[i].deleted);
#endif
    }
	return(n);
}    

/*	feature: sort init edge weight sequence, in select sorting algorithm
	param:(none)
	retval:(none)
*/
int SortInitEdgeWeight(void)
{
    int	i, j, k;
    EDGEWEIGHT	tmpEdgeWeight;
    
    for (i=1; i<=szEdge; i++)
    {
        tmpEdgeWeight = sqEdgeWeight[i];
        k = i;
        for (j=i+1; j<=szEdge; j++)
        {
            if (sqEdgeWeight[j].weight<tmpEdgeWeight.weight)
            {
                tmpEdgeWeight = sqEdgeWeight[j];
                k = j;
            }
        }
        if (k != i)
        {
            sqEdgeWeight[k] = sqEdgeWeight[i];
            sqEdgeWeight[i] = tmpEdgeWeight;
        }
    }
#ifdef __MY_HAMILTON_DEBUG__
	printf("in function:%s\n", __func__);
	PrintEdgeWeightInfo();
#endif
}

/*	feature: add edge i of sq to S set,and del from sq
	param: i,the edge i of sq
	retval:(none)
*/
int	AddEdgeToSet(int i)
{
    stEdgeWeight[stIndex] = sqEdgeWeight[i];
    sqEdgeWeight[i].deleted = 1;
    stEdgeWeight[stIndex].deleted = 0;
    stIndex += 1;
    sqIndex = i+1;
#ifdef	__MY_HAMILTON_DEBUG__
	printf("in function:%s\n", __func__);
	printf("sq info:\n");
	PrintEdgeWeightInfo();
	printf("S set info:\n");
	PrintEdgeWeightSetInfo();
#endif
}

/*	feature: check if some vertex's degree is larger than 2
	param:i,the added edge
	retval:1,yes,some vertex's degree is above 2
			0,no,no vertex's degree is above 2
*/
int	IsDegreeAbove2(int i)
{
	int	j;
	int	c;
	
	c = 0;
	for (j=1; j<=i; j++)
	{
     	if ((stEdgeWeight[j].deleted==0) &&
      		((stEdgeWeight[j].node1 == stEdgeWeight[i].node1) ||
     		 (stEdgeWeight[j].node2 == stEdgeWeight[i].node1)))
     		 c += 1;
    }
    if (c > 2)	return(1);

    c = 0;
	for (j=1; j<=i; j++)
	{
     	if ((stEdgeWeight[j].deleted==0) &&
      		((stEdgeWeight[j].node1 == stEdgeWeight[i].node2) ||
     		 (stEdgeWeight[j].node2 == stEdgeWeight[i].node2)))
     		 c += 1;
    }
    if (c > 2)	return(1);
    
    return(0);
}

/*  feature: delete edge i from S set
	param:i,the edge to delete
	retval:(none)
*/
int	DelSetEdge(int i)
{
    stEdgeWeight[i].deleted = 1;
#ifdef	__MY_HAMILTON_DEBUG__
	printf("in function:%s\n", __func__);
	printf("S set info:\n");
	PrintEdgeWeightSetInfo();
#endif
}

/*	feature: count degree of nodes in S set
	param:(none)
	retval:(none)
*/
int	CountDegree(void)
{
    int	i, j, k;
    
    for(i=1; i<=szNode; i++)
    {
        degree[i] = 0;
    }
    
    for (i=1; i<stIndex; i++)
    {
        j = stEdgeWeight[i].node1;
        k = stEdgeWeight[i].node2;
        degree[j] += 1;
        degree[k] += 1;
    }
#ifdef __MY_HAMILTON_DEBUG__
    PrintDegree();
#endif
}

/* feature: check if S set can form a HC
	param:(none)
	retval:1,yes,has a HC
			0,no,no HC
*/
int IsHamiltonCycle(void)
{
    int	i;
    
    CountDegree();
    for (i=1; i<=szNode; i++)
    {
        if (degree[i] != 2)			/* because there's no self-cycle and no-above-3-degree edge,so the judgement is simple */
        	return(0);
   	}
   	return(1);
}

/*   feature: check is S set have local cycle
	param:(none)
	retval:1,yes,has local cycle
			0,no,no local cycle
*/
int	IsLocalCycle(void)
{
    int	i;

    if	(IsHamiltonCycle())	return(0);	/* if is HC,then not local cycle */
    CountDegree();
    for (i=1; i<=szNode; i++)
    {
        if ((degree[i] != 0) || (degree[i] != 2))		/* if has degree which is not 0 or 2,eg,it has degree 1,the surely is not Local cycle */
        	return(0);
   	}
   	return(1);		/* else(not HC && has only two kind degree,0 or 2,then it must be a local cycle */
}

/*	feature: main body of greedy algorithm
	param:(none)
	retval:1,find HC
			0,not find HC
*/
int	GreedySearch(void)
{
    int i, j, k;
    
    for (i=1; i<=szEdge; i++)  	/* STEP 3 */
    {
        AddEdgeToSet(i);
        if (IsDegreeAbove2(i))			/* some vertex's degree larger than 2 */
        {
        	DelSetEdge(i);
        	continue;					/* goto STEP 3 */
       	}else if(IsHamiltonCycle())		/* S contain all vertex,each vertex has 2 degree,and form a cycle */
       	{
       		return(1);					/* find Hamilton cycle,goto STEP 4 */
  		}else if(IsLocalCycle())                 		/* S contain local cycle */
  		{
        	DelSetEdge(i);				/* del edge i from S set */
  		}else
  		{
//        	AddEdgeToSet(i);			/* add edge i to S set,and del it from sq */
//  			if (0)			/* S contain all vertexs,and each's degree is 2,note:here means self-cycle.but in our graph,there's no such problity  */
//  			{
//         		return(0);	/* not exist Hamilton-cycle,goto STEP 5 */
//      		}else
//      		{
//            	return(1);/* find Hamilton-cycle,goto STEP 4 */
//  			}
  		}
    }
    return(0);
}

int	OutputHC(void)
{
    int i, j, k;
    int HC_len = 0;				/* Hamilton-Cycle length */
    
    printf("Hamilton-Cycle path(in edge presentation):\n");
    for(i=1; i<stIndex; i++)
    {
        if(stEdgeWeight[i].deleted == 0)
        {
            printf("%d\t", stEdgeWeight[i].edgeNum);
            HC_len += stEdgeWeight[i].weight;
        }
    }
    
//    j = stEdgeWeight[1].node1;
//    k = stEdgeWeight[1].node2;
//    printf("\nHamilton-Cycle path(in node form):\n");
//    printf("%d", j);
//    while (k != j)
//    {
//        printf(" -> %d ", k);
//        for(i=2; i<stIndex; i++)
//        {
//            if((stEdgeWeight[i].deleted == 0) && (stEdgeWeight[i].node1 == k))
//            {
//                k = stEdgeWeight[i].node2;
//                break;
//            }
//            if((stEdgeWeight[i].deleted == 0) && (stEdgeWeight[i].node2 == k))
//            {
//            	k = stEdgeWeight[i].node1;
//            	break;
//           	}
//        }
//    }
//    printf(" ->%d ", k);

    printf("\nHamilton-Cycle length: %d\n", HC_len);
}
            
int main(void)
{
    szEdge = GetInitEdgeWeight();
    SortInitEdgeWeight();
//    InitEdgeWeightSet();
    if	(GreedySearch())
    {
#ifdef	__MY_HAMILTON_DEBUG__
    	printf("in function:%s\n", __func__);
    	printf("S set info:\n");
    	PrintEdgeWeightSetInfo();
#endif
	}
	OutputHC();
    system("pause");
    return(0);
}