ck_conty.cpp

ck_conty为判断图的连通性的matlab mex文件

/*先运行m -setup，然后运行m H1.cpp编译，即可按普通mfile一样使用;flag=H1(邻接矩阵)，flag=1表示连通，0表示不连通*/
#include"mex.h"
#include"matrix.h"
#define MAX_SIZE 5
#define NUM_EDGE 5
#include "stdio.h"
#include "malloc.h"
#include "process.h"
bool visited[MAX_SIZE];
typedef struct ArcNode
{//表结点结构类型
	int adjvex;                          //该弧(边)的终点位置
   	struct ArcNode *nextarc;    //指向下一条弧的指针
   	double weight;   	        //该弧的相关信息
}ArcNode,*ArcPtr;
typedef struct Vnode 
{//头结点的类型
	struct ArcNode *firstarc;           //指向第一条弧
}Vnode;
typedef struct ALGraph
{//邻接表
	struct Vnode vertices[MAX_SIZE];             	
	int vexnum,arcnum;		//图中顶点数n和边数e
}ALGraph;

bool Calculate(double **arcs,int n)
{
	void MatToList(double** ,ALGraph* );
	bool DFSTraverse(ALGraph ,int );
    bool flag;
	ALGraph *G;
	G=(ALGraph *)malloc(sizeof(ALGraph));
	MatToList(arcs,G);
	G->vexnum=MAX_SIZE;
	G->arcnum=NUM_EDGE;
	flag=DFSTraverse(*G,n);
    printf("====%d",flag);
    return flag;
}

void MatToList(double **g,ALGraph *G )
/*将邻接矩阵g转换成邻接表G;*/
{    
	int i,j;
	int n=MAX_SIZE;
	ArcNode *p; 	/*n为顶点数*/
	for (i=0;i<n;i++)  /*给所有头结点的指针域置初值*/
		G->vertices[i].firstarc=NULL;
	for (i=0;i<n;i++)	/*检查邻接矩阵中每个元素*/
	{
		for (j=n-1;j>=0;j--)
		{
			if (g[i][j]!=0) 
			{ 
				p=(ArcNode *)malloc(sizeof(ArcNode)); /*创建结点*p*/
				p->adjvex=j;
				p->weight=g[i][j];
				p->nextarc=G->vertices[i].firstarc;/*将*p链到链表上*/
				G->vertices[i].firstarc=p;
			}
		}
	}
}
bool DFSTraverse(ALGraph G ,int k)
{
	int v=0,u;
    bool flag;
	void DFS(ALGraph , int );
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
    {
        if (!visited[k])
		{
			DFS(G,k);
			k++;
			k/=MAX_SIZE;
		}
        if(v==0)
        {
            for(u=0;u<G.vexnum;u++)
            {
                if(visited[u]==0)
                    break;
            }
            if(u==G.vexnum)
                flag=1;
            else flag=0;
        }
    }
    return flag;
}

void DFS(ALGraph G ,int v )
{
	struct ArcNode *p;
	visited[v]=1;
	printf("%d  ",v);
	p=G.vertices[v].firstarc;
	while(p!=NULL)
	{
		if(visited[p->adjvex]==0)
			DFS(G,p->adjvex);
		p=p->nextarc;
	}
}

double** fMarray_to_Carray2(mxArray* Ma)
{
    int i,j,k,m,n;double** Ca;
    m=mxGetM(Ma);n=mxGetN(Ma);
    Ca=new double*[m];
    for(i=0;i<m;i++)
        Ca[i]=new double[n];
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            k=j*m+i;
            Ca[i][j]=*(mxGetPr(Ma)+k);
        }
    }
    return Ca;
}
    
void mexFunction(int nlhs,mxArray *plhs[],int nrhs,mxArray *prhs[])
{
    double **data;
    bool flag;
    data=fMarray_to_Carray2(prhs[0]);
    flag=Calculate(data,2);
    plhs[0]=mxCreateDoubleMatrix(1,1,mxREAL);
    *(mxGetPr(plhs[0]))=flag;
}