graphsearchview.cpp

实现了图的搜索算法

// GraphSearchView.cpp : implementation of the CGraphSearchView class
//

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

#include "MainFrm.h"
#include "GraphSearchDoc.h"
#include "GraphSearchView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CGraphSearchView

IMPLEMENT_DYNCREATE(CGraphSearchView, CView)

BEGIN_MESSAGE_MAP(CGraphSearchView, CView)
	ON_BN_CLICKED(IDC_BUTTON_DFS, OnDFSStart)
	ON_BN_CLICKED(IDC_BUTTON_SHOW_TREE, OnShowTree)
	ON_BN_CLICKED(IDC_BUTTON_SHOW_GRAPH, OnShowGraph)
	ON_BN_CLICKED(IDC_BUTTON_SHOW_SEQUENCE, OnShowSequence)
	ON_BN_CLICKED(IDC_BUTTON_BACK, OnBack)
	//{{AFX_MSG_MAP(CGraphSearchView)
	ON_WM_LBUTTONDOWN()
	ON_WM_LBUTTONUP()
	ON_WM_MOUSEMOVE()
	ON_WM_RBUTTONDOWN()
	ON_WM_RBUTTONUP()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CGraphSearchView construction/destruction

CGraphSearchView::CGraphSearchView()
{
	// TODO: add construction code here
	m_nShowMode = GRAPH_SHOW_NO_INFOR;

	m_nGridRow = 50;
	m_nGridColumn = 50;

	m_nGridLeft = 20;
	m_nGridTop = 20;
	m_nGridWidth = 0;
	m_nGridHeight = 0;

	m_bInsertEdgeFrom = FALSE;
	m_bDeleteEdgeFrom = FALSE;

	m_hcurArrow = AfxGetApp()->LoadStandardCursor(IDC_ARROW);
	m_hcurCross = AfxGetApp()->LoadStandardCursor(IDC_CROSS);
	m_hcurHand = AfxGetApp()->LoadCursor(IDC_CURSOR1);
}

CGraphSearchView::~CGraphSearchView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CGraphSearchView drawing

void CGraphSearchView::OnDraw(CDC* pDC)
{
	CGraphSearchDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
	drawGrid(pDC);
	if(pmainframe->m_bShowGraph){
		//显示图
		pmainframe->m_graph.display(pDC, m_nGridLeft, m_nGridTop, m_nGridWidth, m_nGridHeight, 
			m_nGridRow, m_nGridColumn, 0x000000FF, 0x00646464, 1, m_nShowMode);
		if(m_bDeleteEdgeFrom){
			//对于删除操作，显示第一个选择的点
			int x = m_nGridLeft+m_nDeleteEdgeFrom[1]*m_nGridWidth/(m_nGridColumn-1);
			int y = m_nGridTop+m_nDeleteEdgeFrom[0]*m_nGridHeight/(m_nGridRow-1);
			pDC->SelectStockObject(BLACK_PEN);
			pDC->Ellipse(x-4, y-4, x+4, y+4);
		}
	}else{
		//显示搜索的结果
		pmainframe->displaySearchResult(pDC, m_nSearchFrom, pmainframe->m_bShowSearchTree, 
			pmainframe->m_bShowSearchGraph);
		if(pmainframe->m_bShowSearchSequence){
			pmainframe->displayCloseTable(pDC);
		}
	}
	
}

void CGraphSearchView::drawGrid(CDC* pdc)
{
	CRect rect;
	GetClientRect(&rect);
	rect.left = m_nGridLeft;
	rect.top = m_nGridTop;
	rect.right -= m_nGridLeft;
	rect.bottom -= m_nGridTop;
	
	m_nGridWidth = rect.Width();
	m_nGridHeight = rect.Height();

	int i, j ,x, y;
	pdc->SelectStockObject(BLACK_PEN);
	for(i = 0; i<m_nGridColumn; i++){
		for(j = 0; j<m_nGridRow ; j++){
			x = m_nGridLeft+i*m_nGridWidth/(m_nGridColumn-1);
			y = m_nGridTop+j*m_nGridHeight/(m_nGridRow-1);
			pdc->Ellipse(x-1, y-1, x+1, y+1);
		}
	}
	
	CPen newpen(PS_SOLID, 2, RGB(0, 0, 255));
	pdc->SelectObject(&newpen);
	pdc->MoveTo(m_nGridLeft, m_nGridTop);
	pdc->LineTo(m_nGridLeft+rect.Width(), m_nGridTop);
	pdc->MoveTo(m_nGridLeft, m_nGridTop);
	pdc->LineTo(m_nGridLeft, m_nGridTop+rect.Height());
	pdc->MoveTo(m_nGridLeft, m_nGridTop+rect.Height());
	pdc->LineTo(m_nGridLeft+rect.Width(), m_nGridTop+rect.Height());
	pdc->MoveTo(m_nGridLeft+rect.Width(), m_nGridTop);
	pdc->LineTo(m_nGridLeft+rect.Width(), m_nGridTop+rect.Height());
	pdc->SelectStockObject(BLACK_PEN);
}

