dijkstratestview.cpp

Dijkstra算法及demo实现

// DijkstraTestView.cpp : CDijkstraTestView 类的实现
//

#include "stdafx.h"
#include "DijkstraTest.h"
#include "MainFrm.h"
#include "DijkstraTestDoc.h"
#include "DijkstraTestView.h"
#include "DijkstraSearch.h"
#include ".\dijkstratestview.h"
#include "MidReader.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

static MemSearchObject  s_MemObject[204800];
static long             s_MemObjectCount=0;
static SearchObjectList s_SearchResult;

// CDijkstraTestView

IMPLEMENT_DYNCREATE(CDijkstraTestView, CView)

BEGIN_MESSAGE_MAP(CDijkstraTestView, CView)
	// 标准打印命令
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
	ON_COMMAND(IDM_SEARCH, OnSearch)
	ON_COMMAND(IDM_ENDSEARCH, OnEndsearch)
	ON_COMMAND(IDM_RANDNODE, OnRandnode)
	ON_COMMAND(IDM_SAVERESULT, OnSaveresult)
END_MESSAGE_MAP()

// CDijkstraTestView 构造/析构

void MemConnect(int i,int j)
{
	CDijkstraSearch::ConnectObject(&s_MemObject[i],&s_MemObject[j]);
}

CDijkstraTestView::CDijkstraTestView()
{
	// TODO: 在此处添加构造代码
	/*
	s_MemObject[0].m_OwnerObject.x=50;
	s_MemObject[0].m_OwnerObject.y=50;
	
	s_MemObject[1].m_OwnerObject.x=100;
	s_MemObject[1].m_OwnerObject.y=100;

	s_MemObject[2].m_OwnerObject.x=200;
	s_MemObject[2].m_OwnerObject.y=100;

	s_MemObject[3].m_OwnerObject.x=350;
	s_MemObject[3].m_OwnerObject.y=100;

	s_MemObject[4].m_OwnerObject.x=100;
	s_MemObject[4].m_OwnerObject.y=200;

	s_MemObject[5].m_OwnerObject.x=250;
	s_MemObject[5].m_OwnerObject.y=200;

	s_MemObject[6].m_OwnerObject.x=450;
	s_MemObject[6].m_OwnerObject.y=250;

	s_MemObject[7].m_OwnerObject.x=150;
	s_MemObject[7].m_OwnerObject.y=300;

	s_MemObject[8].m_OwnerObject.x=350;
	s_MemObject[8].m_OwnerObject.y=300;

	s_MemObject[9].m_OwnerObject.x=200;
	s_MemObject[9].m_OwnerObject.y=350;	

	s_MemObject[10].m_OwnerObject.x=500;
	s_MemObject[10].m_OwnerObject.y=400;

	MemConnect(0,1);
	MemConnect(0,3);
	MemConnect(0,4);

	MemConnect(1,2);
	MemConnect(1,4);

	MemConnect(2,3);
	MemConnect(2,5);

	MemConnect(3,5);
	MemConnect(3,6);

	MemConnect(4,5);
	MemConnect(4,5);

	MemConnect(5,7);
	MemConnect(5,8);
	MemConnect(5,9);

	MemConnect(7,8);
	MemConnect(7,9);

	MemConnect(6,8);
	MemConnect(6,10);

	MemConnect(8,9);
	MemConnect(8,10);

	MemConnect(9,10);

	MemConnect(2,4);
	MemConnect(6,5);

	s_MemObjectCount=11;
	*/
	char szDir[MAX_PATH];
	::GetModuleFileName(NULL,szDir,sizeof(szDir));
	CString strPath=szDir;
	strPath=strPath.Left(strPath.ReverseFind('\\')+1);
	CString strFileName=strPath;

	CMidReader Mid;
	long lLen=Mid.GetObjectLength(strFileName+_T("point.mid"));
	s_MemObjectCount=Mid.ReadPoint(strFileName+_T("point.mid"),s_MemObject,sizeof(s_MemObject)/sizeof(MemSearchObject));
	long lReadLine=Mid.ReadLine(strFileName+_T("point_line.mid"));
}

