graphview.cpp

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

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

#include "stdafx.h"
#include "graph.h"

#include "graphDoc.h"
#include "graphView.h"
#include "DialogI.h"

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

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

IMPLEMENT_DYNCREATE(CGraphView, CView)

BEGIN_MESSAGE_MAP(CGraphView, CView)
	//{{AFX_MSG_MAP(CGraphView)
	ON_WM_LBUTTONDOWN()
	ON_WM_LBUTTONUP()
	ON_WM_MOUSEMOVE()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

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

CGraphView::CGraphView()
{
	m_bstart = 1;
	m_narc = 0;
	m_nver = 0;
	m_pvertex = NULL;
	m_pfirstver = NULL;
	m_plastver = NULL;
	m_start = CPoint(0,0);
	m_nmark = 0;
	m_bcapture = FALSE;
	m_bnew = TRUE;
	m_ndisplay = 0;

}

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);

	BOOL* p;
	BOOL** p1;
	int i,j;
	int endcount;
	VerNode *start,*end,*pnode;
	ArcNode* parc;

	if(m_bnew){	
		m_bnew = FALSE;
		CDialogS dlg;
		dlg.DoModal();
		pDoc->m_ntype = dlg.m_ntype;
	}
	switch(m_ndisplay){
		//Display the graph according the parament
	case  0:// case 0 is to display the graph normally.
		pDC->TextOut(250,0,"INPUT SCREEN");
		pDoc->m_graph.DisplayGraph(pDC,pDoc->m_ntype);
		break;
	case 1://case 1 is to display the graph DFS informations.
		pDC->TextOut(250,0,"DFS TRAVERSE SCREEN");
		pDoc->m_graph.DisplayGraph(pDC,pDoc->m_ntype);
		pDoc->m_graph.DFSTraverse(pDC);
		m_ndisplay = 0;
		break;
	case 2://case 2 is to display the graph BFS informations.
		pDC->TextOut(250,0,"BFS TRAVERSE SCREEN");
		pDoc->m_graph.DisplayGraph(pDC,pDoc->m_ntype);
		pDoc->m_graph.BFSTraverse(pDC);
		m_ndisplay = 0;
		break;
	case 3://case 3 is to display the vertex name and the arc weight of the graph.
		pDC->TextOut(250,0,"INFORMATION SCREEN");
		pDoc->m_graph.DisplayGraph(pDC,pDoc->m_ntype);
		DisplayAllName(pDC);
		DisplayAllArc(pDC);
		break;
	case 4://case 4 is to display the graph's mini path that from the start to the end . 
		pDC->TextOut(250,0,"MINIMIZE PATH SCREEN");
		pDoc->m_graph.DisplayGraph(pDC,pDoc->m_ntype);
		p1 = new BOOL*[pDoc->m_queue.m_nnum];
		for(i =0;i<pDoc->m_queue.m_nnum;i++){
			p = new BOOL[pDoc->m_queue.m_nnum];
			p1[i] = p;
		}												
		start = pDoc->m_graph.NameToPointer(m_dlg2.m_strSName);
		end = pDoc->m_graph.NameToPointer(m_dlg2.m_strEName);
		if((start == NULL)||(end == NULL))
			::AfxMessageBox("结点信息输入有误！");
		else{
			endcount = pDoc->m_graph.PointerToNum(end);
			if(pDoc->m_graph.TestKeda(start,end)){
				pDoc->m_graph.ShortestPath(start,p1);
////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////OUTPUT THE MINI PATH HERE.
				for(pnode = pDoc->m_queue.m_phead;pnode;pnode = pnode->m_pnextver)
					pnode->m_bvisit = FALSE;
					for(pnode = pDoc->m_queue.m_phead;pnode;pnode = pnode->m_pnextver){
						i = pDoc->m_graph.PointerToNum(pnode);
						if(p1[endcount][i]&&(i != endcount)){								
							for(parc = pnode->m_pfirstarc;parc;parc = parc->m_pnextarc){
								j = pDoc->m_graph.PointerToNum(parc->m_padjver);
								if(p1[endcount][j]&&(j!=endcount)){
									pnode->m_bvisit = TRUE;	
									DisplayArc(pDC,pnode,parc->m_padjver);
								}
							
							}
						}
					}
					for(pnode = pDoc->m_queue.m_phead;pnode;pnode = pnode->m_pnextver){
						i = pDoc->m_graph.PointerToNum(pnode);
						if(p1[endcount][i]&&(!pnode->m_bvisit)&&(i != endcount))
							DisplayArc(pDC,pnode,end);
					}

////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
					
					for(i = 0,pnode = pDoc->m_queue.m_phead;
						i<pDoc->m_queue.m_nnum;i++,pnode = pnode->m_pnextver){
							if(p1[endcount][i])DisplayName(pnode,pDC);
					}
				}
				else{
					::AfxMessageBox("结点间不可达！");
				}
		}
		m_ndisplay = 0;
		break;
	}
	switch(pDoc->m_nfunction){
		//Output the tip of the different functions
	case 1://case 1 is to give the tip of the vertexs setting.
		pDC->TextOut(200,30,"press the left button to set vertexs");
		break;
	case 2://case 2 is to give the tip of the arc setting.
		if(m_bstart == FALSE)
			pDC->TextOut(200,30,"choose end-point");
		else pDC->TextOut(200,30,"choose start-point");
		break;
	case 3://case 3 is to give the tip of the vertex delete.
		pDC->TextOut(200,30,"choose the vertex that you want to delete.");
		break;
	case 4:
		break;
	case 5://case 5 is to give the tip of the initialization of the vertex name.
		pDC->TextOut(200,30,"choose the vertex that you want to input informations.");
		break;
	case 6://case 6 is to give the tip og the initialization of the arc weight.
		pDC->TextOut(200,30,"choose the vertex that you want to view the informations.");
		break;
	}
	

	
}

