/*本程序通過輸入指定的圖中的節點，然后自動找出該節點的所有祖先節點(不包括父親節點)*/

/*有向歐拉圖的輸入輸出算法程序實現*/
#include<stdio.h>

int node;


int q[20][20];  /*本程序最多處理含20個結點的有向圖*/

char ch[50];   /*字符數組暫存從文件讀入的數據*/
long int pos;   /*記錄文件位置*/
static int point_number=0;  /*圖的結點數*/
static int n=0;   /*表示結點數,將由point_number賦值*/

input_file()
{
   FILE *fp=NULL;

   int i=0,j=0;  /*用于計數的變量,計數均從0開始*/
   int line=0,row=0;
   int n=0;   /*表示結點數,將由point_number賦值*/
   int js1=0,js2=0;

   char s1[50];

   fp=fopen("g:\\yxolt_io\\shuru.txt","r");

     if(fp==NULL)
       {
     printf("can not open file\n");
     getch();
            exit(1);
        }

   /*從文件中讀入圖的結點數*/
   while(point_number==0)
    {
       fscanf(fp,"%c",&ch[i]);

       if(ch[i]==':')
         {
         while(j<i)  /*將 : 之前(即是i之前)的字符讀入字符串s1[]*/
              {
        s1[j]=ch[j];
        j++;
               }

          s1[j]='\0';  /*使字符數組成為字符串*/

          if(strcmp(s1,"points")==0)  /*如果':'之前的字符串是points則讀取:后的數字*/
                 {
            fscanf(fp,"%d",&point_number); /*將':'后的結點數放入point_number*/
                    /*記下當前文件的位置,并退出當前循環*/
                      if((pos=ftell(fp))==-1L)   /*pos記下當前文件位置*/
                          {
                 printf("A file error has occurred!");
                 getch();
                             exit(1);
                            }

                        else
                          {
                           i=0;
                           fclose(fp);
                           break;
                           }
                   }
           }
       i++; /*指向下一個ch[]數組單元*/
     }

  /*由point_number提供的有向圖結點數生成相關數組*/

    n=point_number;

     for(js1=0;js1<=n;js1++)
       for(js2=0;js2<=n;js2++)
        {
           q[js1][js2]=0;
          }   /*初始化相關矩陣*/

 /*從文件上次位置(讀完結點數目)開始讀入文件中的數據*/

    fp=fopen("g:\\yxolt_io\\shuru.txt","r"); /*第二次打開文件*/

     if(fp==NULL)
       {
     printf("can not open file\n");
     getch();
            exit(1);
        }

     fseek(fp,pos,SEEK_SET);  /*將指針指向上次文件中斷的地方*/
     /*經單步調試證明上句已成功執行,將文件指針指向從文件開頭后pos個字節后的位置,
      即是points:6后的位置,此技術在本程序中并無實際意義,但此舉進一步完善了我的文件
      讀寫技術,以供今后使用.*/

     i=0;  /*ch[]從頭開始存放讀入的數據*/

     while(!feof(fp))
        {
           fscanf(fp,"%c",&ch[i]);

           if(ch[i]=='>'&&ch[i-1]=='-')
              {
          row=ch[i-2]-48;  /*行值*/
                 
        /*2004.7.6對本程序維護，使其真正能夠處理20個頂點的有向圖，原先實際只能處理編號<10的有向圖*/

                  if(ch[i-3]>='0'&&ch[i-3]<='9') /*針對頂點編號是兩位數的情況(10.11,12...)
                                                 由于本程序處理上限是20個頂點，故此不考慮頂點
                                                 編號是三位或三位以上的情況。*/
                    { 
                       row=(ch[i-3]-48)*10+row; /*處理頂點編號是兩位數的情況*/
                     }
        /*2004.7.6對本程序維護*/

                  i++; /*指向下一個ch[]存儲單元*/
                  i=check_i(i); /*一旦i>=50就進行隊列管理*/

                 fscanf(fp,"%c",&ch[i]);/*將->后的列值從文件讀入*/
                 line=ch[i]-48;   /*列值*/


       /*2004.7.6對本程序維護，使其真正能夠處理20個頂點的有向圖，原先實際只能處理編號<10的有向圖*/
               i++;
               i=check_i(i); /*一旦i>=50就進行隊列管理*/
               fscanf(fp,"%c",&ch[i]);/*試探性的再讀入一個字符，若該字符是數字，則說明列值是兩位數*/

                if(ch[i]>='0'&&ch[i]<='9')/*計算兩位數的頂點編號*/
                  {
                     line=line*10+(ch[i]-48);
                     }
      /*2004.7.6對本程序維護*/

                     do{
                          i++; /*指向下一個ch[]存儲單元*/
                          i=check_i(i); /*一旦i>=50就進行隊列管理*/

                          fscanf(fp,"%c",&ch[i]); /*讀入兩點間有向邊條數*/
                            if(ch[i]>='0'&&ch[i]<='9')  
                               {
                                    q[row][line]=ch[i]-48;
                                 }

            } while((ch[i]!='\n')&&(!feof(fp)));  /*以讀到該行的結尾為結束,并再讀下一行*/
        }

              i++;   /*指向下一個ch[]存儲單元*/
              i=check_i(i); /*一旦i>=50就進行隊列管理*/

      }

  fclose(fp);
}


