keypathview.cpp

利用Visual c++编程思想方法实现基于交通网络关键路径算法

#include "stdafx.h"
#include "KeyPath.h"

#include "KeyPathDoc.h"
#include "KeyPathView.h"

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

extern CKeyPathApp theApp;
CKeyPathView::CKeyPathView()
	: CFormView(CKeyPathView::IDD)
{
	drawType = 0;
	pointColor = RGB(0,0,0); //顶点颜色
	selPointColor = RGB(0,0,255); //顶点被选中颜色
	keyPointColor = RGB(0,255,0); //关键顶点颜色
	pathColor = RGB(0,0,0); //边界颜色
	selPathColor = RGB(0,0,255); //边界被选中颜色
	keyPathColor = RGB(0,255,0); //关键路径颜色
	prev = -1;
	next = -1;
	curPath = -1;
	movePic = false;
	startCalPoint = -1;
	endCalPoint = -1;

	theApp.m_PathTitle = _T("");
	theApp.m_PathTitleID = -1;

}

CKeyPathView::~CKeyPathView()
{
	//清除vector中的内容，以释放所占用的内存空间。
	pointVec.clear();
	edgeVec.clear();
}

void CKeyPathView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	
}

BOOL CKeyPathView::PreCreateWindow(CREATESTRUCT& cs)
{
	return CFormView::PreCreateWindow(cs);
}

void CKeyPathView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

}

BOOL CKeyPathView::OnPreparePrinting(CPrintInfo* pInfo)
{
	return DoPreparePrinting(pInfo);
}

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

void CKeyPathView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CKeyPathDoc* CKeyPathView::GetDocument() 
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CKeyPathDoc)));
	return (CKeyPathDoc*)m_pDocument;
}
#endif
void CKeyPathView::OnRButtonDblClk(UINT nFlags, CPoint point) 
{
	int selPoint;
	GetSelPoint(selPoint, point);
	if (selPoint > -1) {
		CPointDlg dlg;
		if (dlg.DoModal() == IDOK) {
			pointVec[selPoint].name = theApp.m_pointName;
			pointVec[selPoint].memo = theApp.m_pointMemo;
			ReDrawAll();
		}
	}
	CFormView::OnLButtonDblClk(nFlags, point);
}

void CKeyPathView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	int i = 0;
	
	if (drawType == 0) {
		//移动顶点
		GetSelPoint(prev, point);
		if (prev > -1) {
			movePic = true;
			pointVec[prev].xAxis = point.x;
			pointVec[prev].yAxis = point.y;
			ReDrawAll();
		}
	} else if (drawType == 10) {
		//添加顶点
		CPointDlg dlg;
		if (dlg.DoModal() == IDOK) {
			CPointInfo pInfo;
			pInfo.xAxis = point.x;
			pInfo.yAxis = point.y;
			pInfo.color = pointColor;
			pInfo.name = theApp.m_pointName;
			pInfo.memo = theApp.m_pointMemo;
			int i = pointVec.size();
			pInfo.id = ++i;
			pointVec.push_back(pInfo);
			ReDrawAll();
		}

	} else if (drawType == 20) {
		//添加边界
		if (-1 == prev) {
			//选择开始点
			GetSelPoint(prev, point);
			ReDrawAll();
		} else {
			GetSelPoint(next, point);
			if (next != -1) {
				//选中结束点
				CEdgeDlg dlg;
				if (dlg.DoModal() == IDOK) {
					CEdgeInfo eInfo;
					eInfo.prevPoint = &pointVec[prev];
					eInfo.nextPoint = &pointVec[next];
					eInfo.duttem = theApp.m_dut;
					edgeVec.push_back(eInfo);
					ReDrawAll();
				}
				prev = -1;
				next = -1;
			}
		}
		
	} else if (drawType == 40) {
		//分段计算关键路径
		if (-1 == prev) {
			//选择开始点
			
			m_resultList.ResetContent();
			m_varList.ResetContent();
			
			for (i = 0; i < pointVec.size(); i++) 
				pointVec[i].isKey = 0;
			
			for (i = 0; i < edgeVec.size(); i++)
				edgeVec[i].isKey = 0;
			
			next = -1;
			startCalPoint = -1;
			endCalPoint = -1;

			GetSelPoint(prev, point);
			ReDrawAll();
		} else {
			GetSelPoint(next, point);
			if (next != -1) {
				//选中结束点

				startCalPoint = prev;
				endCalPoint = next;
				CalKeyPath();

				prev = -1;
				next = -1;
			}
		}
	}
	
	CFormView::OnLButtonDown(nFlags, point);
}

void CKeyPathView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	
	if (drawType == 0) {
		prev = -1;
		movePic = false;
	}
	CFormView::OnLButtonUp(nFlags, point);
}

