dialogdis.cpp

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

// DialogDis.cpp : implementation file
//

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

#include "graphDoc.h"
#include "DialogDis.h"

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

/////////////////////////////////////////////////////////////////////////////
// CDialogDis

IMPLEMENT_DYNCREATE(CDialogDis, CFormView)

CDialogDis::CDialogDis()
	: CFormView(CDialogDis::IDD)
{
	//{{AFX_DATA_INIT(CDialogDis)
	m_narc = 0;
	m_nlink = 0;
	m_nvertex = 0;
	m_strdfsname = _T("");
	m_strbfsname = _T("");
	m_nyouarc = 0;
	m_nyouvertex = 0;
	//}}AFX_DATA_INIT
	m_ndfs = 0;
	m_nbfs = 0;
}

CDialogDis::~CDialogDis()
{
}

void CDialogDis::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDialogDis)
	DDX_Text(pDX, IDC_ARCS, m_narc);
	DDX_Text(pDX, IDC_LINKS, m_nlink);
	DDX_Text(pDX, IDC_VERTEXS, m_nvertex);
	DDX_Text(pDX, IDC_DFS_NAME, m_strdfsname);
	DDX_Text(pDX, IDC_BFS_NAME, m_strbfsname);
	DDX_Text(pDX, IDC_YOU_ARCS, m_nyouarc);
	DDX_Text(pDX, IDC_YOU_VERTEXS, m_nyouvertex);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CDialogDis, CFormView)
	//{{AFX_MSG_MAP(CDialogDis)
	ON_BN_CLICKED(IDC_DFS_START, OnDfsStart)
	ON_BN_CLICKED(IDC_DFS_NEXT, OnDfsNext)
	ON_BN_CLICKED(IDC_ALL_VERTEX, OnAllVertex)
	ON_BN_CLICKED(IDC_BFS_NEXT, OnBfsNext)
	ON_BN_CLICKED(IDC_BFS_START, OnBfsStart)
	ON_BN_CLICKED(IDC_YOU_ALL, OnYouAll)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDialogDis diagnostics

#ifdef _DEBUG
void CDialogDis::AssertValid() const
{
	CFormView::AssertValid();
}

void CDialogDis::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CDialogDis message handlers

CGraphDoc* CDialogDis::GetDocument()
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CGraphDoc)));
	return (CGraphDoc*)m_pDocument;
}

void CDialogDis::OnUpdate(CView* pSender, LPARAM lHint, CObject* pHint) 
{
	CGraphDoc* pdoc = GetDocument();
	if(pdoc->m_ntype){
		m_narc = pdoc->m_graph.m_narc/2;
		m_nvertex = pdoc->m_queue.m_nnum;
		pdoc->m_graph.DFSTraverse();
		m_nlink = pdoc->m_graph.m_nunit;
	}
	else{
		m_nyouarc = pdoc->m_graph.m_narc;
		m_nyouvertex = pdoc->m_queue.m_nnum;
	}
	m_strdfsname = "";
	m_strbfsname = "";
	UpdateData(FALSE);

	CButton* pbutton1 = (CButton*)GetDlgItem(IDC_DFS_START);
	CButton* pbutton2 = (CButton*)GetDlgItem(IDC_BFS_START);
	CButton* pbutton3 = (CButton*)GetDlgItem(IDC_ALL_VERTEX);
	CButton* pbutton4 = (CButton*)GetDlgItem(IDC_YOU_ALL);

	pbutton1->EnableWindow(pdoc->m_queue.m_nnum);
	pbutton2->EnableWindow(pdoc->m_queue.m_nnum);
	if(pdoc->m_ntype){
		pbutton3->EnableWindow(TRUE);
		pbutton4->EnableWindow(FALSE);
	}
	else{
		pbutton3->EnableWindow(FALSE);
		pbutton4->EnableWindow(TRUE);
	}
}

void CDialogDis::OnDfsStart() 
{
	CGraphDoc* pdoc = GetDocument();
	SetDlgItemText(IDC_DFS_NEXT,"下个结点");
	
	pdoc->m_ndisplay = 0;
	pdoc->UpdateAllViews(this);

	pdoc->m_graph.DFSTraverse();
	m_strdfsname = pdoc->m_graph.m_verqueue->m_phead->m_strname;
	pdoc->m_ndisplay = 1;
	pdoc->m_pviewvernode = pdoc->m_graph.m_verqueue->m_phead;
	UpdateData(FALSE);
	pdoc->UpdateAllViews(this);

	CButton* pbutton = (CButton*)GetDlgItem(IDC_DFS_NEXT);
	if(pdoc->m_queue.m_nnum != 1)
		pbutton->EnableWindow(TRUE);

	m_ndfs = 1;
}

