graph.cpp

实现了图的搜索算法

#include "stdafx.h"
#include "GraphSearch.h"

#include "math.h"
#include "graph.h"

Graph::Graph()
{
	m_nVertexNum = 0;
	m_nEdgeNum = 0;
}

void Graph::drawArrow(CDC* pdc, int* coor1, int* coor2, COLORREF color, int edgeW)
{
	//绘制从坐标coor1->坐标coor2的箭头
	CPen* oldpen = pdc->GetCurrentPen();
	CBrush* oldbrush = pdc->GetCurrentBrush();

	CPen epen(PS_SOLID, edgeW, color);
	pdc->SelectObject(&epen);

	float v[2] = {(float)(coor2[0]-coor1[0]), (float)(coor2[1]-coor1[1])};//计算矢量
	float d = sqrt(pow(v[0], 2)+pow(v[1], 2));//计算两点之间的距离
	float tan0, cos0, sin0;
	if(v[0] == 0 && v[1]>0){
		//0 = 90;
		cos0 = 0.0f;
		sin0 = 1.0f;
	}else if(v[0] == 0 && v[1]<0){
		//0 = -90;
		cos0 = 0.0f;
		sin0 = -1.0f;
	}else{
		tan0 = v[1]/v[0];
		cos0 = sqrt(1/(1+pow(tan0, 2)));
		sin0 = sqrt(1-pow(cos0, 2));
		if(v[0]<0){
			cos0 = -cos0;
		}
		if(v[1]<0){
			sin0 = - sin0;
		}
	}

	int jt1[2] = {int(d-10), 3};
	int jt2[2] = {int(d-10), -3};
	
	int jt_1[2] = {
		coor1[0]+int(jt1[0]*cos0-jt1[1]*sin0),
		coor1[1]+int(jt1[0]*sin0+jt1[1]*cos0)
	};

	int jt_2[2] = {
		coor1[0]+int(jt2[0]*cos0-jt2[1]*sin0),
		coor1[1]+int(jt2[0]*sin0+jt2[1]*cos0)
	};

	pdc->MoveTo(coor1[0], coor1[1]);
	pdc->LineTo(coor2[0], coor2[1]);
	pdc->MoveTo(coor2[0], coor2[1]);
	pdc->LineTo(jt_1[0], jt_1[1]);
	pdc->MoveTo(coor2[0], coor2[1]);
	pdc->LineTo(jt_2[0], jt_2[1]);

	pdc->SelectObject(oldpen);
	pdc->SelectObject(oldbrush);
}

void Graph::display(CDC* pdc, int left, int top, int width, int height, int row, int column, 
					COLORREF colorV, COLORREF colorE, int edgeW, int mode)
{
	//@para mode:图的显示模式,标志是否显示节点信息以及边的信息
	//@para colorV:节点的颜色
	//@para colorE:边的颜色
	//@para edgeW:边的宽度
	VerNode *pv, *pv1, *pv2;
	EdgeNode *pe;

	CPen vpen(PS_SOLID, 1, colorV);
	CPen epen(PS_SOLID, edgeW, colorE);
	CBrush vbrush(colorV);	
	int alignPos = pdc->GetTextAlign();
	pdc->SetTextAlign(TA_CENTER);

	int x, y, coor1[2], coor2[2];
	CString str;
	//绘制图的边
	for(int i = 0; i<m_vertexs.size(); i++){
		pv = (VerNode*)m_vertexs[i];
		pdc->SelectObject(&epen);
		for(int j = 0; j<pv->m_edgeOut.size(); j++){
			pe = (EdgeNode*)pv->m_edgeOut[j];
			pv1 = pe->m_pVerFrom;
			pv2 = pe->m_pVerTo;

			coor1[0] = left+pv1->m_nCoor[1]*width/(column-1);
			coor1[1] = top+pv1->m_nCoor[0]*height/(row-1);

			coor2[0] = left+pv2->m_nCoor[1]*width/(column-1);
			coor2[1] = top+pv2->m_nCoor[0]*height/(row-1);
//			pdc->MoveTo(x1, y1);
//			pdc->LineTo(x2, y2);
			drawArrow(pdc, coor1, coor2, colorE, edgeW);

			if(mode == GRAPH_SHOW_EDGE_INFOR || mode == GRAPH_SHOW_ALL_INFOR){
				//显示边的信息
				str.Format("%.2f", pe->m_nWeight);
				pdc->TextOut((coor1[0]+coor2[0])/2, (coor1[1]+coor2[1])/2, str);
			}
		}
	}

	//绘制图的顶点
	pdc->SelectObject(&vpen);
	for(i = 0; i<m_vertexs.size(); i++){
		pv = (VerNode*)m_vertexs[i];
		x = left+pv->m_nCoor[1]*width/(column-1);
		y = top+pv->m_nCoor[0]*height/(row-1);
		if(mode == GRAPH_SHOW_NO_INFOR || mode == GRAPH_SHOW_EDGE_INFOR){
			//不显示图的节点信息
			pdc->SelectObject(&vbrush);
			pdc->Ellipse(x-3, y-3, x+3, y+3);
		}else{
			//显示图的节点信息
			pdc->SelectStockObject(WHITE_BRUSH);
			pdc->Ellipse(x-11, y-11, x+11, y+11);
			str.Format("%d", pv->m_nID);
			pdc->TextOut(x, y-7, str);
		}
	}
	
	pdc->SelectStockObject(BLACK_PEN);
	pdc->SelectStockObject(BLACK_BRUSH);
	pdc->SetTextAlign(alignPos);
}


