//CreatUDN.cpp
//采用鄰接矩陣表示法,構造圖
# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

# define INFINITY 1000
# define MAX_VERTEX_NUM 20
# define OK 1
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int EType;
typedef int InfoType;
typedef int VertexType;

typedef struct ArcCell		//定義 MGraph
{  EType adj;
   InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{  VertexType vexs[MAX_VERTEX_NUM];
   AdjMatrix  arcs;
   int vexnum,arcnum;
   GraphKind kind;
}MGraph;

int LocateVex(MGraph G,int v)	//確定v在G中的位置
{
	return(v);
}

int CreatUDN(MGraph &G)		//CreatUDN() 子函數
{  int i,j,k,v1,v2,w;
   int IncInfo;
   cout<<endl<<"Please input the number of G.vexnum 頂點數目 (eg, 4): ";
   cin>>G.vexnum;			//輸入頂點數目
   cout<<"Please input the number of G.arcnum 弧的數目 (eg, 4): ";
   cin>>G.arcnum;			//輸入弧的數目
   //cout<<"Please input IncInfo 弧的信息 (0 for none)                  : ";
   printf("Please input IncInfo 弧的信息 (0 for none)          : ");
   //cin>>IncInfo;			//輸入弧的信息                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           
   scanf("%d",&IncInfo);
   for(i=1;i<=G.vexnum;++i)
     for(j=1;j<=G.vexnum;++j)
       {  G.arcs[i][j].adj=INFINITY;	//初始化鄰接矩陣
		  G.arcs[i][j].info=NULL;	
       }
   cout<<"Plese input 弧 arc(V1-->V2), For example: arc(1,3),arc(2,4)..."<<endl;
   for(k=0;k<G.arcnum;++k)	//構造鄰接矩陣
   {   cout<<endl<<"Please input the "<<k+1<<"th arc's v1 弧頭 [1.."<<G.vexnum<<"] :";
       cin>>v1;				//輸入弧頭
       cout<<"Please input the "<<k+1<<"th arc's v2 弧尾 [1.."<<G.vexnum<<"] :";
       cin>>v2;				//輸入弧尾
       cout<<"Please input the "<<k+1<<"th arc's weight 權      :";
       cin>>w;				//輸入權
	   i=LocateVex(G,v1);	//確定v1在G中的位置
       j=LocateVex(G,v2);	//確定v2在G中的位置
       while(i<1||i>G.vexnum||j<1||j>G.vexnum)	//如果弧頭或弧尾不合法,重新輸入
       {	cout<<"Please input Again the "<<k+1<<"th arc's v1 弧頭[1.."<<G.vexnum<<"] :";
			cin>>v1;
			cout<<"Please input Again the"<<k+1<<"th arc's v2 弧尾[11.."<<G.vexnum<<"] :";
			cin>>v2;
			cout<<"Please input Again the "<<k+1<<"th arc's weight 權      :";
			cin>>w;
			i=LocateVex(G,v1);	//確定v1在G中的位置
			j=LocateVex(G,v2);	//確定v2在G中的位置	
       } //while end
       G.arcs[i][j].adj=w;			//weight
	   if(IncInfo!=0)
		   {	G.arcs[i][j].info=&IncInfo;
			//printf("%d",*G.arcs[i][j].info);
		}
   } //for end
   return (OK);
} //CreatUDN() end

//int CreateGraph(MGraph &G)
//{  cout<<endl<<"Please input the kind of Graph (DG, DN, UDG, UDN ) : ";
//   cin>>G.kind;
//   switch(G.kind)
//   {  case DG   : return CreatDG(G);
//      case DN   : return CreatD(Gn);
//      case UDG  : return CreatUDG(G);
//      case UDN  : return CreatUDN(G);
//      default   : return (0);
//   }
//}

void ShowMGraph(MGraph G)	//輸出圖 G
{	int i,j;
	for(i=1;i<=G.vexnum;++i)
		for(j=1;j<=G.vexnum;++j)
			if(G.arcs[i][j].adj!=INFINITY)
			{	//cout<<endl<<"arc("<<i<<","<<j<<") weight="<<G.arcs[i][j].adj;
				//cout<<" G.arcs["<<i<<"]["<<j<<"].info=";//<<*G.arcs[i][j].info;
				//printf("%d",*G.arcs[i][j].info);
				printf("\narc(%d,%d) weight=%d  ",i,j,G.arcs[i][j].adj);
				//printf("G.arcs[%d,%d].info=",i,j);//,*G.arcs[i][j].info);
				//printf("%d",G.arcs[i][j].info);
			}
}


void main()			//main() 函數
{   MGraph G;
    cout<<endl<<endl<<"CreatUDN.cpp";
    cout<<endl<<"============"<<endl;
    if(CreatUDN(G))	//調用 CreatUDN()
	{	//cout<<endl<<"Create MGraph success !";	//如果構造圖成功,則輸出圖
		printf("\nCreate MGraph success !");
		ShowMGraph(G);		//顯示構造成功后的圖
	}
	cout<<endl<<endl<<"...OK!...";
    getch();
} //main() end