void CDialogDis::OnDfsNext() 
{
	CGraphDoc* pdoc = GetDocument();
	CButton* pbutton = (CButton*)GetDlgItem(IDC_DFS_NEXT);
	m_ndfs++;
	if(pdoc->m_ndisplay == 0){
		pbutton->EnableWindow(FALSE);
		pdoc->UpdateAllViews(this);
	
	}
	else{
		for(VerNode* pnode = pdoc->m_queue.m_phead;pnode;pnode = pnode->m_pnextver){
			if(m_ndfs == pnode->m_nvisit){
				m_strdfsname = pnode->m_strname;
				pdoc->m_pviewvernode = pnode;
				UpdateData(FALSE);
				pdoc->UpdateAllViews(this);
			}
		}
		if(m_ndfs == pdoc->m_queue.m_nnum){
			SetDlgItemText(IDC_DFS_NEXT,"完成");
			pdoc->m_ndisplay = 0;
		}
	}
}

void CDialogDis::OnInitialUpdate() 
{
	CFormView::OnInitialUpdate();
	
	CButton* pbutton1 = (CButton*)GetDlgItem(IDC_DFS_NEXT);
	CButton* pbutton2 = (CButton*)GetDlgItem(IDC_DFS_START);
	CButton* pbutton3 = (CButton*)GetDlgItem(IDC_BFS_NEXT);
	CButton* pbutton4 = (CButton*)GetDlgItem(IDC_BFS_START);

	pbutton1->EnableWindow(FALSE);
	pbutton2->EnableWindow(FALSE);
	pbutton3->EnableWindow(FALSE);
	pbutton4->EnableWindow(FALSE);
}

void CDialogDis::OnAllVertex() 
{
	CGraphDoc* pdoc = GetDocument();
	pdoc->m_ndisplay = 2;
	pdoc->UpdateAllViews(this);
	
}

void CDialogDis::OnBfsNext() 
{
	CGraphDoc* pdoc = GetDocument();
	CButton* pbutton = (CButton*)GetDlgItem(IDC_BFS_NEXT);
	m_nbfs++;
	if(pdoc->m_ndisplay == 5){
		pbutton->EnableWindow(FALSE);
		pdoc->UpdateAllViews(this);
	
	}
	else{
		for(VerNode* pnode = pdoc->m_queue.m_phead;pnode;pnode = pnode->m_pnextver){
			if(m_nbfs == pnode->m_nvisit){
				m_strbfsname = pnode->m_strname;
				pdoc->m_pviewvernode = pnode;
				UpdateData(FALSE);
				pdoc->UpdateAllViews(this);
			}
		}
		if(m_nbfs == pdoc->m_queue.m_nnum){
			SetDlgItemText(IDC_BFS_NEXT,"完成");
			pdoc->m_ndisplay = 5;
		}
	}
	
}

void CDialogDis::OnBfsStart() 
{
	CGraphDoc* pdoc = GetDocument();
	SetDlgItemText(IDC_BFS_NEXT,"下个结点");
	
	pdoc->m_ndisplay = 5;
	pdoc->UpdateAllViews(this);

	pdoc->m_graph.BFSTraverse();
	m_strbfsname = pdoc->m_graph.m_verqueue->m_phead->m_strname;
	pdoc->m_ndisplay = 1;
	pdoc->m_pviewvernode = pdoc->m_graph.m_verqueue->m_phead;
	UpdateData(FALSE);
	pdoc->UpdateAllViews(this);

	CButton* pbutton = (CButton*)GetDlgItem(IDC_BFS_NEXT);
	if(pdoc->m_queue.m_nnum != 1)
		pbutton->EnableWindow(TRUE);

	m_nbfs = 1;

	
}

void CDialogDis::OnYouAll() 
{
	CGraphDoc* pdoc = GetDocument();
	pdoc->m_ndisplay = 6;
	pdoc->UpdateAllViews(this);
	
}