graph2.h

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

#ifndef __GRAPH2_H
#define __GRAPH2_H


#if !defined(__TOOLS_H)
#include"tools.h"
#endif

#define  rdx 9
#define rdy    9
#define max_node_num  20
#define   upv 86
#define   lowv 118
#define    upe 69
#define   lowe 101
#define    upc 67
#define    lowc 99
#define    upm  77
#define   lowm 109

#ifndef ddarr
#define ddarr

  class Vararray
{private:
    int  *element;
    int size;
    int min;
    int max;
  public:
   Vararray( int m=0,int s=0);
   Vararray();
   int&  operator [](const int index);
   ~Vararray(){ delete []element; }
   };

   Vararray::Vararray(int m,int s)
   {
	size=s-m+1;
	max=s;
	min=m;
	element=new int[size];
	for(int i=0;i<size;i++)
	element[i]=0;
	}

    int & Vararray::operator[](const int index)
     {  return element[index-min];
     }




  class BB2
  {
   public:
     unsigned int numberofrow;
     unsigned int numberofcol;
     unsigned int rowstart;
     unsigned int colstart;
     Vararray array;
     BB2(unsigned int,unsigned int,unsigned int,unsigned int);
     int& select(unsigned int,unsigned int);
     class Row
     {
     public:
       BB2& array2D;
       unsigned int const row;
       Row(BB2& _array2D,unsigned int _row):
       array2D(_array2D),row(_row){}
       int& operator[](unsigned int column)const
	   {return array2D.select (row,column);}
      };

      Row operator[](unsigned int);
      };

      BB2::BB2(unsigned int m=0,unsigned int n=30,
		       unsigned int k=0,unsigned l=30):

      numberofrow(n-m+1),
      numberofcol(l-k+1),
      rowstart(m),
      colstart(k),
      array(0,(n-m+1)*(l-k+1) ){}

      int& BB2::select(unsigned int i,unsigned int j)
      {
      if(i>=rowstart+numberofrow||i<rowstart)
	 {
	 Error("invalid row");
	 exit(0);
	 }
      if(j>=colstart+numberofcol||j<colstart)
	 {
	 Error("invalid column");
	 exit(0);
	 }
      return array[(i-rowstart)*numberofcol+j-colstart+1];
      }

      BB2::Row BB2::operator[](unsigned int row)
      {return Row(*this,row);
      }

