match.cpp

对图进行匹配的算法

// match.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "node.h"
#include "graph.h"
#include "stdio.h"
#include "memory.h"

#define MAX 100
#ifndef NULL
#define NULL 0
#endif 
//function
int getmindegree(graph *gh,int vm,int *nf);
void match(graph *gh,int vm);
int getnodedegree(graph *gh,int vm,int i,int *nf);
//
int *lm,*rm;
int main(int argc, char* argv[])
{
	int vm;                    //the number of the vertexs
	FILE *of;                  //the file for reading the graph information
	node *left,*right,*bl,*br;
	node *temp;
	int ln,rn;
	int i;
	graph *gh,*back;
	char str[MAX];
	if((of=fopen(argv[1],"r+"))==NULL)
	{
		printf("failed to open the file!\n");
	    return -1;
	}
	memset(str,0,MAX);
	if((fgets(str,MAX,of))==NULL)
	{
	 printf("end of file!");
	 return 0;
	}
	sscanf(str,"len=%d",&vm);
	memset(str,0,MAX);
	gh=new graph[vm];
    back=new graph[vm];
	lm=new int[vm];
	rm=new int[vm];
	while(fgets(str,MAX,of))
	{
      sscanf(str,"(%d,%d)",&ln,&rn);
	  left=new node(ln);
	  right=new node(rn);
      gh[ln].addnode(right);
	  gh[rn].addnode(left);
	  bl=new node(ln);
	  br=new node(rn);
      back[ln].addnode(br);
	  back[rn].addnode(bl);
	  memset(str,0,MAX);
	}
    for(i=0;i<vm;i++)
	{
	  printf("%d-->",i);
	  temp=gh[i].head->next;
      while(temp!=NULL)
	  {
	  printf("%d-->",temp->number);
	  temp=temp->next;
	  }
	  printf("NULL\n");
	}

	return 0;
}

void match(graph *gh,int vm)
{
int *nf;
int i;
nf=new int[vm];
for(i=0;i<vm;i++)
nf[i]=0;
}

int getmindegree(graph *gh,int vm,int *nf)
{
int min=vm,i,j;
for(i=0;i<vm;i++)
{
if((gh[i].getlength()<min)&&nf[i]!=1)
{
	min=gh[i].getlength();
    j=i;
}
}
return j;
}

int getnodedegree(graph *gh,int vm,int i,int *nf)
{
node *temp;
int min=vm;
int n=-1;
while((temp=gh[i].getnext())!=NULL)
{
    if(gh[temp->number].getlength()<min&&nf[temp->number]!=1)
	{
	  n=temp->number;
	}
}
return n;
}