CDijkstraTestView::~CDijkstraTestView()
{
	s_SearchResult.RemoveAllNode(true);
}

BOOL CDijkstraTestView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: 在此处通过修改 CREATESTRUCT cs 来修改窗口类或
	// 样式

	return CView::PreCreateWindow(cs);
}

// CDijkstraTestView 绘制

void CDijkstraTestView::OnDraw(CDC* pDC)
{
	CDijkstraTestDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	if (!pDoc)
		return;

	// TODO: 在此处为本机数据添加绘制代码
	int d=5;
	for(long i=0;i<s_MemObjectCount;i++)
	{
		pDC->Ellipse(s_MemObject[i].m_OwnerObject.x-d,s_MemObject[i].m_OwnerObject.y-d,s_MemObject[i].m_OwnerObject.x+d,s_MemObject[i].m_OwnerObject.y+d);
	
		int nCount=s_MemObject[i].m_pNextMemObjectList.GetNodeCount();
		MemSearchObject *pObject=NULL;
		for(long j=0;j<nCount;j++)
		{
			pObject=s_MemObject[i].m_pNextMemObjectList.GetNode(j);
			pDC->MoveTo(s_MemObject[i].m_OwnerObject.x,s_MemObject[i].m_OwnerObject.y);
			pDC->LineTo(pObject->m_OwnerObject.x,pObject->m_OwnerObject.y);
		}
	}

	CPen pen1;
	pen1.CreatePen(PS_SOLID,2,RGB(0,0,255));
	CPen *pOldPen=pDC->SelectObject(&pen1);
	pDC->Ellipse(s_MemObject[0].m_OwnerObject.x-d*2,s_MemObject[0].m_OwnerObject.y-d*2,s_MemObject[0].m_OwnerObject.x+d*2,s_MemObject[0].m_OwnerObject.y+d*2);
    pDC->Ellipse(s_MemObject[s_MemObjectCount-1].m_OwnerObject.x-d*2,s_MemObject[s_MemObjectCount-1].m_OwnerObject.y-d*2,s_MemObject[s_MemObjectCount-1].m_OwnerObject.x+d*2,s_MemObject[s_MemObjectCount-1].m_OwnerObject.y+d*2);
	pen1.DeleteObject();
	pDC->SelectObject(pOldPen);

	if(s_SearchResult.GetNodeCount()>0)
	{
		POINT oldPos={-1,-1};

		CPen pen2;
		pen2.CreatePen(PS_SOLID,2,RGB(255,0,0));
		CPen *pOldPen=pDC->SelectObject(&pen2);
		
		long nCount=s_SearchResult.GetNodeCount();
		SearchObject *pObject=NULL;

		for(long j=0;j<nCount;j++)
		{
			pObject=s_SearchResult.GetNode(j);
			if(oldPos.x!=-1 && oldPos.y!=-1)
			{
				pDC->MoveTo(oldPos);
				pDC->LineTo(pObject->x,pObject->y);
			}

			oldPos.x=pObject->x;
			oldPos.y=pObject->y;
		}

		pen2.DeleteObject();
		pDC->SelectObject(pOldPen);
	}
}


// CDijkstraTestView 打印

BOOL CDijkstraTestView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// 默认准备
	return DoPreparePrinting(pInfo);
}

void CDijkstraTestView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: 打印前添加额外的初始化
}

void CDijkstraTestView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: 打印后添加清除过程
}


// CDijkstraTestView 诊断

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

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

CDijkstraTestDoc* CDijkstraTestView::GetDocument() const // 非调试版本是内联的
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CDijkstraTestDoc)));
	return (CDijkstraTestDoc*)m_pDocument;
}
#endif //_DEBUG


// CDijkstraTestView 消息处理程序