void CKeyPathView::OnMouseMove(UINT nFlags, CPoint point) 
{
	if (drawType == 0 && movePic && prev > -1) {
		//移动顶点
		pointVec[prev].xAxis = point.x;
		pointVec[prev].yAxis = point.y;
		ReDrawAll();
	}
	CFormView::OnMouseMove(nFlags, point);
}

/************************************************************************/
/* 添加边界                                                             */
/************************************************************************/
void CKeyPathView::OnButtonAddLine() 
{
	// TODO: Add your command handler code here
	drawType = 20;
}

/************************************************************************/
/* 添加顶点                                                             */
/************************************************************************/
void CKeyPathView::OnButtonAddPoint() 
{
	// TODO: Add your command handler code here
	drawType = 10;
}

/************************************************************************/
/* 计算关键路径                                                         */
/************************************************************************/
void CKeyPathView::OnButtonCalResult() 
{
	// TODO: Add your command handler code here

	drawType = 30;
	int i = 0;
	
	m_resultList.ResetContent();
	m_varList.ResetContent();
	
	for (i = 0; i < pointVec.size(); i++) 
		pointVec[i].isKey = 0;
	
	for (i = 0; i < edgeVec.size(); i++)
		edgeVec[i].isKey = 0;
	
	prev = -1;
	next = -1;
	startCalPoint = -1;
	endCalPoint = -1;

	int total = 0;
	
	//int begin,end,duttem;
	edgenode *p;
	vexnode* graphicmap = (vexnode*) malloc(pointVec.size() * sizeof(vexnode));
	
	//初始化默认值
	for(i = 0; i < pointVec.size(); i++)
	{
        graphicmap[i].trafficnetname = i;
		graphicmap[i].id = 0;
		graphicmap[i].link = NULL;
	}	
	
	//构建关键路径计算数值
	for(i = 0; i < edgeVec.size(); i++)
	{
		CEdgeInfo eInfo = edgeVec[i];
		p = (edgenode*) malloc(sizeof(edgenode));
		p->adjvex = eInfo.nextPoint->id - 1;
		p->dut = eInfo.duttem;
		graphicmap[eInfo.nextPoint->id - 1].id++;
		p->next = graphicmap[eInfo.prevPoint->id - 1].link ;
		graphicmap[eInfo.prevPoint->id - 1].link = p;
	}
	StepRun(1);
	
	//寻找关键路径
	SearchKeyPath(graphicmap, pointVec.size(), edgeVec.size(), total);
	
	//显示最后结果
	CString tmp;
	for (i = 0; i < pointVec.size(); i++) {
		if (pointVec[i].isKey == 1) {
			tmp += pointVec[i].name;
			tmp += ";";
		}
	}
	m_resultList.AddString(tmp);
	tmp.Format("关键路径总长度:%d", total);
	m_resultList.AddString(tmp);
	
}

/************************************************************************/
/* 移动顶点                                                             */
/************************************************************************/
void CKeyPathView::OnButtonMovePoint() 
{
	drawType = 0;
}