/////////////////////////////////////////////////////////////////////////////
// CGraphSearchView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CGraphSearchView message handlers

void CGraphSearchView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	if(point.x>=m_nGridLeft && point.y>=m_nGridTop && 
		point.x<=m_nGridLeft+m_nGridWidth && point.y<=m_nGridTop+m_nGridHeight){
		
		SetCursor(m_hcurHand);
		//求逻辑坐标
		int  coor[2];
		coor[1] = (point.x-m_nGridLeft)*(m_nGridColumn-1)/m_nGridWidth;
		coor[0] = (point.y-m_nGridTop)*(m_nGridRow-1)/m_nGridHeight;
		int cx = m_nGridLeft+coor[1]*m_nGridWidth/(m_nGridColumn-1);
		int cy = m_nGridTop+coor[0]*m_nGridHeight/(m_nGridRow-1);
		int w = m_nGridWidth/(m_nGridColumn-1);
		int h = m_nGridHeight/(m_nGridRow-1);
		float d[4] = {
			abs(point.x-cx)+abs(point.y-cy), abs(point.x - (cx+w))+abs(point.y-cy),
			abs(point.x-cx)+abs(point.y-(cy+h)), abs(point.x - (cx+w))+abs(point.y-(cy+h))
		};
		if(d[1]<d[0] && d[1]<d[2] && d[1]<d[3]){
			coor[1]++;			
		}else if(d[2]<d[0] && d[2]<d[1] && d[2]<d[3]){
			coor[0]++;
		}else if(d[3]<d[0] && d[3]<d[1] && d[3]<d[2]){
			coor[0]++;coor[1]++;
		}
		//进行功能选择
		CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
		switch(pmainframe->m_nFunction){
		case FUN_INSERT_VERTEX:
			pmainframe->m_graph.insertVertex(coor);
			break;
		case FUN_INSERT_EDGE:
			if(!m_bInsertEdgeFrom){
				if(!pmainframe->m_graph.isNewVertex(coor)){
					m_nInsertEdgeFrom[0] = coor[0];
					m_nInsertEdgeFrom[1] = coor[1];
					m_nLastCursorPos[0] = coor[0];
					m_nLastCursorPos[1] = coor[1];
					m_bInsertEdgeFrom = TRUE;
				}
			}else if(m_bInsertEdgeFrom && m_nInsertEdgeFrom[0] == coor[0] && m_nInsertEdgeFrom[1] == coor[1]){
				return;
			}else{
				if(!pmainframe->m_graph.isNewVertex(coor)){
					m_bInsertEdgeFrom = FALSE;
					pmainframe->m_graph.insertEdge(m_nInsertEdgeFrom, coor);
				}
			}
			break;
		case FUN_DELETE_VERTEX:
			pmainframe->m_graph.deleteVertex(coor);
			break;
		case FUN_DELETE_EDGE:
			if(m_bDeleteEdgeFrom){
				m_bDeleteEdgeFrom = FALSE;
				pmainframe->m_graph.deleteEdge(m_nDeleteEdgeFrom, coor);
			}else{
				m_bDeleteEdgeFrom = TRUE;
				m_nDeleteEdgeFrom[0] = coor[0];
				m_nDeleteEdgeFrom[1] = coor[1];
			}
			break;
		}
		Invalidate();
	}else{
		SetCursor(m_hcurArrow);
	}
	
	CView::OnLButtonDown(nFlags, point);
}

void CGraphSearchView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	if(point.x>=m_nGridLeft && point.y>=m_nGridTop && 
		point.x<=m_nGridLeft+m_nGridWidth && point.y<=m_nGridTop+m_nGridHeight){
		SetCursor(m_hcurHand);
	}else{
		SetCursor(m_hcurArrow);
	}

	CView::OnLButtonUp(nFlags, point);
}