/////////////////////////////////////////////////////////////////////////////
// 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::OnLButtonDown(UINT nFlags, CPoint point) 
{
	CRect rect;
	CPoint cenpoint;
	CGraphDoc* pdoc = GetDocument();
	CClientDC dc(this);
///////////////////////////////////////////////////////////////////////////////////////
//switch to different fuctions
	switch(pdoc->m_nfunction){
/////////////////////////////////////////////
//case1 is to select the vertex 
	case 1:
		//to draw all the vertexs here
		rect=PointChangeToRect(point);
		dc.SelectStockObject(BLACK_BRUSH);
		dc.Ellipse(rect);

		pdoc->m_queue.EnQueue(rect);
		pdoc->UpdateAllViews(this);
		Invalidate();
		break;
//case1 end here
/////////////////////////////////////////////
		
/////////////////////////////////////////////
//case2 is to select the arc
	case 2:
		//to draw all the arcs here
		if(IsInQueue(point,cenpoint)){


			//point is in the vertexs		
			if(m_bstart == TRUE){
				//to accept the start coordinate
				m_start = cenpoint;
				m_bstart = FALSE;
				m_pfirstver = IsInQueue(point,cenpoint);
				
			}
			else{
				//to accept the last coordinate
				m_plastver = IsInQueue(point,cenpoint);	
			////////////////////////////////////////////////////////////////
				switch(pdoc->m_ntype){
				case 0:
					if(pdoc->m_graph.IsNewArc(m_pfirstver,m_plastver)
						&&m_pfirstver != m_plastver){
						m_bstart = TRUE;
						pdoc->m_graph.InsertArc(m_pfirstver,m_plastver,m_nmark);
					}
					else{
						if(m_pfirstver == m_plastver)
							::AfxMessageBox("Don't choose the same vertex of one arc.");
						else
							::AfxMessageBox("You already inserted this arc,please insert another. ");
						m_bstart = TRUE;
					}//ELSE
					break;
				case 1:
					if(pdoc->m_graph.IsNewArc(m_pfirstver,m_plastver)
						&&pdoc->m_graph.IsNewArc(m_plastver,m_pfirstver)
						&&m_pfirstver != m_plastver){
						m_bstart = TRUE;
						pdoc->m_graph.InsertArc(m_pfirstver,m_plastver,m_nmark);
						pdoc->m_graph.InsertArc(m_plastver,m_pfirstver,m_nmark++);
			
					}
					else{
						if(m_pfirstver == m_plastver)
							::AfxMessageBox("Don't choose the same vertex of one arc.");
						else
							::AfxMessageBox("You already inserted this arc,please insert another. ");
						m_bstart = TRUE;
					}//ELSE
					break;