BOOL Graph::isNewVertex(int* coor)
{
	int index = getVertexID(coor);
	if(index>=0){
		return FALSE;
	}else{
		return TRUE;
	}
}

BOOL Graph::isNewEdge(int* coor1, int* coor2)
{
	int id1 = getVertexID(coor1);
	int id2 = getVertexID(coor2);

	if(id1>=0 && id2>=0){
		VerNode* pv = m_vertexs[id1];
		EdgeNode* pe;		
		
		for(int i = 0 ;i<pv->m_edgeOut.size(); i++){
			pe = (EdgeNode*)pv->m_edgeOut[i];
			if(pe->m_pVerTo->m_nID == id2){
				return FALSE;
			}
		}
		return TRUE;
	}else{
		return FALSE;
	}
}

int Graph::getVertexID(int *coor)
{
	int size = m_vertexs.size(); 
	VerNode* pnode = NULL;
	for(int i = 0; i<size; i++){
		pnode = (VerNode*)m_vertexs[i];
		if(coor[0] == pnode->m_nCoor[0] && coor[1] == pnode->m_nCoor[1]){
			return i;
		}
	}
	return -1;
}

void Graph::insertVertex(int *coor)
{
	//在图中插入一个节点 
	if(isNewVertex(coor)){
		int newID = m_vertexs.size();
		VerNode* pnewnode = new VerNode;
		pnewnode->m_nID = newID;
		pnewnode->m_nCoor[0] = coor[0];
		pnewnode->m_nCoor[1] = coor[1];
		pnewnode->m_bInOpen = FALSE;
		pnewnode->m_bInClose = FALSE;
		pnewnode->m_f = 0.0f;
		pnewnode->m_g = 0.0f;

		m_vertexs.push_back(pnewnode);
		m_nVertexNum++;
	}
}

void Graph::insertEdge(int *coor1, int* coor2)
{
	//在图中插入一条边
	//边的方向是从coor1->coor2
	if(isNewEdge(coor1, coor2)){
		int id1 = getVertexID(coor1);
		int id2 = getVertexID(coor2);
		VerNode* pv1 = (VerNode*)m_vertexs[id1];
		VerNode* pv2 = (VerNode*)m_vertexs[id2];
		
		EdgeNode* pnewnode = new EdgeNode;
		pnewnode->m_nWeight = sqrt(pow(coor1[0]-coor2[0], 2)+pow(coor1[1]-coor2[1], 2));
		pnewnode->m_pVerFrom = pv1;
		pnewnode->m_pVerTo = pv2;
		
		pv1->m_edgeOut.push_back(pnewnode);
		pv2->m_edgeIn.push_back(pnewnode);
		m_nEdgeNum++;
	}
}

void Graph::deleteVertex(int* coor)
{
	int index = getVertexID(coor);
	if(index>=0){
		deleteVertex(index);
	}
}

void Graph::deleteVertex(int index)
{
	VerNode* pv = (VerNode*)m_vertexs[index];
	EdgeContainer& edgesOut = pv->m_edgeOut;
	EdgeContainer& edgesIn = pv->m_edgeIn;
	EdgeNode* pedge = NULL;
	int id1 = index, id2 = 0;
	
	//删除所有的出边
	while(edgesOut.size()){
		pedge = (EdgeNode*)edgesOut[0];
		id2 = pedge->m_pVerTo->m_nID;
		deleteEdge(id1, id2);
	}
	//删除所有的入边
	id2 = index;
	while(edgesIn.size()){
		pedge = (EdgeNode*)edgesIn[0];
		id1 = pedge->m_pVerFrom->m_nID;
		deleteEdge(id1, id2);
	}
	//删除该节点,并对index以后的节点的ID进行修改
	m_vertexs.erase(m_vertexs.begin()+index);
	delete pv;
	m_nVertexNum--;

	for(int i = index; i<m_vertexs.size(); i++){
		pv = (VerNode*)m_vertexs[i];
		pv->m_nID--;
	}
}

