mstscr.cpp

运筹学最小支撑树的求解方法。该程序共有两种计算方法

// MSTScr.cpp : implementation file
//

#include "stdafx.h"
#include "MSTPro.h"
#include "MSTScr.h"
#include "MSTProDlg.h"
#include "InputValue.h"

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

/////////////////////////////////////////////////////////////////////////////
// CMSTScr
UINT Step1_Proc( LPVOID pParam );
UINT Step2_Proc( LPVOID pParam );

CMSTScr::CMSTScr()
{
	CBitmap m_Bitmap;
	m_Bitmap.LoadBitmap(IDB_BMPPOT);
	MemDC_Pot.CreateCompatibleDC(NULL);
	MemDC_Pot.SelectObject(&m_Bitmap);

	CBitmap m_BitmapR;
	m_BitmapR.LoadBitmap(IDB_BMPPOTRED);
	MemDC_PotRed.CreateCompatibleDC(NULL);
	MemDC_PotRed.SelectObject(&m_BitmapR);

	ptr_View=NULL;
	FirstChoose=FALSE;
	First_Index=-1;
	DirectionOrNot=-1;
	ReDraw = false;
}

CMSTScr::~CMSTScr()
{
	do{
		if(PointArray.GetSize())
		{
			structPot * ptrPot=(structPot *)PointArray.GetAt(0);
			PointArray.RemoveAt(0);
			delete ptrPot;
			ptrPot=NULL;
		}else break;
	}while(1);
}


BEGIN_MESSAGE_MAP(CMSTScr, CStatic)
	//{{AFX_MSG_MAP(CMSTScr)
	ON_WM_PAINT()
	ON_WM_LBUTTONDOWN()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMSTScr message handlers

void CMSTScr::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	// TODO: Add your message handler code here
	if(ReDraw)
	{
		CBrush Brush;
		Brush.CreateSolidBrush(GetSysColor(COLOR_MENU));
		RECT Rect;
		GetClientRect(&Rect);
		dc.FillRect(&Rect,&Brush);
		ReDraw=false;
	}
	DrawGrid(&dc);
	DrawGraph(&dc);
	// Do not call CStatic::OnPaint() for painting messages
}

void CMSTScr::DrawGraph(CDC *pDC)
{
	CPen penLight(PS_SOLID, 1, GetSysColor(COLOR_HIGHLIGHT));
	CPen penWild(PS_SOLID, 2, RGB(255,0,0));
	CPen *pOldPen = pDC->SelectObject( &penLight );
	for(int icount=0;icount<PointArray.GetSize();icount++)
	{
		CPoint point;	CString strNum;	  CSize Size;	
		
		structPot * ptrPot=(structPot *)PointArray.GetAt(icount);//得到图中顶点
		point=ptrPot->point;//取得该顶点的坐标
		CDC * ptrCDC=ptrPot->G_R ? &MemDC_Pot:&MemDC_PotRed;//取得该顶点的位图显示类型
		pDC->BitBlt(point.x-6,point.y-6,12,12,ptrCDC,0,0,SRCCOPY);//显示位图
		
		strNum.Empty();
		strNum.Format("V%d",ptrPot->tag);//取得该顶点标号的字符串
		Size=pDC->GetTextExtent(strNum);//计算该顶点字符串的尺寸
		pDC->SetBkMode(TRANSPARENT);//设置显示背景
		pDC->TextOut( point.x-Size.cx/2, point.y-6-Size.cy,strNum);//显示该顶点字符串

		for(int jcount=0;jcount< ptrPot->neighborhood.GetSize();jcount++)//显示从该顶点出发的边
		{
			border Border=ptrPot->neighborhood.GetAt(jcount);//取得其中一条边的指针
			structPot * ptrPot_another=(structPot *)PointArray.GetAt(Border.index);//取得该边的另一个顶点的坐标
			//得到两个点，point和ptrPot_another->point,以及该边的权重Border.value；
			if(Border.isTree)
			{
				pDC->SelectObject( &penWild );
				pDC->MoveTo(point);
				pDC->LineTo( ptrPot_another->point );//画出该边
				pDC->SelectObject( &penLight);
			}
			else
			{
				pDC->MoveTo(point);
				pDC->LineTo( ptrPot_another->point );//画出该边
			}
			strNum.Empty();
			strNum.Format("%d",Border.value);//取得该边权重字符串
			Size=pDC->GetTextExtent(strNum);//计算边权重字符串的尺寸
			int dx=(point.x+ptrPot_another->point.x)/2-Size.cx/2;
			int dy=(point.y+ptrPot_another->point.y)/2-Size.cy/2;//计算显示位置
			pDC->SetBkMode(OPAQUE);//设置显示背景
			pDC->TextOut(dx,dy,strNum);//显示该边权重字符串
/*			if(this->DirectionOrNot == 1)//如果是有向图
			{
				int ArrowX=point.x+(ptrPot_another->point.x-point.x)*2/3;
				int ArrowY=point.y+(ptrPot_another->point.y-point.y)*2/3;
				double Dx=(ptrPot_another->point.x-point.x);
				double Dy=(ptrPot_another->point.y-point.y);
				double sina=Dy/sqrt(Dx*Dx+Dy*Dy);
				int D_x=(int)(sqrt((1-sina*sina))*6);
				int D_y=(int)(sina*6);
				pDC->MoveTo(ArrowX-D_x,ArrowY+D_y);
				pDC->LineTo(ArrowX+6,ArrowY+6);
				pDC->LineTo(ArrowX+D_x,ArrowY-D_y);
			}
*/		}
	}
	pDC->SelectObject( pOldPen );
}

