core.cpp

基于C＋＋的MFC实现的地图着色问题。对于使用文档/视图模型的 MFC 应用程序。

#include "stdafx.h"
#include "core.h"
#include <fstream>
#include <cassert>


void addVertex(Graph& container, int x, int y)
{
	Vertex* v = new Vertex;
	v->x = x;
	v->y = y;
	v->render = VC_BLACK;
	v->id = container.size();
	container.push_back(v);
}


void addArc(Graph& container, int a, int b)
{
	container[a]->arcs.insert(b);
	container[b]->arcs.insert(a);
}

class VertexGreaterThan
{
public:
	bool operator() (const Vertex* a, const Vertex* b)
	{
		return (a->arcs.size() > b->arcs.size());
	}
};
void renderGraph(Graph& container)
{
	// reset graph
	for (unsigned int i=0; i<container.size(); ++i)
	{
		container[i]->render = VC_BLACK;
	}


	Graph graph(container);
	sort(graph.begin(), graph.end(), VertexGreaterThan()); // 降序

	int noRenderYet = graph.size();
	VertexColor color[] = { 
		VC_RED,
		VC_GREEN,
		VC_BLUE,
		VC_YELLOW,
		VC_WHITE
	};
	int colorIndex = 0;

	ofstream ofile("GraphRender.txt");
	for (unsigned int i=0; i<graph.size(); ++i)
	{
		set<int> vertexArcs; // 保存所有被着同一种颜色了的顶点的邻接顶点
		// render the vertex i, and its not neiborght
		if (VC_BLACK == graph[i]->render)
		{
			assert(colorIndex < 6 && "colorIndex < 6");
			graph[i]->render = color[colorIndex];
			ofile<<graph[i]->id<<"color"<<colorIndex+1<<':';
			vertexArcs.insert(graph[i]->arcs.begin(), graph[i]->arcs.end());
			//--noRenderYet;
		} else
		{
			continue;
		}

		// search vertex i 's not neiborght
		for (unsigned int j=0; j<container.size(); ++j)
		{
			// find j is vertex i 's not neiborght, and they must not render yet
			if (vertexArcs.find(j) == vertexArcs.end() && VC_BLACK == container[j]->render)
			{
				assert(colorIndex < 6 && "colorIndex < 6");
				container[j]->render = color[colorIndex];
				ofile<<j<<' ';
				vertexArcs.insert(container[j]->arcs.begin(), container[j]->arcs.end());
				//--noRenderYet;
			}
		}

		++colorIndex;
		ofile<<"\r\n";
	}
	ofile.close();
}


void releaseVertex(Graph& container)
{
	for (unsigned int i=0; i<container.size(); ++i)
	{
		Vertex* v = container[i];
		if (v) { delete v; v=0; }
	}

	container.clear();
}