#endif





     class   adjnode
	  {
	  public:
	  int weight;
	  int  nodenum;
	   adjnode far * nextadj;
	   adjnode(){};
	   ~adjnode(){};
	   };
  typedef adjnode far * adjlink;

   struct adjhead
	 {

	   int nodenum;
	   adjlink firstadj;
	   adjhead far *nexthead;
	   int x;
	   int y;
	 } ;
   typedef adjhead far * adjhlink;

   class  datagraph
      {public:
      int  nodes;
       adjhlink  firsthead;
       boolean  haveweight,direct;
       datagraph(){firsthead=nil;}
       ~datagraph();
       };

     datagraph::~datagraph()
     {adjhlink p=nil,q=nil;
      adjlink l,m;
      p=firsthead;
      while(p!=nil)
      {
       q=p->nexthead;

	l=p->firstadj;
	while(l!=nil)
	{
	  m=l->nextadj;
	  delete l;
	  l=m;
	}
	delete p;
	p=q;
     }

   }

   class gnodeptr
     {
     public:
      string ptrname;
      adjhlink ptr;
      gnodeptr far *next;
      int x,y,num;
      void far *fdd0;
      gnodeptr(){next=nil;fdd0=nil; }
      ~gnodeptr();
    };

     gnodeptr::~gnodeptr()
     {if(fdd0!=nil)
	farfree(fdd0);
     }



   typedef gnodeptr far * gptrlink  ;



  void  two_point_angle(int x1,int y1,int x2,int y2,int& sa);
  void  get_arc_cord(int x1,int y1,int sa,int& sx,int& sy,int& ex,int& ey);
  void  weight_cord(int mx,int my,int sa,int& wx,int& wy);
  void join1(float x,float y,float x1,float y1,int&  nx,int& ny);
  void join_single_edge(adjhlink h1,adjhlink h2,int& sx,int& sy,int& ex,int& ey,int& wx,int& wy);
  void join_double_edge(adjhlink h1,adjhlink h2,int&  sx,int& sy,int& ex,int& ey,int& wx,int& wy);
  void initial_graph();
  void setnull_graph(datagraph& g,boolean isweight,boolean isdirect);
  void fifild(adjhlink& t,int orxor);
  void cur_cover(adjhlink& t,int orxor);
  void cur_cover_node(datagraph& g,int v,int orxor);
  void disnodedat(adjhlink& t);
  boolean   un_cover_nodes(datagraph& g,int x0,int y0);
  adjhlink  get_ver_head(datagraph& g,int v);
  adjlink  firstadjp(datagraph& g ,int v);
  adjlink  nextadjp(datagraph& g ,int v ,adjlink adj);
  int    firstadj(datagraph& g ,int v);
  int    nextadj(datagraph& g ,int v,int w);
  int   nodes(datagraph& g );
  boolean   is_digraph(datagraph& g );
  boolean   have_weight(datagraph& g );
  void print_graph(datagraph& g );
  void insert_vertex(datagraph& g ,int num,int cx,int cy);
  void insert_edge(datagraph& g ,int v1,int v2);
  void insert_edge_weight(datagraph& g ,int v1,int v2,int w);
  boolean   have_edge(datagraph& g ,int v1,int v2);
  void join(datagraph& g ,adjhlink h1,adjhlink hl,int&  sx,int& sy,int& ex,
		       int& ey,int& wx,int& wy);
  void display_edge(datagraph& g ,int& v1,int& v2);
  void display_all_edge(datagraph& g );
  void display_vertex(adjhlink& h);
  void display_all_vertex(datagraph& g );
  void copy_all_vertex(datagraph& g, datagraph& g1,int dx,int dy);
  void display_graph(string s,datagraph& g );
  void create_graph(datagraph& g );
  void edit_graph(datagraph& g );
  int  edge_weight(datagraph& g ,int v1,int v2);
  void copy_edge(datagraph& g ,int v1,int v2,datagraph& g1);
  void copy_all_edge(datagraph& g ,datagraph& g1);
  void save_graph_file(datagraph& g ,string ss);
  void save_graph(datagraph& g );
  void load_graph_file(datagraph& g ,string ss);
  void load_graph(datagraph& g );

  void move_graph_dxy(string s,datagraph& g ,int dx,int dy);
  void move_graph_to(string s,datagraph& g ,int x,int y);
  void move_graph(string s,datagraph& g );
  void move1_graph(string s,datagraph& g );
  void set_graph_range(datagraph& g );
  void cur_gnode_onoff(datagraph& g ,int gnode);
  void write_atgnode_angle(datagraph& g ,int v,int an,string ss);
  void writestr_atgnode_angle(datagraph& g ,int v,int an,string ss);
  void writeint_atgnode_angle(datagraph& g ,int v,int an,int ii);
  void writeint_gnode(datagraph& g ,int v,int ld,int xe);
  void dispstr_atgnode_angle(string ss, datagraph& g ,int v,int an);
  void dispint_atgnode_angle(int ii,datagraph& g ,int v,int an);
  void graph_range(datagraph& g ,int& xl,int& yl,int& xr,int& yr);
  void clear_graph_range(datagraph& g );
  boolean   graph_cover_node(datagraph& g ,int gnode);
  void create_gptr(gptrlink& sptr,string title);
  void gptr_point_to(gptrlink& sptr, datagraph& g ,int v);
  void disp_gptr_atgnode(gptrlink& sptr,datagraph& g, int v);
  boolean   have_gptr(string title);
  void append_graph(datagraph& g );
  void modify_graph(datagraph& g );
  void modify_weight(datagraph& g ,int v1,int v2,int www);
  void put_edge_weight(datagraph& g ,int v1,int v2,int w);
  void modify_edges_weight(datagraph& g );
  void move_vertex_to(datagraph& g ,int v,int x,int y,boolean checkcover);
  void modify_vertex_card(datagraph& g );
  void disp_graph(string s,datagraph& g );
  void handle_graph_event(pmenunode& pmenu, datagraph& g );
  void handle_graph_menu( mymenu& graphmenu1, boolean& selectorno,
			      pmenunode&  pmenu, datagraph& g );

  void handle_graph(datagraph& g );
  void get_graph(datagraph& g );
  void visite_gnode(datagraph& g ,int  v,int i);
  void set_vgnode_mode();
  void reset_vgnode_mode(int i);
  void comput_graph_in(datagraph& g ,int  xl,int yl,int xr,int yr);
  void comput_graph(datagraph& g );
  void trans_arrbb2_graph(BB2& a,int  n,datagraph& g );
  void trans_AnyArr2_graph(BB2&  a,int i01,int i02,
		     int j01,int j02,int n,datagraph& g );

  // {test for graph menu}
