graphview.cpp

BFS、DFS、有向图、无向图中的各种算法的实现

				
				}
			////////////////////////////////////////////////////////////////////
			}//ELSE
		}//OUTER IF
		
		pdoc->UpdateAllViews(this);
		Invalidate();
		break;
//case2 end here
///////////////////////////////////////////////////////

/////////////////////////////////////////////////////////
//case 3 is to delete the vertex
	case 3:
		m_pvertex = IsInQueue(point,cenpoint);
		if(m_pvertex)
			pdoc->m_graph.DeleteVer(m_pvertex);
		pdoc->UpdateAllViews(this);
		Invalidate();

		break;
//case3 end here
////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////
//case4 is to move the certain vertexs
	case 4:
		m_pvertex = IsInQueue(point,cenpoint);
		if(m_pvertex)
			m_bcapture = TRUE;
		Invalidate();
		break;
//case4 end here.
//////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////
//case 5 is to receive the information that user input
	case 5:	
		m_pvertex = IsInQueue(point,cenpoint);
		if(m_pvertex != NULL){
			if(m_dialog.DoModal() == IDOK){
				m_pvertex->m_strname = m_dialog.m_strname;
				pdoc->UpdateAllViews(this);
			}
		}
		Invalidate();
		break;
//case5 end here.
////////////////////////////////////////////////////////////
	
//////////////////////////////////////////////////////////////
//case6 is to display the vertex informations
	case 6:
		m_pvertex = IsInQueue(point,cenpoint);
		if(m_pvertex != NULL){
			if(pdoc->m_ntype){
				CDialogV dlg;
				dlg.m_nDu = pdoc->m_graph.CalculateDu(m_pvertex);
				dlg.m_strName = m_pvertex->m_strname;
				dlg.DoModal();
			}
			else{
				CDialogVY dlg;
				dlg.m_nindu = pdoc->m_graph.CalculateInDu(m_pvertex);
				dlg.m_noutdu = pdoc->m_graph.CalculateOutDu(m_pvertex);
				dlg.m_strname = m_pvertex->m_strname;
				dlg.DoModal();
			}
			
		}
		Invalidate();
		break;
//case6 end here.
/////////////////////////////////////////////////////////////

	}// switch 
//switch end here
		
	CView::OnLButtonDown(nFlags, point);
}

CRect CGraphView::PointChangeToRect(CPoint point)
{
	CRect rect(point.x-5,point.y-5,point.x+5,point.y+5);
	return rect;	
}

VerNode* CGraphView::IsInQueue(CPoint p, CPoint &cp)
{
	CGraphDoc* pdoc = GetDocument();
	return pdoc->m_queue.IsInQueue(p,cp);
}




void CGraphView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	if(m_bcapture)
		m_bcapture = FALSE;
	
	CView::OnLButtonUp(nFlags, point);
}

void CGraphView::OnMouseMove(UINT nFlags, CPoint point) 
{
	if(m_bcapture){
		CGraphDoc* pdoc = GetDocument();
		m_pvertex->m_rect = PointChangeToRect(point);
		pdoc->UpdateAllViews(this);
		Invalidate();
	}
		
	
	CView::OnMouseMove(nFlags, point);
}




void CGraphView::OnUpdate(CView* pSender, LPARAM lHint, CObject* pHint) 
{
	
	CGraphDoc* pdoc = GetDocument();
	CClientDC dc(this);
	CRect rect;
	VerNode *start,*end;
	CDialogKD dlg;
	CDialogRV dlg1;


	switch(pdoc->m_ndisplay){
	case 0:	//case0 is to review the graph.
		GetClientRect(rect);
		dc.Rectangle(rect);
		pdoc->m_graph.DisplayGraph(&dc,pdoc->m_ntype);
		dc.TextOut(250,0,"DFS TRAVERSE SCREEN");
		break;
	case 1:	//case1 is to display the DFS informations.
		DisplayVernode(pdoc->m_pviewvernode,&dc);
		break;	
	case 2:	//case2 is to display all the vertexs name.
		DisplayAllName(&dc);
		break;
	case 3: //case3 is to display the original graph.
		Invalidate();
		break;
	case 4:	//case4 is to display the graph in different ways according 
			//the function dialog .
		switch(pdoc->m_nsubfunction){
		case 1://subfunction 1 is to display the DFS screen.
			m_ndisplay = 1;
			Invalidate();
			break;
		case 2://subfunction 2 is to display the BFS screen.
			m_ndisplay = 2;
			Invalidate();
			break;
		case 3://subfunction 3 is to test the two vertexs if they are connected.
			m_ndisplay = 3;
			Invalidate();
			while(dlg1.m_bcontinue){
				if(dlg.DoModal() == IDOK){
					start = pdoc->m_graph.NameToPointer(dlg.m_strSName);
					end = pdoc->m_graph.NameToPointer(dlg.m_strEName);
					if((start == NULL)||(end == NULL))
						::AfxMessageBox("结点信息输入有误！");
					else{
						if(pdoc->m_graph.TestKeda(start,end))
							dlg1.m_strResult = "可达";
						else dlg1.m_strResult = "不可达";
						dlg1.DoModal();
					}
				
				}
				else{
					dlg1.m_bcontinue = FALSE;
				}
			}
			m_ndisplay = 0;
			Invalidate();
			break;
		case 4://subfunction 4 is to ask for the mini path of two vertex .
			if(m_dlg2.DoModal() == IDOK){
				m_ndisplay = 4;
				Invalidate();
			}
			break;
		}
		break;
	case 5://case 5 is to display the BFS screen.
		GetClientRect(rect);
		dc.Rectangle(rect);
		pdoc->m_graph.DisplayGraph(&dc,pdoc->m_ntype);
		dc.TextOut(250,0,"BFS TRAVERSE SCREEN");
		break;
	case 6://case6 is to display all the informations of the graph.
		DisplayAllName(&dc);
		DisplayAllArc(&dc);
		break;
	}
	
}