/************************************************************************/
/* 重新绘制图形                                                         */
/************************************************************************/
void CKeyPathView::ReDrawAll()
{
	CRect rect;
	int i = 0;
	CString tmp;
	int x1, x2, x11, x22, y1, y2, y11, y22;
	
	// 获取绘制坐标的文本框
	CWnd* pWnd = GetDlgItem(IDC_DRAW_STC);
	
	pWnd->GetClientRect(&rect);
	// 指针
	pDC = pWnd->GetDC();	
	pWnd->Invalidate();
	pWnd->UpdateWindow();
	
	//pDC->Rectangle(&rect);
	CBrush brushNew;
	brushNew.CreateSolidBrush(RGB(255, 255, 255));
	
    //内存绘图
    CBitmap memBitmap;
	CBitmap* pOldBmp = NULL;
	memDC.CreateCompatibleDC(pDC);
	memBitmap.CreateCompatibleBitmap(pDC,rect.right,rect.bottom);
	pOldBmp = memDC.SelectObject(&memBitmap);
	memDC.BitBlt(rect.left,rect.top,rect.right,rect.bottom,pDC,0,0,SRCCOPY);
	memDC.FillSolidRect(rect.left,rect.top,rect.right,rect.bottom, RGB(255, 255, 255));

	CPen norPen(0, 1, RGB(0,0,0));
	CPen selPen(0, 1, RGB(0,255,0));
	CPen keyPen(0, 1, RGB(255,0,0));

	//绘制顶点
	for (i = 0; i < pointVec.size(); i++) {
		CPointInfo pInfo = pointVec[i];
		if (pInfo.isKey == 1) {
			memDC.SetTextColor(keyPointColor);
			memDC.SelectObject(keyPen);
		} else if (prev == i || next == i) {
			memDC.SetTextColor(selPointColor);
			memDC.SelectObject(selPen);
		} else {
			memDC.SetTextColor(pInfo.color);
			memDC.SelectObject(norPen);
		}
		tmp.Format("%d", pInfo.id);
		memDC.Ellipse(pInfo.xAxis -15, pInfo.yAxis - 15, pInfo.xAxis + 15, pInfo.yAxis + 15);
		memDC.TextOut(pInfo.xAxis - 4, pInfo.yAxis - 8, tmp);
		memDC.TextOut(pInfo.xAxis + 15, pInfo.yAxis + 15, pInfo.name);
	}

	//绘制边界线
	for (i = 0; i < edgeVec.size(); i++) {
		CEdgeInfo eInfo = edgeVec[i];
		tmp.Format("%d", eInfo.duttem);

		if (curPath == i) {
			memDC.SetTextColor(selPointColor);
			memDC.SelectObject(selPen);
		} else if (eInfo.isKey == 1) {
			memDC.SetTextColor(keyPointColor);
			memDC.SelectObject(keyPen);
		} else {
			memDC.SetTextColor(eInfo.prevPoint->color);
			memDC.SelectObject(norPen);
		}
		
		//计算直线起点与第一个圆的交点
		GetJionPointCoor(eInfo.prevPoint->xAxis, eInfo.prevPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, eInfo.prevPoint->xAxis, eInfo.prevPoint->yAxis, 15, x1, y1, 0);
		//计算直线终点与第二个圆的交点
		GetJionPointCoor(eInfo.prevPoint->xAxis, eInfo.prevPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, 15, x2, y2, 0);
		//计算直线终点与第二个圆的交点，用于画出向上箭头
		GetJionPointCoor(eInfo.prevPoint->xAxis, eInfo.prevPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, 20, x11, y11, 5);
		//计算直线终点与第二个圆的交点，用于画出向下箭头
		GetJionPointCoor(eInfo.prevPoint->xAxis, eInfo.prevPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, eInfo.nextPoint->xAxis, eInfo.nextPoint->yAxis, 20, x22, y22, -5);
		//绘制连接线
		memDC.MoveTo(x1, y1);
		memDC.LineTo(x2, y2);
		//绘制向上箭头
		memDC.MoveTo(x11, y11);
		memDC.LineTo(x2, y2);
		//绘制向下箭头
		memDC.MoveTo(x22, y22);
		memDC.LineTo(x2, y2);
		//标明线段上的文字
		memDC.TextOut((eInfo.prevPoint->xAxis + eInfo.nextPoint->xAxis) / 2, (eInfo.prevPoint->yAxis + eInfo.nextPoint->yAxis) / 2, tmp); 
	}
	
	pDC->BitBlt(rect.left,rect.top,rect.right,rect.bottom,&memDC,0,0,SRCCOPY);
	
	norPen.DeleteObject();
	selPen.DeleteObject();
	keyPen.DeleteObject();
	memDC.SelectObject(pOldBmp);
	memDC.DeleteDC();
	memBitmap.DeleteObject();
}

void CKeyPathView::OnDraw(CDC* pDC) 
{
	ReDrawAll();
}

void CKeyPathView::GetSelPoint(int & num, CPoint point)
{
	num = -1;
	CString aa;
	for (int i = 0; i < pointVec.size(); i++) {
		CPointInfo pInfo1 = pointVec[i];
		double dist = sqrt((point.x - pInfo1.xAxis) * (point.x - pInfo1.xAxis) + 
			(point.y - pInfo1.yAxis) * (point.y - pInfo1.yAxis));
		if (dist <= 15) {
			num = i;
			break;
		}

	}

}

int CKeyPathView::SearchKeyPath(vexnode* graphicmap,int citynumber,int activenumber,int& total)
{
	StepRun(2);
	int i, j, k, m = 0;
	StepRun(3);
	int front = -1, rear = -1;
	StepRun(4);
	int* topologystack = (int*) malloc(citynumber * sizeof(int)); //用来保存拓扑排列
	StepRun(5);
	int* vl = (int*) malloc(citynumber * sizeof(int)); //用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间
	StepRun(6);
    int* ve = (int*) malloc(citynumber * sizeof(int)); //用来表示Vj最早发生时间
	StepRun(7);
	int* l = (int*) malloc(activenumber * sizeof(int)); //用来表示活动Ai最迟完成开始时间
	StepRun(8);
	int* e = (int*) malloc(activenumber * sizeof(int)); //表示活动最早开始时间
	StepRun(9);