const int  comgrcreategraph=401;
const int  commodigraph=402;
const int  comreadgraph=403;
const int  comsavegraph=404;
const int  comsetrange=405;
const int  comdisp=406;
const int  commove1=407;
const int  commove2=408;
 mymenu graphmenu1,vstmenu2;


#ifndef constvar
#define constvar
const int startrow=30;
const int keystep=5;
const int bigstep=40;
const int step=5;
const int dirnum=6;
const int mvstep=5;
const int sd=4;
const int d=0;
const int m=2;
typedef int move[dirnum][3];
const move mv={{0,-1,  up },{0,1,down},
		      {-1,0,left},{1,0,right},
		      {-4,0,bigleft},{4,0,bigright}};

#endif


gptrlink frstgptr=NULL;
datagraph g;
int gnum=0, num=0, vstno=0;
#ifndef glovar
#define glovar
int key=0;
unsigned char  st[10]="";
#endif

typedef void far * ffield1;
ffield1    nilnd=nil, datafild=nil, vn=nil, curblk=nil, cursor=nil, fdd1=nil, fdd2=nil, fdd3=nil, fdd4=nil;//ffield



#define  ComWriteData 801
#define  ComNotWriteData 802
#define    ComUseCurMove 803
#define    ComUseCurKeep 804
#define    ComNotUseCur 805
#define    ComWaitKey 806
#define    ComDelay  807
#define    ComNotPause 808
#define   ComUsePtr 809
#define    ComNotUsePtr 810
#define    ComNeedNo 811
#define    ComNotNeedNo 812
#define   ComSelectModeNo 813
#define   NumOfVstMode=3
 struct visitemode
	 {    boolean ifwrite,
	      ifcurcovermove, ifcurcoverkeep,
	      ifwaitkey, ifdelay, ifuseptr,
	      ifusenum,  ifdispnum;
	      int delaytime,num,numangle;
	      gptrlink ptr;
	      unsigned char  ptrname[15];
    };

const visitemode  onevisitemode={true,true,false,true,false,true,true,true, 0,0,270,nil,""};
typedef visitemode vstmdarr[4];

vstmdarr    visitegraphmodes;

