mainfrm.cpp

实现了图的搜索算法

// MainFrm.cpp : implementation of the CMainFrame 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

/////////////////////////////////////////////////////////////////////////////
// CMainFrame

IMPLEMENT_DYNCREATE(CMainFrame, CFrameWnd)

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
	//{{AFX_MSG_MAP(CMainFrame)
	ON_WM_CREATE()
	ON_COMMAND(ID_NEW_GRAPH, OnNewGraph)
	ON_COMMAND(ID_SAVE_GRAPH, OnSaveGraph)
	ON_COMMAND(ID_OPEN_GRAPH, OnOpenGraph)
	ON_COMMAND(ID_INSERT_VERTEX, OnInsertVertex)
	ON_COMMAND(ID_INSERT_EDGE, OnInsertEdge)
	ON_COMMAND(ID_DELETE_VERTEX, OnDeleteVertex)
	ON_COMMAND(ID_DELETE_EDGE, OnDeleteEdge)
	ON_UPDATE_COMMAND_UI(ID_INSERT_VERTEX, OnUpdateInsertVertex)
	ON_UPDATE_COMMAND_UI(ID_INSERT_EDGE, OnUpdateInsertEdge)
	ON_UPDATE_COMMAND_UI(ID_DELETE_VERTEX, OnUpdateDeleteVertex)
	ON_UPDATE_COMMAND_UI(ID_DELETE_EDGE, OnUpdateDeleteEdge)
	ON_COMMAND(ID_BFS, OnBfs)
	ON_UPDATE_COMMAND_UI(ID_BFS, OnUpdateBfs)
	ON_COMMAND(ID_DFS, OnDfs)
	ON_UPDATE_COMMAND_UI(ID_DFS, OnUpdateDfs)
	ON_COMMAND(ID_DIJKSTRA, OnDijkstra)
	ON_UPDATE_COMMAND_UI(ID_DIJKSTRA, OnUpdateDijkstra)
	ON_COMMAND(ID_EDGE_INFOR, OnEdgeInfor)
	ON_UPDATE_COMMAND_UI(ID_EDGE_INFOR, OnUpdateEdgeInfor)
	ON_COMMAND(ID_VERTEX_INFOR, OnVertexInfor)
	ON_UPDATE_COMMAND_UI(ID_VERTEX_INFOR, OnUpdateVertexInfor)
	ON_COMMAND(ID_A_STAR, OnAStar)
	ON_UPDATE_COMMAND_UI(ID_A_STAR, OnUpdateAStar)
	ON_UPDATE_COMMAND_UI(ID_NEW_GRAPH, OnUpdateNewGraph)
	ON_UPDATE_COMMAND_UI(ID_SAVE_GRAPH, OnUpdateSaveGraph)
	ON_UPDATE_COMMAND_UI(ID_OPEN_GRAPH, OnUpdateOpenGraph)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

static UINT indicators[] =
{
	ID_SEPARATOR,           // status line indicator
	ID_INDICATOR_CAPS,
	ID_INDICATOR_NUM,
	ID_INDICATOR_SCRL,
};

/////////////////////////////////////////////////////////////////////////////
// CMainFrame construction/destruction

CMainFrame::CMainFrame()
{
	m_nFunction = FUN_INSERT_VERTEX;
	m_bShowVertexInfor = FALSE;
	m_bShowEdgeInfor = FALSE;

	m_bShowGraph = TRUE;

	m_bShowSearchTree = TRUE;
	m_bShowSearchGraph = TRUE;
	m_bShowSearchSequence = FALSE;
}

