地图着色问题

问题：地图着色问题

问题简介：将一个图分成几部分，使得对于每一个部分，其中的节点互相不连接。

问题理解：这种问题往往有多种划分方式，即有多个解。可以采用贪心法找到其中的某一个解，或者使用回溯法遍历所有的可能解。

设计与实现

• 程序实现的数据结构：图（用于存储节点之间的网状关系），集合（用于存储划分中的每个部分），由集合构成的顺序表（用于存储划分），字符串，字符串构成的顺序表（用于存储节点的名字）。

• 各数据结构的UML图：

classDiagram
    class string{
        -char* str
        +fprint(FILE*) Void
        +operator=(char*) Void
        +operator==(string) Bool
    }
    class graph{
        -int nodeCount
        +initgraph() Void
        +islinked(int,int) Bool
    }
    class set{
        -int size
        -bool* setarray
        +add() Void
        +remove() Void
        +isempty() Bool
        +begin() iterator
        +end() iterator
    }
    class iterator{
        <>
            -int pos
            -set* fatherset
            +operator*(): Int
            +operator++()
            +next(): iterator
    }

• 算法：实现了贪心法 及 回溯法。仅上交回溯法的代码。

• 环境：g++ -std=c++11; MacOS，arm64

总结

收获：回顾了计算概论的内容。学习了图在计算机中的存储。复习了c++中类的写法。

问题与解决办法：

• 问题：集合中元素的遍历。由于集合元素的存储方式，元素的存储位置在内存中可能是分立的，给集合的遍历带来困难。
• 查阅资料，实现了一个集合的迭代器，封装了集合的遍历过程。

不足：搜索效率不高。

输入输出：

输入为filei.txt，包含：

一个整数N，代表节点个数；N个字符串，代表每个节点的名字；一个N * N的矩阵，每个数是0或1。a[i][j]=1代表节点i和j相连。

输出为fileo.txt，包含：

所有可能的分划，以及可能的分划总数，以及最少的分划数。

源码

/* 地图着色问题 */
#include <cstdio>
using namespace std;
#define MAXLEN 20

class string{
	/* 类定义：字符串 */
private:
	/* 存储结构：顺序存储 */
	char str[MAXLEN] = "";
public:
	void print(){
		/* 操作：打印字符串 */
		printf("%s ",str);
	}
	void fprint(FILE *fp){
		/* 操作：打印字符串 */
		fprintf(fp,"%s ",str);
	}
	void operator=(const char s[]){
		/* 操作：字符串赋值 */
		int i=0;
		for (; i < s[i]!='\0' && i<MAXLEN ; ++i)
		{
			str[i] = s[i];
		}
		str[i]='\0';
	}
	bool operator==(const string s){
		/* 操作：字符串比较是否相等 */
		for (int i = 0; i < MAXLEN; ++i)
		{
			if(str[i]!=s.str[i])return false;
		}
		return true;
	}
	bool operator==(const char s[]){
		string ts;ts = s;
		return *this==ts;
	}
};

class graph{
	/* 类定义：图 */
private:
	/* 存储结构：顺序存储 */
	/* 逻辑关系：网状结构 */
	int grapharr[MAXLEN][MAXLEN]={0};
	int n=0;
public:
	/* 构造函数，填入图的节点数 */
	graph(int nn){n=nn;}
	void initgraph(){
		/* 初始化函数，读入图的数据 */
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				scanf("%d",&grapharr[i][j]);
			}
		}
	}
	void initgraph(FILE *fp){
		/* 初始化函数，读入图的数据 */
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				fscanf(fp,"%d",&grapharr[i][j]);
			}
		}
	}
	/* 操作：判断两个节点是否连接上 */
	bool islinked(int a,int b){return grapharr[a][b];}
};

class set{
	/* 类定义：集合 */
private:
	/* 逻辑关系：集合；但是在内部实现时，利用了元素的线性结构 */
	/* 存储结构：顺序存储 */
	int size = 0;
	bool setarray[MAXLEN] = {0};
public:
	void add(int i){
		/* 操作：添加元素 */
		if(i>=0 && i<MAXLEN && not isexist(i)){
			setarray[i] = true;
			size++;
		}
	}
	void remove(int i){
		/* 操作：删除元素 */
		if(isexist(i)){
			setarray[i] = false;
			size--;
		}
	}
	bool isempty(){return !size;}/* 判断集合是否为空 */
	bool isexist(int i){
		/* 判断元素是否存在 */
		return i>=0 && i<MAXLEN && setarray[i];
	}