void CMSTScr::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if( ((CButton * )ptr_View->GetDlgItem(IDC_RADIO1))->GetCheck() )
	{
		if( DirectionOrNot == -1 )
		{
			if( ((CButton * )ptr_View->GetDlgItem(IDC_RADIO5))->GetCheck() ) DirectionOrNot = 0;
			else DirectionOrNot = 1;
			((CButton * )ptr_View->GetDlgItem(IDC_RADIO5))->EnableWindow(FALSE);
			((CButton * )ptr_View->GetDlgItem(IDC_RADIO6))->EnableWindow(FALSE);
		}
		RECT rect;
		CPaintDC dc(this);
		GetClientRect(&rect);
		if( point.x >= 12 && point.x <= rect.right-12 && point.y >= 6 + 16 && point.y <= rect.bottom - 6 )
		{
			structPot * ptrPot=new structPot;
			ptrPot->point=point;
			int size = PointArray.GetSize();
			if( ! size )	ptrPot->tag = 1;
			else ptrPot->tag = ((structPot *)PointArray.GetAt( size -1 ))->tag + 1;
			ptrPot->G_R=true;
			PointArray.Add(ptrPot);
			Invalidate();
		}
	}
	else if(((CButton * )ptr_View->GetDlgItem(IDC_RADIO2))->GetCheck())
	{
		int size = PointArray.GetSize();
		for(int icount=0; icount < size; icount++)
		{
			CPoint Array_point=((structPot *)PointArray.GetAt(icount))->point;
			if( point.x <= Array_point.x + 6 && point.x >= Array_point.x - 6
				&& point.y <= Array_point.y + 6 && point.y >= Array_point.y - 6 )
			{
				if( ! FirstChoose ){
					structPot * ptrPot=(structPot *)PointArray.GetAt(icount);//取得该点
					ptrPot->G_R=false;		//修改图形显示方式参数
					PointArray.SetAt(icount,ptrPot);	//替换原先的点
					FirstChoose=TRUE;
					First_Index=icount;
					Invalidate();
				}else{	
					structPot * ptrPot;
					ptrPot=(structPot *)PointArray.GetAt(First_Index);//取得前一个点
					if(icount == First_Index){	//如果是同一个点
						ptrPot->G_R=true;		//修改图形显示方式。
						PointArray.SetAt(First_Index,ptrPot);
					}else{	//对边的权重进行操作
						CInputValue dlg;
						dlg.DoModal();
						CString strValue=dlg.m_value;
						strValue.TrimLeft();	//得到权重
						border Border;	
						Border.value=atoi(strValue.GetBuffer(10));
						Border.index = icount;
						for(int jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++)
							if(ptrPot->neighborhood.GetAt(jcount).index==Border.index) break;
						if( jcount == ptrPot->neighborhood.GetSize() )	ptrPot->neighborhood.Add(Border);
						else{
							this->ReDraw = TRUE;
							ptrPot->neighborhood.SetAt(jcount,Border);
						}
						ptrPot->G_R=true;
						PointArray.SetAt(First_Index,ptrPot);
						if(this->DirectionOrNot==0)//如果为无向图
						{
							ptrPot=(structPot *)PointArray.GetAt(icount);
							Border.index = First_Index;
							for(int jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++)
								if(ptrPot->neighborhood.GetAt(jcount).index==Border.index) break;
							if( jcount == ptrPot->neighborhood.GetSize() )	ptrPot->neighborhood.Add(Border);
							else ptrPot->neighborhood.SetAt(jcount,Border);
							PointArray.SetAt(icount,ptrPot);
						}
					}
					FirstChoose=FALSE;
					First_Index=-1;
					Invalidate();
				}
			}
		}
	}
	CStatic::OnLButtonDown(nFlags, point);
}

void CMSTScr::SetParent(CMSTProDlg * ptr){	ptr_View=ptr; }

void CMSTScr::DrawGrid(CDC *pDC)
{
	RECT rect;
	CPaintDC dc(this);
	GetClientRect(&rect);
	CPen penLight(PS_SOLID, 1, GetSysColor(COLOR_3DLIGHT));
	CPen *pOldPen = pDC->SelectObject( &penLight );
	
	int Interval=20;
	do{
		if( Interval < rect.bottom )
		{
			pDC->MoveTo(0,Interval-1);
			pDC->LineTo(rect.right,Interval-1);
			Interval+=20;
		}
		else if( Interval > rect.bottom ) break;
	}while(1);

	Interval=20;
	do{
		if( Interval < rect.right )
		{
			pDC->MoveTo(Interval-1,0);
			pDC->LineTo(Interval-1,rect.bottom);
			Interval+=20;
		}
		else if( Interval > rect.right ) break;
	}while(1);

	pDC->SelectObject( pOldPen );
}

