graphview.cpp

演示了最小生成树的普林算法和克鲁斯卡尔算法得算法过程。

// GraphView.cpp : implementation of the CGraphView class
//

#include "stdafx.h"
#include "Graph.h"

#include "GraphDoc.h"
#include "GraphView.h"
#include "Smalltree.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

//我的定义
//bool primeif = false;
//bool kruscalif = false;
Smalltree smalltree;
//定义结束

/////////////////////////////////////////////////////////////////////////////
// CGraphView

IMPLEMENT_DYNCREATE(CGraphView, CView)

BEGIN_MESSAGE_MAP(CGraphView, CView)
	//{{AFX_MSG_MAP(CGraphView)
	ON_COMMAND(ID_PRIME, OnPrime)
	ON_COMMAND(ID_KRUSCAL, OnKruscal)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CGraphView construction/destruction

CGraphView::CGraphView()
{
	linewide = 3;
	linecol = RGB(155,234,71);
	for(int i = 0;i < 18;i++)
	{
		pvex[i].vpoint.x = 0;
		pvex[i].vpoint.y = 0;
		pvex[i].weight = MAX;
		kvex[i].vpoint.x = 0;
		kvex[i].vpoint.y = 0;
		kvex[i].weight = MAX;

	}
	primeif = false;
	kruscalif = false;

}

CGraphView::~CGraphView()
{
}

BOOL CGraphView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CGraphView drawing

void CGraphView::OnDraw(CDC* pDC)
{
	CGraphDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	//my own codes
	CRect rect;
	GetClientRect(&rect);
	smalltree.putvpoint(rect);
	MapX = rect.right/4;
	MapY = 0;
	primeX = 0;
	primeY = rect.bottom/2;
	kX = rect.right/2;
	kY = rect.bottom/2;

	drawmap(pDC,smalltree);
	//drawPnode(pDC,smalltree);
	//drawKnode(pDC,smalltree);
	if(primeif == true)
	{
		int pcount = 0;		
		pcount = smalltree.prime(pvex);
		drawPnode(pDC,smalltree);
		for(int p = 0; p< pcount; p++)
		{
			Pos point = pvex[p];
			int weight = pvex[p].weight;
			CPoint fromvex = smalltree.vpoint[smalltree.graph.vexs[point.vpoint.x].pos];
			CPoint endvex = smalltree.vpoint[smalltree.graph.vexs[point.vpoint.y].pos];
			fromvex.x = fromvex.x + primeX;
			fromvex.y = fromvex.y + primeY;
			endvex.x = endvex.x + primeX;
			endvex.y = endvex.y + primeY;
			//smalltree.posvex.pop();
			drawline(pDC,fromvex,endvex,weight);
			Sleep(300);
		}
		drawPnode(pDC,smalltree);
	}
	if(kruscalif == true)
	{
		int kcount = 0;		
		kcount = smalltree.kruscal(kvex);
		drawKnode(pDC,smalltree);
		for(int k =0; k < kcount ; k++)
		{
			Pos kpoint = kvex[k];
			int kweight = kpoint.weight;
			CPoint kfromvex = smalltree.vpoint[smalltree.graph.vexs[kpoint.vpoint.x].pos];
			CPoint kendvex = smalltree.vpoint[smalltree.graph.vexs[kpoint.vpoint.y].pos];
			kfromvex.x = kfromvex.x + kX;
			kfromvex.y = kfromvex.y + kY;
			kendvex.x = kendvex.x + kX;
			kendvex.y = kendvex.y + kY;
			//smalltree.kposvex.pop();
			drawline(pDC,kfromvex,kendvex,kweight);
			Sleep(300);
		}
		drawKnode(pDC,smalltree);
	}
	//finished
}

/////////////////////////////////////////////////////////////////////////////
// CGraphView diagnostics

#ifdef _DEBUG
void CGraphView::AssertValid() const
{
	CView::AssertValid();
}