void CDijkstraTestView::OnSearch()
{
	// TODO: 在此添加命令处理程序代码
	DWORD dwOldTick=::GetTickCount();
	CDijkstraSearch ds;
	ds.InitSearch(s_MemObject,s_MemObjectCount);

	s_SearchResult.RemoveAllNode();
	ds.StartSearch(&s_MemObject[0],&s_MemObject[s_MemObjectCount-1],0,&s_SearchResult);

	Invalidate();
	CString str;
	str.Format(_T("搜索完成,途经结点数%d,耗时%.2f秒"),s_SearchResult.GetNodeCount(),((double)::GetTickCount()-dwOldTick)/1000.0);
	CMainFrame *pMainWnd=(CMainFrame*)AfxGetMainWnd();
	pMainWnd->m_wndStatusBar.SetPaneText(0,str);
}

void CDijkstraTestView::OnEndsearch()
{
	// TODO: 在此添加命令处理程序代码
	s_SearchResult.RemoveAllNode();
	Invalidate();
}

void CDijkstraTestView::OnRandnode()
{
	// TODO: 在此添加命令处理程序代码
	
	for(long i=0;i<sizeof(s_MemObject)/sizeof(MemSearchObject);i++)
	{
		s_MemObject[i].m_pNextMemObjectList.RemoveAllNode();
	}
	s_MemObjectCount=0;

#if 1
	int nWidth=20;
	int nHeight=15;
	int d=45;
	int side=2;
#else
	int nWidth=400;
	int nHeight=250;
	int d=2;
	int side=2;
#endif

	for(int j=0;j<nHeight;j++)
	for(int i=0;i<nWidth;i++)
	{
		static int rand=0;
		srand((unsigned)time(NULL));
		rand=(::rand()+::GetTickCount()+rand+i+j)%(d/2);

		s_MemObject[s_MemObjectCount].m_OwnerObject.x=(i+1)*d + (rand-d/4);
		s_MemObject[s_MemObjectCount].m_OwnerObject.y=(j+1)*d + (rand-d/4);
		s_MemObjectCount++;
	}

	int dm[8];
	dm[0]=-1-nWidth;
	dm[1]=-1+nWidth;
	dm[2]=1-nWidth;
	dm[3]=1+nWidth;
	dm[4]=-1;
	dm[5]=nWidth;
	dm[6]=1;
	dm[7]=nWidth;

	int m=0;
	for(int j=0;j<nHeight;j++)
	for(int i=0;i<nWidth;i++)
	{
		for(int r=0;r<side;r++)
		{
			bool bRet=false;
			static int rand=0;
			srand((unsigned)time(NULL));
			rand=(::rand()+::GetTickCount()+rand+i+j)%8;

			while(!bRet)
			{
				int z=m+dm[rand];

				if(z>=0 && z<s_MemObjectCount)
				{
					if(s_MemObject[m].m_OwnerObject.GetValue(s_MemObject[z].m_OwnerObject,0)<(ValueType)(d*2))
					{
						MemConnect(m,z);
						bRet=true;
					}
				}

				if(!bRet) rand=(rand+1)%8;
			}
		}
		m++;
	}
	
	s_SearchResult.RemoveAllNode();
	Invalidate();
}

void CDijkstraTestView::OnSaveresult()
{
	// TODO: 在此添加命令处理程序代码
	CFileDialog dlg(FALSE,
		"", //缺省扩展名
		"result.txt",
		OFN_HIDEREADONLY|OFN_FILEMUSTEXIST, //文件必须存在
		"all files(*.*)|*.*|",
		this);

	if(dlg.DoModal()==IDOK)
	{
		CString strData=_T("");
		CString strTmp;
		long nCount=s_SearchResult.GetNodeCount();
		SearchObject *pObject=NULL;
		for(long j=0;j<nCount;j++)
		{
			pObject=s_SearchResult.GetNode(j);
			strTmp.Format(_T("%d,%f,%f"),pObject->id,pObject->x,pObject->y);
			strData+=strTmp;
			strData+=_T("\r\n");
		}

		CFile file;
		if(file.Open(dlg.GetPathName(),CFile::modeCreate|CFile::modeWrite))
		{
			char *p=strData.GetBuffer(0);
			file.Write(p,strData.GetLength());
			strData.ReleaseBuffer();
			file.Close();
		}
	}
}