void CMSTScr::WorkMST2()
{
	if( !PointArray.GetSize() ) return; //网络图中没有顶点

	int icount=0,jcount=0,index=0;
	
	//构造点对集合pointCoupleArray，包含点对的两个点和权重
	CPtrArray pointCoupleArray;
	CPtrArray Set_C_Array;

	for(icount=0;icount<PointArray.GetSize();icount++)
	{
		CStruct_C * ptrSet_C=new CStruct_C;
		ptrSet_C->PotArray.Add(icount);
		Set_C_Array.Add(ptrSet_C);

		structPot *ptrPot=(structPot *)PointArray.GetAt(icount);
		if( ! ptrPot->neighborhood.GetSize() )
		{
			MessageBox("网络中存在孤立点！","Input Error!",MB_OK|MB_ICONINFORMATION);
			do{
				if(pointCoupleArray.GetSize())
				{
					CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
					pointCoupleArray.RemoveAt(0);
					delete ptrCouple;
					ptrCouple=NULL;
				}else break;
			}while(1);
			do{
				if(Set_C_Array.GetSize())
				{
					CStruct_C * ptrPot=(CStruct_C *)Set_C_Array.GetAt(0);
					Set_C_Array.RemoveAt(0);
					delete ptrPot;
					ptrPot=NULL;
				}else break;
			}while(1);
			return;
		}

		for(jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++){
			//icount当前顶点的索引，
			//ptrPot->neighborhood.GetAt(jcount).index,从当前节点出发的边的另一个顶点的索引
			CPointCouple * ptrCouple=new CPointCouple(icount,
				ptrPot->neighborhood.GetAt(jcount).index,ptrPot->neighborhood.GetAt(jcount).value);
			for(index=0; index<pointCoupleArray.GetSize(); index++ )
				if( ( * ( (CPointCouple *)pointCoupleArray.GetAt(index) ) ) == ( * ptrCouple) )	break;
			if( index == pointCoupleArray.GetSize() )	pointCoupleArray.Add(ptrCouple);
			else delete ptrCouple;
		}
	}
	if( ! PointArray.GetSize() ) return;//网络图中没有边
	UndoTree();

	while( Set_C_Array.GetSize() > 1 )
	{
		//重新初始化集合C中所有元素的最小值。
		index=0; 
		do{
			( (CStruct_C *)Set_C_Array.GetAt( index ++ ) )->SetMin();	
		}while( index != Set_C_Array.GetSize() ); 
		
		//对于网络中的每一条边，匹配集合C中的元素。
		for(icount=0; icount < pointCoupleArray.GetSize(); icount++)
		{	//ptrCouple—取得的当前边(点对)的指针
			CPointCouple * ptrCouple = (CPointCouple *)pointCoupleArray.GetAt(icount);
			int index1=-1,index2=-1;	//对于取出的点对的一个点位于集合C中的元素的索引。
			//ptrSet_C_Locate—取得的集合C的当前元素指针。
			for(jcount=0; jcount<Set_C_Array.GetSize(); jcount++)
			{
				CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(jcount);
				for(index=0; index < ptrSet_C_Locate->PotArray.GetSize(); index++ )
				{
					if( ptrSet_C_Locate->PotArray.GetAt(index) == ptrCouple->indexpoint1 ) index1 = jcount;
					if( ptrSet_C_Locate->PotArray.GetAt(index) == ptrCouple->indexpoint2 ) index2 = jcount;
				}
				if( index1 == index2 && index1 != -1 && index2 != -1) break;
			}
			ASSERT( index1 != -1 || index2 != -1 );  //必然会在其中找到。
			if( index1 != index2 )//找到了分属于不同的点集合。
			{
				int D_uv = ptrCouple->value;
				int & MinPot1 = ((CStruct_C *)Set_C_Array.GetAt(index1))->MinPot;
				if( D_uv < MinPot1 )
				{
					MinPot1=D_uv;
					//记录了该点对在点对集合中的位置
					((CStruct_C *)Set_C_Array.GetAt(index1))->Shortest = icount;
				}
				int & MinPot2 = ((CStruct_C *)Set_C_Array.GetAt(index2))->MinPot;
				if( D_uv < MinPot2 )
				{
					MinPot2 = D_uv;
					//记录了该点对在点对集合中的位置
					((CStruct_C *)Set_C_Array.GetAt(index2))->Shortest = icount;
				}
			}
		}
		//for all Sj属于C, do T:T并{shortest[j]};
		for(icount=0; icount<Set_C_Array.GetSize(); icount++)
		{
			CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(icount);
			ptrSet_C_Locate->AddShortest(pointCoupleArray);
		}
		//找出（V，T）的连通分图集合C
		icount=0;
		while(icount <Set_C_Array.GetSize())