void CGraphSearchView::OnMouseMove(UINT nFlags, CPoint point) 
{
	if(point.x>=m_nGridLeft && point.y>=m_nGridTop && 
		point.x<=m_nGridLeft+m_nGridWidth && point.y<=m_nGridTop+m_nGridHeight){
		
		SetCursor(m_hcurHand);
		//如果没有点击鼠标左键则直接返回
		if(!m_bInsertEdgeFrom){
			return;
		}
		//求逻辑坐标
		int  coor[2];
		coor[1] = (point.x-m_nGridLeft)*(m_nGridColumn-1)/m_nGridWidth;
		coor[0] = (point.y-m_nGridTop)*(m_nGridRow-1)/m_nGridHeight;
		int cx = m_nGridLeft+coor[1]*m_nGridWidth/(m_nGridColumn-1);
		int cy = m_nGridTop+coor[0]*m_nGridHeight/(m_nGridRow-1);
		int w = m_nGridWidth/(m_nGridColumn-1);
		int h = m_nGridHeight/(m_nGridRow-1);
		float d[4] = {
			abs(point.x-cx)+abs(point.y-cy), abs(point.x - (cx+w))+abs(point.y-cy),
			abs(point.x-cx)+abs(point.y-(cy+h)), abs(point.x - (cx+w))+abs(point.y-(cy+h))
		};
		if(d[1]<d[0] && d[1]<d[2] && d[1]<d[3]){
			coor[1]++;			
		}else if(d[2]<d[0] && d[2]<d[1] && d[2]<d[3]){
			coor[0]++;
		}else if(d[3]<d[0] && d[3]<d[1] && d[3]<d[2]){
			coor[0]++;coor[1]++;
		}
		//进行功能选择
		CClientDC dc(this);
		CPen whitepen(PS_SOLID,2,RGB(255, 255, 255));
		CPen graypen(PS_SOLID, 2, RGB(100, 100, 100));

		CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
		int x1, y1, x2, y2, x3, y3;
		switch(pmainframe->m_nFunction){
		case FUN_INSERT_EDGE:
			x1 = m_nGridLeft+m_nInsertEdgeFrom[1]*m_nGridWidth/(m_nGridColumn-1);
			y1 = m_nGridTop+m_nInsertEdgeFrom[0]*m_nGridHeight/(m_nGridRow-1);
			x2 = m_nGridLeft+m_nLastCursorPos[1]*m_nGridWidth/(m_nGridColumn-1);
			y2 = m_nGridTop+m_nLastCursorPos[0]*m_nGridHeight/(m_nGridRow-1);
			x3 = m_nGridLeft+coor[1]*m_nGridWidth/(m_nGridColumn-1);
			y3 = m_nGridTop+coor[0]*m_nGridHeight/(m_nGridRow-1);

			dc.SelectObject(&whitepen);
			dc.MoveTo(x1, y1);
			dc.LineTo(x2, y2);
			
			dc.SelectObject(&graypen);
			dc.MoveTo(x1, y1);
			dc.LineTo(x3, y3);

			m_nLastCursorPos[0] = coor[0];
			m_nLastCursorPos[1] = coor[1];

			dc.SelectStockObject(BLACK_PEN);
			drawGrid(&dc);
			pmainframe->m_graph.display(&dc, m_nGridLeft, m_nGridTop, m_nGridWidth, m_nGridHeight, 
				m_nGridRow, m_nGridColumn, 0x000000FF, 0x00646464, 1, m_nShowMode);
			break;
		}
	}else{
		SetCursor(m_hcurArrow);
	}

	CView::OnMouseMove(nFlags, point);
}

void CGraphSearchView::OnRButtonDown(UINT nFlags, CPoint point) 
{
	if(point.x>=m_nGridLeft && point.y>=m_nGridTop && 
		point.x<=m_nGridLeft+m_nGridWidth && point.y<=m_nGridTop+m_nGridHeight){

		SetCursor(m_hcurHand);
		CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
		switch(pmainframe->m_nFunction){
		case FUN_INSERT_EDGE:
			m_bInsertEdgeFrom = FALSE;
			Invalidate();
			break;
		case FUN_DELETE_EDGE:
			m_bDeleteEdgeFrom = FALSE;
			Invalidate();
			break;
		}
	}else{
		SetCursor(m_hcurArrow);
	}

	CView::OnRButtonDown(nFlags, point);
}

void CGraphSearchView::OnRButtonUp(UINT nFlags, CPoint point) 
{
	if(point.x>=m_nGridLeft && point.y>=m_nGridTop && 
		point.x<=m_nGridLeft+m_nGridWidth && point.y<=m_nGridTop+m_nGridHeight){

		SetCursor(m_hcurHand);
	}else{
		SetCursor(m_hcurArrow);
	}
	CView::OnRButtonUp(nFlags, point);
}