check_i(int i)
{
  if(i>=50)    /*一旦i>=50就進行隊列管理*/
    {
      queue_manage();
      i--;
     }

  return i;
}

queue_manage()/*將最早入隊的數據出隊，i減一。50個字符空間相當于存儲有關
                信息的緩沖區，以備后用*/
{
   int j=0;

   for(j=0;j<49;j++)
      ch[j]=ch[j+1];
}

father(int fnode,int G[],int jg)
{
  int i=0;
  int F[21]; /*用來存放fnode 的父親節點,也就是node的祖先節點，應該存入G[]數組中*/
  int jf=0; /*紀錄fnode節點的父親節點的個數*/

  for(i=0;i<=20;i++)
     {
       F[i]=0;
      }

  F[jf]=0; /*F[0]用來記錄父親節點的個數*/
 for(i=1;i<=point_number;i++)
  {
    if(q[i][fnode]==1)
      {
        F[++jf]=i; /*記下一個fnode 的父親節點*/
        G[++jg]=i; /*同時作為node的祖先節點存入G[]*/
        }
    }/*此for循環找出fnode的所有父親節點，并將這些節點作為NODE的祖先節點存入G[]*/

  F[0]=jf; /*F[0]用來記錄父親節點的個數*/
  G[0]=jg;/*G[0]用來記錄node祖先節點的個數*/

 /*通過遞歸找出node節點祖先的祖先，并存入G[]*/
  if(F[0]!=0)
   {
      while(jf!=0)
        {
          if(F[jf]!=0)
            jg=father(F[jf],G,jg);

          jf--;
         }
    }

  return jg;
}


grand() /*找出M[]中的node的祖先節點，并將其從M[]中移出*/
{
  int G[21];/*用來存放node 的祖先節點，用于與M[]數組比較*/
  int jg=0; /*紀錄祖先節點的個數*/
  int i=0;
  int F[21]; /*用來存放node 的父親節點*/
  int jf=0; /*紀錄父親節點的個數*/

  for(i=0;i<=20;i++)
     {
       G[i]=0;
       F[i]=0;

      }

  F[jf]=0; /*F[0]用來記錄父親節點的個數*/
  for(i=1;i<=point_number;i++)
     {
       if(q[i][node]==1)
           {
             F[++jf]=i; /*記下一個node 的父親節點*/
             }
       }/*此for循環找出node的所有父親節點*/
  F[0]=jf; /*F[0]用來記錄父親節點的個數*/

  while(jf!=0)
  {
    if(F[jf]!=0)
     jg=father(F[jf],G,jg);/*通過father()函數以及node node 的父親節點找出node所有祖先節點*/

     jf--;
    }

  /*輸出G[]的內容*/
 if(jg==0)
   {
    printf("\n The node didn't have grand! \n ");
     }

  else
    {
      /*由于可能出現node節點的祖先節點重復出現在G[]中，故此對G[]做一個處理，
       將G[]中重復的節點只保留一個*/
       tidyG(G,jg);

     printf("\n %d's grands are:",node);

      jg=G[0];
      while(jg!=0)
     {
       printf("%4d",G[jg]);
       jg--;
       }

     }/*end else*/

  /*將G[]中出現的node的祖先節點，從M[]中移出*/
 }

tidyG(int G[],int jg)
{
  int temp[21];
  int jt=0;
  int cut=0;
  int i=0,j=0;

  for(i=0;i<=20;i++)
     {
        temp[i]=0;
      }


  jg=G[0];
     while(jg!=0) /*將G[]中的節點加入temp[]，節點不能重復出現在temp[]中*/
       {
         j=jt;
         cut=0;

         if(j>0) /*temp[]不空*/
           {
             while(j!=0)
               {
                 if(temp[j]==G[jg]) /*檢查G[jp]是否與已經進入temp[]的節點重復
                                       若重復，則G[jp]不加入temp[]*/
                    {
                       cut=1;break;
                       }

                  j--;
                 }
             }

         if(cut==0)
           {
              temp[++jt]=G[jg];
             }

         jg--;
       } /*end while*/

     temp[0]=jt;

     for(i=0;i<=temp[0];i++)  /*得到經過整理的G[],其中沒有重復的元素*/
       {
           G[i]=temp[i];
         }
}


main()
{
  clrscr();
  input_file();/*讀入有向圖，建立q[][]鄰接矩陣*/

  printf("\nPlease input the node witch you want to find it's grands(but not include father): ");
  scanf("%d",&node);
  grand();

  getch();
}