CMainFrame::~CMainFrame()
{
	m_nFunction = FUN_INSERT_VERTEX;
}

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
	if (CFrameWnd::OnCreate(lpCreateStruct) == -1)
		return -1;
	
	if (!m_wndToolBar.CreateEx(this, TBSTYLE_FLAT, WS_CHILD | WS_VISIBLE | CBRS_TOP
		| CBRS_GRIPPER | CBRS_TOOLTIPS | CBRS_FLYBY | CBRS_SIZE_DYNAMIC) ||
		!m_wndToolBar.LoadToolBar(IDR_MAINFRAME))
	{
		TRACE0("Failed to create toolbar\n");
		return -1;      // fail to create
	}

	if (!m_wndStatusBar.Create(this) ||
		!m_wndStatusBar.SetIndicators(indicators,
		  sizeof(indicators)/sizeof(UINT)))
	{
		TRACE0("Failed to create status bar\n");
		return -1;      // fail to create
	}

	// TODO: Delete these three lines if you don't want the toolbar to
	//  be dockable
	m_wndToolBar.EnableDocking(CBRS_ALIGN_ANY);
	EnableDocking(CBRS_ALIGN_ANY);
	DockControlBar(&m_wndToolBar);

	//////////////////////////////////////////////////////////////////////////
	//create the bar ctrl
	if(!m_wndDFSBar.Create(this,IDD_DLG_BAR,WS_CHILD | WS_VISIBLE | CBRS_RIGHT |
		CBRS_GRIPPER | CBRS_TOOLTIPS | CBRS_FLYBY | CBRS_SIZE_DYNAMIC,IDD_DLG_BAR)){
		TRACE0("Failed to create progress bar.\n");
		return -1;
	}
	m_wndDFSBar.ShowWindow(SW_HIDE);

	return 0;
}

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
	if( !CFrameWnd::PreCreateWindow(cs) )
		return FALSE;
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	cs.style = WS_OVERLAPPED | WS_CAPTION | FWS_ADDTOTITLE
		| WS_THICKFRAME | WS_SYSMENU | WS_MINIMIZEBOX | WS_MAXIMIZEBOX | WS_MAXIMIZE;

	return TRUE;
}

/////////////////////////////////////////////////////////////////////////////
// CMainFrame diagnostics

#ifdef _DEBUG
void CMainFrame::AssertValid() const
{
	CFrameWnd::AssertValid();
}

void CMainFrame::Dump(CDumpContext& dc) const
{
	CFrameWnd::Dump(dc);
}

#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMainFrame message handlers


void CMainFrame::OnNewGraph() 
{
	m_graph.clear();	
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	pview->Invalidate();
}

void CMainFrame::OnSaveGraph() 
{
	CFileDialog dlg(FALSE, "g", "graph", OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,
					"Graph Files (*.g)|*.g", NULL);
	if(dlg.DoModal() == IDOK){
		CString name = dlg.GetFileName();
		FILE *file;
		if((file = fopen(name,"wb"))==NULL)
		{
			AfxMessageBox("Cannot open file.");
			exit(1);
		}

		m_graph.save(file);
		
		fclose(file);
	}
}

void CMainFrame::OnOpenGraph() 
{
	CFileDialog dlg(TRUE, NULL, NULL, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,
		"Graph Files (*.g)|*.g", NULL);
	if(dlg.DoModal() == IDOK){
		CString name = dlg.GetPathName();
		FILE *file;
		if((file=fopen(name,"rb"))==NULL)
		{
			AfxMessageBox("Cannot open file.");
			exit(1);
		}

		m_graph.load(file);
		CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
		pview->Invalidate();
		
		fclose(file);
	}
}

void CMainFrame::OnInsertVertex() 
{
	m_nFunction = FUN_INSERT_VERTEX;	
}

void CMainFrame::OnInsertEdge() 
{
	m_nFunction = FUN_INSERT_EDGE;
}

void CMainFrame::OnDeleteVertex() 
{
	m_nFunction = FUN_DELETE_VERTEX;
}

void CMainFrame::OnDeleteEdge() 
{
	m_nFunction = FUN_DELETE_EDGE;
}

void CMainFrame::OnVertexInfor() 
{
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	m_bShowVertexInfor = !m_bShowVertexInfor;
	if(m_bShowVertexInfor && m_bShowEdgeInfor){
		pview->m_nShowMode = GRAPH_SHOW_ALL_INFOR;
	}else if(m_bShowVertexInfor && !m_bShowEdgeInfor){
		pview->m_nShowMode = GRAPH_SHOW_VERTEX_INFOR;
	}else if(!m_bShowVertexInfor && m_bShowEdgeInfor){
		pview->m_nShowMode = GRAPH_SHOW_EDGE_INFOR;
	}else{
		pview->m_nShowMode = GRAPH_SHOW_NO_INFOR;
	}
	pview->Invalidate();
}