//////////////////////////////////////////////////////////////////////////
void CGraphSearchView::OnDFSStart()
{
	CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
	
	CString str;
	pmainframe->m_wndDFSBar.m_editStart.GetWindowText(str);
	int start = -1, end = -1;
	if(str.GetLength()>0){
		start = atoi(str);
	}
	pmainframe->m_wndDFSBar.m_editEnd.GetWindowText(str);
	if(str.GetLength()>0){
		end = atoi(str);
	}

	if(start >=0 && end >=0 &&
		start < pmainframe->m_graph.m_nVertexNum && end < pmainframe->m_graph.m_nVertexNum){
		switch(pmainframe->m_nFunction){
		case FUN_DFS:
			//DFS搜索过程
			if(pmainframe->m_graph.DFS(start, end, pmainframe->m_tree)){
				//寻找搜索的起点
				VerNode* pv = pmainframe->m_graph.m_vertexs[end];
				m_nSearchFrom[0] = pv->m_nCoor[0];
				m_nSearchFrom[1] = pv->m_nCoor[1];
				//更新视图
				pmainframe->m_bShowGraph = FALSE;
				//更新搜索的结果
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				pmainframe->insertSearchResult();
			}else{
				//此次搜索失败，清空搜索树以及搜索结果
				pmainframe->m_tree.clear();
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				AfxMessageBox("节点间不可达");	
			}
			Invalidate();
			break;
		case FUN_BFS:
			//BFS搜索过程
			if(pmainframe->m_graph.BFS(start, end, pmainframe->m_tree)){
				//寻找搜索的起点
				VerNode* pv = pmainframe->m_graph.m_vertexs[end];
				m_nSearchFrom[0] = pv->m_nCoor[0];
				m_nSearchFrom[1] = pv->m_nCoor[1];
				//更新视图
				pmainframe->m_bShowGraph = FALSE;
				//更新搜索的结果
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				pmainframe->insertSearchResult();
			}else{
				//此次搜索失败，清空搜索树以及搜索结果
				pmainframe->m_tree.clear();
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				AfxMessageBox("节点间不可达");	
			}
			Invalidate();
			break;
		case FUN_DIJKSTRA:
			//Dijkstra搜索算法
			if(pmainframe->m_graph.Dijkstra(start, end, pmainframe->m_tree)){
				//寻找搜索的起点
				VerNode* pv = pmainframe->m_graph.m_vertexs[end];
				m_nSearchFrom[0] = pv->m_nCoor[0];
				m_nSearchFrom[1] = pv->m_nCoor[1];
				//更新视图
				pmainframe->m_bShowGraph = FALSE;
				//更新搜索的结果
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				pmainframe->insertSearchResult();
			}else{
				//此次搜索失败，清空搜索树以及搜索结果
				pmainframe->m_tree.clear();
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				AfxMessageBox("节点间不可达");	
			}
			Invalidate();
			break;
		case FUN_A_STAR:
			//A*搜索算法
			if(pmainframe->m_graph.A_star(start, end, pmainframe->m_tree)){
				//寻找搜索的起点
				VerNode* pv = pmainframe->m_graph.m_vertexs[end];
				m_nSearchFrom[0] = pv->m_nCoor[0];
				m_nSearchFrom[1] = pv->m_nCoor[1];
				//更新视图
				pmainframe->m_bShowGraph = FALSE;
				//更新搜索的结果
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				pmainframe->insertSearchResult();
			}else{
				//此次搜索失败，清空搜索树以及搜索结果
				pmainframe->m_tree.clear();
				pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
				AfxMessageBox("节点间不可达");	
			}
			Invalidate();
			break;
		}
	}else{
		AfxMessageBox("搜索节点参数不正确");
	}
}

void CGraphSearchView::OnShowTree()
{
	CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
	if(pmainframe->m_tree.m_nVertexNum>0){
		pmainframe->m_bShowSearchTree = !pmainframe->m_bShowSearchTree;
		Invalidate();
	}
}

void CGraphSearchView::OnShowGraph()
{
	CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
	if(pmainframe->m_tree.m_nVertexNum>0){
		pmainframe->m_bShowSearchGraph = !pmainframe->m_bShowSearchGraph;
		Invalidate();
	}
}

void CGraphSearchView::OnShowSequence()
{
	CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
	if(pmainframe->m_tree.m_nVertexNum>0){
		pmainframe->m_bShowSearchSequence = !pmainframe->m_bShowSearchSequence;
		Invalidate();
	}
}

void CGraphSearchView::OnBack()
{
	CMainFrame* pmainframe = (CMainFrame*)AfxGetMainWnd();
	//清空搜索的结果
	pmainframe->m_tree.clear();
	pmainframe->m_wndDFSBar.m_list.DeleteAllItems();
	//关闭搜索界面
	pmainframe->m_wndDFSBar.ShowWindow(FALSE);
	pmainframe->RecalcLayout();
	//将功能开关置为插入节点
	pmainframe->m_nFunction = FUN_INSERT_VERTEX;
	//显示原图
	pmainframe->m_bShowGraph = TRUE;
	Invalidate();
}