/*创建头文件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__ */

/* cpp文件*/
  /*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);
}