//   {  Array2  ====>  graph  }
    void comput_graph_in(datagraph& g ,int xl,int yl,int xr,int yr)
     {int i,j,r,x0,y0;
       char ch;
       adjhlink h; float jl;
	     x0=(xl+xr)/2;
	     y0=(yl+yr)/2;
	    jl=2*3.1415/nodes(g);
	     r=Max(Min((xr-xl)/3,(yr-yl)/3),Round(3*rdx/sin(jl/2)));
	  for (j=1;j<=nodes(g);j++)
		{ h=get_ver_head(g,j);
		 h->x=x0+Round(r*cos(jl*j));
		 h->y=y0+Round(r*sin(jl*j));
		 }
   }
    void move_vertex_to(datagraph& g ,int  v,int x,int y,boolean  checkcover)
     {
     adjhlink  h,h1; int i,xt,yt;boolean  cover;
	     h=get_ver_head(g,v);
	   if(!checkcover)
		   { h->x=x; h->y=y;}
	   else    {  xt=h->x;
		      yt=h->y;  cover=false;
		      h->x=-30;
		      h->y=-30;
		      for( i=1 ;i<=nodes(g);i++)
			   {h1=get_ver_head(g,i);
			   if ((abs(h->x-x)<3*rdx)&&(abs(h->y-y)<3*rdy))
				   cover=true;
			     }
		      if (!cover)
			     {  h->x=x; h->y=y;}
			else {  h->x=xt; h->y=yt;
				 Convs(v,st);
				cout<< "顶点"<<st<<"与其它顶点相互覆盖"<<endl;// error('顶点'+convs(v)+'与其它顶点相互覆盖')
			     }
		   }
     }
    void comput_graph(datagraph& g )
      {int  xl,yl;
	   xl=getmaxx()/4;  yl=getmaxy()/4;
	     comput_graph_in(g,xl,yl,3*xl,3*yl);
      }

    void trans_arrbb2_graph(BB2& a,int n,datagraph& g )
     {int i,j,xl,yl; adjhlink h; boolean db,wb;
	  g.nodes=0;
	  g.firsthead=new adjhead;
	  g.firsthead->nexthead=nil;
	  g.firsthead->nodenum=0;
	  db=false; wb=false;
	  for (i=1;i<=n;i++)
	    for (j=1;j<=i;j++)
	      {  if( a[i][j]!=a[j][i] )
		       db=true;
		     if ((a[i][j]>1)||(a[j][i]>1))  wb=true;
	      }
	  g.direct=db; g.haveweight=wb;
	  for (i=1;i<=n;i++)
	    insert_vertex(g,i,0,0);
	  for (i=1;i<=n;i++)
	    for (j=1;j<=n;j++)
	      if (a[i][j]!=0)
		    insert_edge_weight(g,i,j,a[i][j]);
	    xl=639/4;
	    yl=479/4;
	    comput_graph_in(g,xl,yl,3*xl,3*yl);

	   display_graph("hhhh",g);

       }

   /* void trans_anyarr2_graph(BB2& a,int i01,int i02,int j01,int j02,int n, datagraph& g )
      {     int i,j,xl,yl;
	    adjhlink h;
	    boolean db,wb;
	    g.nodes=0;
	    g.firsthead=new adjhead;
	    g.firsthead->nexthead=nil;
	    g.firsthead->nodenum=0;
	    db=false; wb=false;
	  for (i=1;i<=n;i++)
	    for (j=1;j<=i;j++)
	      {  if( a[i][j]!=a[j][i] )
		       db=true;
		     if ((a[i][j]>1)||(a[j][i]>1))  wb=true;
	      }
	  g.direct=db; g.haveweight=wb;
	  for (i=1;i<=n;i++)
	    insert_vertex(g,i,0,0);
	  for (i=1;i<=n;i++)
	    for (j=1;j<=n;j++)
	      if (a[i][j]!=0)
		    insert_edge_weight(g,i,j,a[i][j]);

	    xl=getmaxx()/4;
	    yl=getmaxy()/4;
	    comput_graph_in(g,xl,yl,3*xl,3*yl);

	   display_graph("hhhh",g);

       } */
// {  visite node  }
  void initial_visitemode(vstmdarr&  visitemodes)
   { int  i;
     unsigned char ss[10]="";
	for (i=0;i<=3;i++)
	{
	    Convs(i,ss);
	    strcpy(visitemodes[i].ptrname,"V");
	    strcat(visitemodes[i].ptrname,ss);
	      if (visitemodes[i].ifuseptr&&(!have_gptr(visitemodes[i].ptrname) ) )
		  create_gptr(visitemodes[i].ptr,visitemodes[i].ptrname);
		   visitemodes[i].ptr->x=-1;
		   visitemodes[i].ptr->y=-1;
		   visitemodes[i].ptr->ptr=nil;


	       if (visitemodes[i].ifusenum)
		  visitemodes[i].num=0;
	 }
   }
  void reset_vgnode_mode(int i)
   { if (visitegraphmodes[i].ifuseptr)
	 gptr_point_to(visitegraphmodes[i].ptr,g,0);
	 visitegraphmodes[i].num=0;
      }

  void visite_gnode(datagraph& g ,int v,int i)
    {

     unsigned char ss[100]="访问模式",s1[100]="",s[10]="";
     Convs(i,s);
     strcat(ss,s);
     strcat(ss," 访问元素方式:");
     if(v>=1&&v<=nodes(g) )
	{
	if (visitegraphmodes[i].ifwrite)
			strcpy(s1," 打印元素");
	if (visitegraphmodes[i].ifcurcovermove||visitegraphmodes[i].ifcurcoverkeep)
			strcat(s1," 显示光标");
	if (visitegraphmodes[i].ifuseptr)
		     strcat(s1," 用指示器");
	if (visitegraphmodes[i].ifusenum)
			   strcat(s1," 显示序号");
	if (visitegraphmodes[i].ifwaitkey)
			  strcat(s1," 按键继续");
	      else if(visitegraphmodes[i].ifdelay)
		    { strcat(s1," delay ");
		      Convs(visitegraphmodes[i].delaytime,s);
		      strcat(s1,s);
		      strcat(s1," ms to cont.");
		     }
	strcat(ss," by");
	strcat(ss,s1);
	Menu(ss);