void CGraphView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CGraphDoc* CGraphView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CGraphDoc)));
	return (CGraphDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CGraphView message handlers

////////////////////////////我的定义//////////////////////////////////////
void CGraphView::drawline(CDC* hdc, CPoint point1,CPoint point2,int weight)
{
	char buf[5];
	wsprintf(buf,"%d",weight);
	CPen siPen;
	CPen* hOldpen;
	siPen.CreatePen(PS_SOLID,linewide,linecol);
	hOldpen = hdc->SelectObject(&siPen);
	

	hdc->MoveTo(point1);
	hdc->LineTo(point2);
	hdc->TextOut((point1.x+point2.x)/2,(point1.y + point2.y) /2,buf,strlen(buf));
	hdc->SelectObject(hOldpen);
	siPen.DeleteObject();
}

void CGraphView::OnPrime() 
{
	primeif = true;
	kruscalif = false;
	Invalidate();
	
}

void CGraphView::OnKruscal() 
{
	primeif = false;
	kruscalif = true;
	Invalidate();	
}

void CGraphView::drawmap(CDC* hdc,Smalltree& smalltree)
{
	//char data;
	CPen eiPen;
	CPen* hOldpen;
	eiPen.CreatePen(PS_SOLID,linewide,linecol);
	hOldpen = (CPen*)hdc->SelectObject(&eiPen);
	for(int j = 0;j<N;j++)
	{
		for(int k = j+1;k < N;k++)
		{
			if(smalltree.graph.arcs[j][k] != MAX)
			{

				char buf[5];
				wsprintf(buf,"%d",smalltree.graph.arcs[j][k]);

				CPoint vpos;
				vpos.x = smalltree.graph.vexs[j].pos;
				vpos.y = smalltree.graph.vexs[k].pos;
				CPoint fromvex;
				fromvex.x = MapX + smalltree.vpoint[vpos.x].x;
				fromvex.y = MapY + smalltree.vpoint[vpos.x].y; 
				CPoint endvex;
				endvex.x = MapX + smalltree.vpoint[vpos.y].x;
				endvex.y = MapY + smalltree.vpoint[vpos.y].y;
				hdc->MoveTo(fromvex.x,fromvex.y);
				hdc->LineTo(endvex.x,endvex.y);
				hdc->TextOut((fromvex.x+endvex.x)/2,(fromvex.y + endvex.y) /2,buf,strlen(buf));
			}
		}
	}
	hdc->SelectObject(hOldpen);
	eiPen.DeleteObject();

	COLORREF col = RGB(166,202,240);
	CBrush eiBrush;
	CBrush* hOldbrush;
	
	hOldpen = (CPen*)hdc->SelectStockObject(NULL_PEN);
	eiBrush.CreateSolidBrush(col);
	hOldbrush = hdc->SelectObject(&eiBrush);
	for(int i = 0; i< N;i++)
	{
		CRect rrect;
		rrect.left = MapX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x - R;
		rrect.top = MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y - R;
		rrect.right = MapX + smalltree.vpoint[smalltree.graph.vexs[i].pos].x + R;
		rrect.bottom = MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y + R;
		//CRect((MapX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x - R),(MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y - R),(MapX + smalltree.vpoint[smalltree.graph.vexs[i].pos].x + R),(MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y + R))
		hdc->Ellipse(rrect);
		CPoint textpos;
		textpos.x = MapX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x-textR;
		textpos.y = MapY+smalltree.vpoint[smalltree.graph.vexs[i].pos].y-textR;
		CString datanode(smalltree.graph.vexs[i].data);
		hdc->TextOut(textpos.x,textpos.y,datanode,1*sizeof(char));
	}
	hdc->SelectObject(hOldpen);
	hdc->SelectObject(hOldbrush);
	eiBrush.DeleteObject();

	
}


void CGraphView::drawPnode(CDC* hdc,Smalltree& smalltree)
{
	COLORREF col = RGB(166,202,240);
	CBrush eiBrush;
	CBrush* hOldbrush;
	CPen* hOldpen;
	hOldpen = (CPen*)hdc->SelectStockObject(NULL_PEN);
	eiBrush.CreateSolidBrush(col);
	hOldbrush = hdc->SelectObject(&eiBrush);
	for(int i = 0; i< N;i++)
	{
		CRect rrect;
		rrect.left = primeX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x - R;
		rrect.top = primeY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y - R;
		rrect.right = primeX + smalltree.vpoint[smalltree.graph.vexs[i].pos].x + R;
		rrect.bottom = primeY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y + R;
		//CRect((primeX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x - R),(MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y - R),(primeX + smalltree.vpoint[smalltree.graph.vexs[i].pos].x + R),(MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y + R))
		hdc->Ellipse(rrect);
		CPoint textpos;
		textpos.x = primeX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x-textR;
		textpos.y = primeY+smalltree.vpoint[smalltree.graph.vexs[i].pos].y-textR;
		CString datanode(smalltree.graph.vexs[i].data);
		hdc->TextOut(textpos.x,textpos.y,datanode,1*sizeof(char));
	}
	hdc->SelectObject(hOldpen);
	hdc->SelectObject(hOldbrush);
	eiBrush.DeleteObject();
}

void CGraphView::drawKnode(CDC* hdc,Smalltree& smalltree)
{
	COLORREF col = RGB(166,202,240);
	CBrush eiBrush;
	CBrush* hOldbrush;
	CPen* hOldpen;
	hOldpen = (CPen*)hdc->SelectStockObject(NULL_PEN);
	eiBrush.CreateSolidBrush(col);
	hOldbrush = hdc->SelectObject(&eiBrush);
	for(int i = 0; i< N;i++)
	{
		CRect rrect;
		rrect.left = kX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x - R;
		rrect.top = kY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y - R;
		rrect.right = kX + smalltree.vpoint[smalltree.graph.vexs[i].pos].x + R;
		rrect.bottom = kY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y + R;
		//CRect((MapX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x - R),(MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y - R),(MapX + smalltree.vpoint[smalltree.graph.vexs[i].pos].x + R),(MapY + smalltree.vpoint[smalltree.graph.vexs[i].pos].y + R))
		hdc->Ellipse(rrect);
		CPoint textpos;
		textpos.x = kX+smalltree.vpoint[smalltree.graph.vexs[i].pos].x-textR;
		textpos.y = kY+smalltree.vpoint[smalltree.graph.vexs[i].pos].y-textR;
		CString datanode(smalltree.graph.vexs[i].data);
		hdc->TextOut(textpos.x,textpos.y,datanode,1*sizeof(char));
	}
	hdc->SelectObject(hOldpen);
	hdc->SelectObject(hOldbrush);
	eiBrush.DeleteObject();
}

////////////////////////////定义结束//////////////////////////////////////