void Graph::deleteEdge(int* coor1, int* coor2)
{
	int id1 = getVertexID(coor1);
	int id2 = getVertexID(coor2);
	if(id1>=0 && id2>=0){
		deleteEdge(id1, id2);	
	}
}

void Graph::deleteEdge(int id1, int id2)
{
	VerNode* pv1 = (VerNode*)m_vertexs[id1];
	VerNode* pv2 = (VerNode*)m_vertexs[id2];
	EdgeNode* pedge = NULL, * pdelete = NULL;

	int size = pv1->m_edgeOut.size();
	for(int i = 0; i<size; i++){
		pedge = (EdgeNode*)pv1->m_edgeOut[i];
		if(pedge->m_pVerTo->m_nID == id2){
			//发现、删除该边
			pdelete = pedge;
			pv1->m_edgeOut.erase(pv1->m_edgeOut.begin()+i);
			break;
		}
	}

	if(pdelete){
		size = pv2->m_edgeIn.size();
		for(int i = 0; i<size; i++){
			pedge = (EdgeNode*)pv2->m_edgeIn[i];
			if(pedge->m_pVerFrom->m_nID == id1){
				pv2->m_edgeIn.erase(pv2->m_edgeIn.begin()+i);
				break;
			}
		}
		delete pdelete;
		m_nEdgeNum--;
	}
}

//////////////////////////////////////////////////////////////////////////
//save or load the graph file

void Graph::clear()
{
	while(m_vertexs.size()>0){
		deleteVertex(0);
	}
}

void Graph::save(FILE* file)
{
	int size = m_vertexs.size();
	fwrite(&(size), sizeof(int), 1, file);
	//保存图中所有的节点坐标（逻辑）
	VerNode* pv = NULL;
	for(int i = 0; i<size; i++){
		pv = (VerNode*)m_vertexs[i];
		fwrite(&(pv->m_nCoor[0]), sizeof(int), 1, file);
		fwrite(&(pv->m_nCoor[1]), sizeof(int), 1, file);
	}
	//保存图中所有的边
	fwrite(&(m_nEdgeNum), sizeof(int), 1, file);
	EdgeNode* pe = NULL;
	for(i = 0; i<size; i++){
		pv = (VerNode*)m_vertexs[i];
		for(int j = 0; j<pv->m_edgeOut.size(); j++){
			pe = pv->m_edgeOut[j];
			fwrite(&(pe->m_pVerFrom->m_nID), sizeof(int), 1, file);
			fwrite(&(pe->m_pVerTo->m_nID), sizeof(int), 1, file);
		}
	}
}

void Graph::load(FILE* file)
{
	//清空原有的图
	clear();
	//首先读取图的顶点信息
	fread(&(m_nVertexNum), sizeof(int), 1, file);
	VerNode* pv = NULL;
	for(int i = 0; i<m_nVertexNum; i++){
		pv = new VerNode;
		pv->m_nID = i;
		fread(&(pv->m_nCoor[0]), sizeof(int), 1, file);
		fread(&(pv->m_nCoor[1]), sizeof(int), 1, file);
		m_vertexs.push_back(pv);
	}
	//读取边的信息
	fread(&(m_nEdgeNum), sizeof(int), 1, file);
	EdgeNode* pe = NULL;
	int id1, id2;
	VerNode *pv1, *pv2;
	for(i = 0; i<m_nEdgeNum; i++){
		fread(&(id1), sizeof(int), 1, file);
		fread(&(id2), sizeof(int), 1, file);
		pv1 = (VerNode*)m_vertexs[id1];
		pv2 = (VerNode*)m_vertexs[id2];
		
		EdgeNode* pe = new EdgeNode;
		pe->m_nWeight = sqrt(pow(pv1->m_nCoor[0]-pv2->m_nCoor[0], 2)+
			pow(pv1->m_nCoor[1]-pv2->m_nCoor[1], 2));
		pe->m_pVerFrom = pv1;
		pe->m_pVerTo = pv2;
		
		pv1->m_edgeOut.push_back(pe);
		pv2->m_edgeIn.push_back(pe);
	}
}

//////////////////////////////////////////////////////////////////////////
//各种图的搜索算法
void Graph::clearVertexFlag()
{
	int size = m_vertexs.size();
	VerNode* pv = NULL;
	for(int i = 0; i<size; i++){
		pv= m_vertexs[i];
		pv->m_bInOpen = FALSE;
		pv->m_bInClose = FALSE;
		pv->m_f = 0.0f;
		pv->m_g = 0.0f;
	}
}

BOOL Graph::DFS(int* coor1, int* coor2, Graph& tree)
{
	int start = getVertexID(coor1);
	int end = getVertexID(coor2);
	return DFS(start, end, tree);
}	

BOOL Graph::BFS(int* coor1, int* coor2, Graph& tree)
{
	int start = getVertexID(coor1);