void CMainFrame::OnEdgeInfor() 
{
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	m_bShowEdgeInfor = !m_bShowEdgeInfor;
	if(m_bShowVertexInfor && m_bShowEdgeInfor){
		pview->m_nShowMode = GRAPH_SHOW_ALL_INFOR;
	}else if(m_bShowVertexInfor && !m_bShowEdgeInfor){
		pview->m_nShowMode = GRAPH_SHOW_VERTEX_INFOR;
	}else if(!m_bShowVertexInfor && m_bShowEdgeInfor){
		pview->m_nShowMode = GRAPH_SHOW_EDGE_INFOR;
	}else{
		pview->m_nShowMode = GRAPH_SHOW_NO_INFOR;
	}
	pview->Invalidate();
}

void CMainFrame::OnDfs() 
{
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	m_nFunction = FUN_DFS;
	//显示搜索界面
	m_wndDFSBar.init("深度优先搜索");
	m_wndDFSBar.ShowWindow(SW_SHOW);
	RecalcLayout();
	//清空以前的搜索结果
	m_tree.clear();
	m_wndDFSBar.m_list.DeleteAllItems();
	//更新视图
	m_bShowGraph = TRUE;
	pview->Invalidate();
}

void CMainFrame::OnBfs() 
{
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	m_nFunction = FUN_BFS;
	//显示搜索界面
	m_wndDFSBar.init("广度优先搜索");
	m_wndDFSBar.ShowWindow(SW_SHOW);
	RecalcLayout();
	//清空以前的搜索结果
	m_tree.clear();
	m_wndDFSBar.m_list.DeleteAllItems();
	//更新视图
	m_bShowGraph = TRUE;
	pview->Invalidate();
}

void CMainFrame::OnDijkstra() 
{
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	m_nFunction = FUN_DIJKSTRA;
	//显示搜索界面
	m_wndDFSBar.init("Dijkstra搜索算法");
	m_wndDFSBar.ShowWindow(SW_SHOW);
	RecalcLayout();
	//清空以前的搜索结果
	m_tree.clear();
	m_wndDFSBar.m_list.DeleteAllItems();
	//更新视图
	m_bShowGraph = TRUE;
	pview->Invalidate();
}

void CMainFrame::OnAStar() 
{
	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	m_nFunction = FUN_A_STAR;
	//显示搜索界面
	m_wndDFSBar.init("A*搜索算法");
	m_wndDFSBar.ShowWindow(SW_SHOW);
	RecalcLayout();
	//清空以前的搜索结果
	m_tree.clear();
	m_wndDFSBar.m_list.DeleteAllItems();
	//更新视图
	m_bShowGraph = TRUE;
	pview->Invalidate();
}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void CMainFrame::OnUpdateInsertVertex(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else{
		pCmdUI->Enable(TRUE);
		pCmdUI->SetCheck(m_nFunction == FUN_INSERT_VERTEX);
	}
}

void CMainFrame::OnUpdateInsertEdge(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else{
		pCmdUI->Enable(TRUE);
		pCmdUI->SetCheck(m_nFunction == FUN_INSERT_EDGE);
	}
}

void CMainFrame::OnUpdateDeleteVertex(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else if(m_graph.m_nVertexNum>0){
		pCmdUI->Enable(TRUE);
		pCmdUI->SetCheck(m_nFunction == FUN_DELETE_VERTEX);
	}else{
		pCmdUI->Enable(FALSE);
	}
}

void CMainFrame::OnUpdateDeleteEdge(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else if(m_graph.m_nEdgeNum>0){
		pCmdUI->Enable(TRUE);
		pCmdUI->SetCheck(m_nFunction == FUN_DELETE_EDGE);
	}else{
		pCmdUI->Enable(FALSE);
	}
}

void CMainFrame::OnUpdateVertexInfor(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_bShowVertexInfor);
}

void CMainFrame::OnUpdateEdgeInfor(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_bShowEdgeInfor);
	
}

void CMainFrame::OnUpdateDfs(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_nFunction == FUN_DFS);	
}

void CMainFrame::OnUpdateBfs(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_nFunction == FUN_BFS);	
}

void CMainFrame::OnUpdateDijkstra(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_nFunction == FUN_DIJKSTRA);		
}


void CMainFrame::OnUpdateAStar(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_nFunction == FUN_A_STAR);
}

void CMainFrame::OnUpdateNewGraph(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else{
		pCmdUI->Enable(TRUE);
	}
}

void CMainFrame::OnUpdateSaveGraph(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else{
		pCmdUI->Enable(TRUE);
	}
}