	class iterator{
		/* 类定义：集合的迭代器，用于遍历集合的所有元素 */
		int pos=0;
		set* fatherset = nullptr;
	public:
		iterator(set* ptr,int n){
			/* 构造函数：给定一个指定位置 */
			pos = n-1;
			fatherset = ptr;
			(*this)++;
		}
		iterator(set* ptr){
			/* 构造函数：定在初始位置 */
			pos = -1;
			fatherset = ptr;
			(*this)++;
		}
		void operator++(){
			/* 操作：自增 */
			pos++;
			if(pos>=MAXLEN)return;
			while(fatherset->setarray[pos]==0){
				pos++;
				if(pos>=MAXLEN)return;
			}
		}
		void operator++(int k){
			/* 操作：自增 */
			pos++;
			if(pos>=MAXLEN)return;
			while(fatherset->setarray[pos]==0){
				pos++;
				if(pos>=MAXLEN)return;
			}
		}
		int operator*()const{
			/* 操作：取值 */
			return pos;
		}
		int operator!=(const iterator& it){
			/* 运算：是否不等 */
			return it.pos!=pos;
		}
		int operator==(const iterator& it){
			/* 运算：是否相等 */
			return it.pos==pos;
		}
		iterator next(){
			return iterator(fatherset,pos+1);
		}
	};
	iterator begin(){
		/* 操作：得到一个指向首个元素的迭代器 */
		return iterator(this);
	}
	iterator begin(int i){
		/* 操作：得到一个指向首个元素的迭代器 */
		return iterator(this);
	}
	iterator end(){
		/* 操作：得到一个指向末尾的迭代器 */
		return iterator(this,MAXLEN);
	}
};

bool isunrelated(set targetset,graph g,int node){
	/* 判断图 g 上的 node 节点是否与 targetset 里面的所有节点都不相连 */
	for (auto i = targetset.begin();i!=targetset.end();i++)
	{
		if(g.islinked(*i, node)){return false;}
	}
	return true;
}

void printtempset(set tset,string i2s[MAXLEN]){
	/* 将tset里面的元素对应的string全部打印。元素和字符串的对应关系存储在i2s[]中 */
	for (auto i = tset.begin();i!=tset.end();i++)
	{
		i2s[*i].print();
	}
	printf("\n");
}

void fprinttempset(FILE *fp,set tset,string i2s[MAXLEN]){
	/* 将tset里面的元素对应的string全部打印。元素和字符串的对应关系存储在i2s[]中 */
	for (auto i = tset.begin();i!=tset.end();i++)
	{
		i2s[*i].fprint(fp);
	}
	fprintf(fp,"\n");
}

/* 节点数 */
int N=0;
/* 用一个顺序表存储所有数字元素对应的节点名称 */
string indexToString[MAXLEN];
graph *mygraph;
set leftset;
set groupsets[20];


int loaddatafromfile(char fpath[]){
	FILE *fp;
	fp = fopen(fpath,"r");
	if(fp==NULL){return -1;}
	/* 录入节点数 */
	fscanf(fp,"%d",&N);
	/* 录入所有名称 */
	for (int i = 0; i < N; ++i)
	{
		char ts[MAXLEN]="";
		fscanf(fp,"%s",ts);
		indexToString[i] = ts;
	}
	/* 实例化、初始化图 */
	mygraph = new graph(N);
	mygraph->initgraph(fp);
	
	fclose(fp);
	return 0;
}

bool check(){
	for (int i = 0; i < 4; i++)
	{
		for (auto j = groupsets[i].begin(); j != groupsets[i].end(); j++)
		{
			if(not isunrelated(groupsets[i],*mygraph,*j)){
				return false;
			}
		}
		
	}
	return true;
	
}

int count = 0;
int shortestgroupnum = MAXLEN;

int search(FILE *fp,int currentgroupnum, set::iterator currentanalyzenode){
	/* fp:写入结果的文件指针，currentgroupnum：目前有的分划数，
	currentanalyzenode：目前要处理的节点 */
	if(currentgroupnum>4){
		return 0;
	}
	if(currentanalyzenode == leftset.end()){
		/* 完成了一次分划，输出分划结果 */
		if(currentgroupnum < shortestgroupnum){
			shortestgroupnum = currentgroupnum;
		}
		count++;
		fprintf(fp,"第%d个结果:\n",count);
		for (int i = 0; i < currentgroupnum; i++)
		{
			fprinttempset(fp,groupsets[i],indexToString);
		}
		fprintf(fp,"校验结果：%s\n",check()?"正确":"错误");
		fprintf(fp,"\n");

		return 0;
	}

	/* 带回溯的将当前节点放置到所有可能的分划中，包括已有的分划和放入一个新分划 */
	set::iterator i = currentanalyzenode;
	for(int j=0;j<currentgroupnum;j++){
		if(isunrelated(groupsets[j],*mygraph , *i)){
			groupsets[j].add(*i);
			leftset.remove(*i);
			/* 放入已有的分划，向下搜索 */
			search(fp,currentgroupnum,i.next());
			/* 回溯 */
			groupsets[j].remove(*i);
			leftset.add(*i);
		}
	}
	groupsets[currentgroupnum].add(*i);
	leftset.remove(*i);
	/* 放入一个新分划，向下搜索 */
	search(fp,currentgroupnum+1,i.next());
	/* 回溯 */
	groupsets[currentgroupnum].remove(*i);
	leftset.add(*i);

	return 0;
}

int mymain(){
	/* 实例化、初始化集合 */
	for (int i = 0; i < N; ++i)
	{
		leftset.add(i);
	}

	FILE *fp = fopen("fileo.txt","w");
	if(fp==NULL)return -2;
	/* 搜索 */
	search(fp,0,leftset.begin());
	/* 结果 */
	fprintf(fp,"搜索完成，共%d个结果\n", count);
	fprintf(fp,"最少分划个数为：%d", shortestgroupnum);

	fclose(fp);

	return 0;
}

int main(){
	char path[] = "filei.txt";
	if(loaddatafromfile(path))return -1;
	return mymain();
}