void CGraphView::DisplayVernode(VerNode *pnode,CDC* pdc)
{
	//Display all the vertexs order in DFS or BFS search.
	CString str;
	str.Format("%d",pnode->m_nvisit);
	CPen newpen(PS_DASHDOTDOT,2,RGB(255,0,0));
	pdc->SelectObject(&newpen);
	pdc->Ellipse(pnode->m_rect.left-5,pnode->m_rect.top-5,
		pnode->m_rect.right+5,pnode->m_rect.bottom+5);
	pdc->TextOut(pnode->m_rect.left,pnode->m_rect.top-3,str);
	pdc->SelectStockObject(BLACK_PEN);
}

void CGraphView::DisplayAllName(CDC *pdc)
{
	//Display all the name of the vertexs.
	CGraphDoc* pdoc = GetDocument();
	CPen newpen(PS_DASHDOTDOT,2,RGB(255,0,0));
	pdc->SelectObject(&newpen);
	for(VerNode* pnode = pdoc->m_queue.m_phead;pnode;pnode = pnode->m_pnextver){
		pdc->Rectangle(pnode->m_rect.left-10,pnode->m_rect.top-3,
			pnode->m_rect.right+10,pnode->m_rect.bottom+8);
		pdc->TextOut(pnode->m_rect.left,pnode->m_rect.top,pnode->m_strname);
	}
	pdc->SelectStockObject(BLACK_PEN);
}

void CGraphView::DisplayAllArc(CDC *pdc)
{
	//Display all the arc and their weight.
	CGraphDoc* pdoc = GetDocument();
	ArcNode* parc;
	int x1,x2,y1,y2;
	CString str;
	for(VerNode* pver = pdoc->m_queue.m_phead;pver;pver = pver->m_pnextver){
		x1 = (pver->m_rect.left+pver->m_rect.right)/2;
		y1 = (pver->m_rect.top+pver->m_rect.bottom)/2;
		for(parc = pver->m_pfirstarc;parc;parc = parc->m_pnextarc){
			x2 = (parc->m_padjver->m_rect.left+parc->m_padjver->m_rect.right)/2;
			y2 = (parc->m_padjver->m_rect.top+parc->m_padjver->m_rect.bottom)/2;
			str.Format("%d",parc->info);
			pdc->TextOut((x1+x2)/2,(y1+y2)/2,str);
		}
	}
}


void CGraphView::DisplayName(VerNode* pnode,CDC* pdc)
{
	//Display the name of the NODE.
	CGraphDoc* pdoc = GetDocument();
	CPen newpen(PS_DASHDOTDOT,2,RGB(255,0,0));
	pdc->SelectObject(&newpen);
	pdc->Rectangle(pnode->m_rect.left-10,pnode->m_rect.top-3,
			pnode->m_rect.right+10,pnode->m_rect.bottom+8);
	pdc->TextOut(pnode->m_rect.left,pnode->m_rect.top,pnode->m_strname);

	pdc->SelectStockObject(BLACK_PEN);
}

void CGraphView::DisplayArc(CDC *pdc,VerNode* start,VerNode* end)
{
	//Display the arc and its name.
	CPen newpen(PS_DASHDOTDOT,2,RGB(255,0,0));
	int weight,x2,y2,x1,y1;
	CString str;
	x1 = (start->m_rect.left+start->m_rect.right)/2;
	y1 = (start->m_rect.top+start->m_rect.bottom)/2;
	x2 = (end->m_rect.left+end->m_rect.right)/2;
	y2 = (end->m_rect.top+end->m_rect.bottom)/2;
	pdc->SelectObject(&newpen);
	pdc->MoveTo(x1,y1);
	pdc->LineTo(x2,y2);
	for(ArcNode* parc = start->m_pfirstarc;parc;parc = parc->m_pnextarc)
		if(parc->m_padjver == end)
			weight = parc->info;
	str.Format("%d",weight);
	pdc->TextOut((x1+x2)/2,(y1+y2)/2,str);
	pdc->SelectStockObject(BLACK_PEN);
}