void CMainFrame::OnUpdateOpenGraph(CCmdUI* pCmdUI) 
{
	if(m_nFunction == FUN_DFS || m_nFunction == FUN_BFS ||
		m_nFunction == FUN_DIJKSTRA || m_nFunction == FUN_A_STAR){
		pCmdUI->Enable(FALSE);
	}else{
		pCmdUI->Enable(TRUE);
	}
}

//////////////////////////////////////////////////////////////////////////
void CMainFrame::displaySearchResult(CDC* pdc, int* coor, BOOL bTree, BOOL bGraph)
{
	int end = m_tree.getVertexID(coor);
	VerNode* pv = NULL;
	EdgeNode* pe = NULL;
	CPen pen(PS_SOLID, 3, RGB(255, 0, 0));
	CBrush brush(RGB(255, 0, 0));	

	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	int left = pview->m_nGridLeft;
	int top  = pview->m_nGridTop;
	int width = pview->m_nGridWidth;
	int height = pview->m_nGridHeight;
	int row = pview->m_nGridRow;
	int column = pview->m_nGridColumn;
	
	//显示输入的原始图
	if(bGraph){
		m_graph.display(pdc, left, top, width, height, row, column, 
			0x000000FF, 0x00646464, 1, pview->m_nShowMode);
	}

	if(end>=0){
		//显示搜索树
		if(bTree){
			m_tree.display(pdc, left, top, width, height, row, column, 
				0x00FF0000, 0x00FF0000, 2, GRAPH_SHOW_NO_INFOR);
		}
		//显示搜索路径
		pdc->SelectObject(&pen);
		pdc->SelectObject(&brush);
		pv = m_tree.m_vertexs[end];
		int coor1[2], coor2[2];
		while(pv){
			coor2[0] = left+pv->m_nCoor[1]*width/(column-1);
			coor2[1] = top+pv->m_nCoor[0]*height/(row-1);
			pdc->Ellipse(coor2[0]-4, coor2[1]-4, coor2[0]+4, coor2[1]+4);

			if(pv->m_edgeIn.size()>0){
				pe = pv->m_edgeIn[0];
				pv = pe->m_pVerFrom;
				coor1[0] = left+pv->m_nCoor[1]*width/(column-1);
				coor1[1] = top+pv->m_nCoor[0]*height/(row-1);
				m_graph.drawArrow(pdc, coor1, coor2, 0x000000FF, 3);
			}else{
				break;
			}
		}
	}

	pdc->SelectStockObject(BLACK_PEN);
	pdc->SelectStockObject(BLACK_BRUSH);
}

void CMainFrame::displayCloseTable(CDC* pdc)
{
	int size = m_graph.m_close.size();
	VerNode *pv = NULL;
	
	CPen pen(PS_SOLID, 3, RGB(255, 0, 0));
	pdc->SelectObject(&pen);
	pdc->SelectStockObject(WHITE_BRUSH);
	int alignPos = pdc->GetTextAlign();
	pdc->SetTextAlign(TA_CENTER);

	CGraphSearchView* pview = (CGraphSearchView*)GetActiveView();
	int left = pview->m_nGridLeft;
	int top  = pview->m_nGridTop;
	int width = pview->m_nGridWidth;
	int height = pview->m_nGridHeight;
	int row = pview->m_nGridRow;
	int column = pview->m_nGridColumn;
	int x, y, n;
	CString str;

	for(int i = 0; i<size; i++){
		n = m_graph.m_close[i];
		pv = m_graph.m_vertexs[n];

		x = left+pv->m_nCoor[1]*width/(column-1);
		y = top+pv->m_nCoor[0]*height/(row-1);
		
		//显示图的节点信息
		pdc->Ellipse(x-15, y-15, x+15, y+15);
		str.Format("%d", i);
		pdc->TextOut(x, y-7, str);
	}

	pdc->SelectStockObject(BLACK_PEN);
	pdc->SetTextAlign(alignPos);
}

void CMainFrame::insertSearchResult()
{
	int size = m_graph.m_close.size();
	int n;
	CString str;
	for(int i = 0; i<size; i++){
		n = m_graph.m_close[i];

		str.Format("%d", i);
		m_wndDFSBar.m_list.InsertItem(i, str);
		str.Format("%d", n);
		m_wndDFSBar.m_list.SetItemText(i, 1, str);
	}
}