Программа решения задачи о графах

Федеральное государственное образовательное учреждение

высшего профессионального образования

"Саровский государственный физико-технический институт"



Экономико-математический факультет





пояснительная записка

к курсовой работе



На тему:

Программа решения задачи о графах









СТУДЕНТ	 (группа ИС-45Д)	

РУКОВОДИТЕЛЬ	Беляев С.П.





















г. Саров 2008 г


Оглавление



ВВЕДЕНИЕ

ПОЛНЫЙ ГРАФ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Исходные параметры

Матрица смежностей

Исходные параметры

Этапы построения модели

РЕШЕНИЕ ЗАДАЧИ О ГРАФАХ

ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ

ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ

КОНТРОЛЬНЫЙ ПРИМЕР

СПИСОК ЛИТЕРАТУРЫ

ТЕКСТ ПРОГРАММЫ


ВВЕДЕНИЕ



Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых — теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков.


ПОЛНЫЙ ГРАФ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ



Граф G состоит из конечного непустого множества V, содержащего р вершин *), и заданного множества X, содержащего q неупорядоченных пар различных вершин из V. Каждую пару *= {ut v} вершин в X называют ребром графа G и говорят, что х соединяет uhv. Мы будем писать x=uv и говорить, что и v — смежные вершины (иногда это обозначается uadjv); вершина и ребро х инцидентны, так же как v и х. Если два различных ребра хну инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (pt ф-графом. A,0)-граф называется тривиальным. Граф полностью определяется или его смежностями, или его инциденциями. Указанную информацию о графе удобно представлять в матричной форме. Действительно, с данным графом, помеченым соответствующим образом, связаны несколько матриц, в том числе матрица смежностей, матрица инциденций, матрица циклов и матрица коциклов. Часто эти матрицы удается использовать при выявлении определенных свойств графа. Классическим результатом о графах и матрицах является матричная теорема о деревьях, в которой дается число остовов любого помеченного графа. В данной главе рассматриваются также матроиды, связанные с матрицами циклов и матрицами коциклов. 

Матрицей смежностей A = ||а(i,j)|| помеченного графа G с р вершинами называется (рхр)-матрица, в которой а(i,j)=\9 если вершина vt смежна с uj9 и а(i,j)~0 в противном случае. Таким образом, существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (рхр)т матрицами с нулями на диагонали.

Исходные параметры

Матрица смежностей

Исходные параметры

Матрица смежностей инвариантного и полного графа

Этапы построения модели

Составление матрицы смежностей 

Составление матрицы смежностей инвариантного графа

Составление матрицы смежностей полного графа

Построение графов


РЕШЕНИЕ ЗАДАЧИ О ГРАФАХ



Матрицей смежностей A = ||а(i,j)|| для некоторого помеченного графа G с р вершинами называется (рхр)-матрица, в которой а(i,j)=1 если вершина vi смежна с vj и а(i,j)=0 в противном случае. Таким образом, существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (рхр) – матрицами с нулями на диагонали.





Рисунок 1 Помеченный граф и его матрица смежностей



Матрицей смежностей B = ||b(i,j)|| для инварианта помеченного графа G с р вершинами называется (рхр)-матрица, в которой b(i,j)=1 если a(i,j)=0 и b(i,j)=0 в противном случае.





Рисунок 2 Инвариант помеченного граф и его матрица смежностей



Матрицей смежностей C = ||c(i,j)|| для  полного графа G с р вершинами называется (рхр)-матрица, в которой с(i,j)=0 если i=j и c(i,j)=1 в противном случае.



Рисунок 3 Полный граф и его матрица смежностей


ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ



Курсовая работа выполнена с помощью программы Microsoft Visual C++ 6.0, одной из наиболее передовых, мощных и современных сред разработки Windows-приложений с богатым инструментарием разработки приложений. Средства работы с контекстом устройства позволяет быстро справиться с задачей и выдать графическое отображение результатов.


ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ



После запуска программы, программа ищет файл с описанием графа Graph.dat







Далее выбираются следующие пиктограммы окна 





Отображение графа по его матрице смежностей

Отображение инварианта графа

Отображение полного графа

Редактор графа

Проверка графа на полноту

Перестраивает исходный граф в полный граф


Выбираем вторую пиктограмму





Теперь выберем последнюю пиктограмму




КОНТРОЛЬНЫЙ ПРИМЕР



 

 

 


ЗАКЛЮЧЕНИЕ



В результате выполнения работы был изучен алгоритм решения задачи поиска инвариантного и полного графа. На основе алгоритма реализована программа с графическим интерфейсом пользователя. Также реализован удобный редактор графа и вывод полученных результатов в простой и понятной форме.


СПИСОК ЛИТЕРАТУРЫ



		Холзенер С. X71 Visual C++ 6: Учебный курс – СПб: Питер, 2001 – 576 с: ил. 

		Дж. Макконнел. Анализ алгоритмов. Вводный курс – Москва: Техносфера, 2002 – 304 с.

		Тимофеев В. В.С++ как он есть. Самоучитель. – М.: ООО ≪Бином-Пресс≫,2004 г. – 366с.:ил.


ТЕКСТ ПРОГРАММЫ



Файл Graph.h

// Graph.h: interface for the CGraph class.//

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_)

#define AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_



#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000



class CGraphV{

public:

	CPoint pt;

	CString Title;

public:

	CGraphV() : pt(CPoint(0,0)), Title(_T("")){};

	virtual ~CGraphV() {};

public:

	CGraphV& operator = (const CGraphV& gV){

		pt = gV.pt; Title = gV.Title;

		return *this;

	}

};



class CGraphE{

public:

	BOOL state;

	double len;

public:

	CGraphE() : state(FALSE),len(0.0){};

	virtual ~CGraphE() {};

public:

	CGraphE& operator = (const CGraphE& gE){

		state = gE.state; len = gE.len;

		return *this;

	}

};



class CGraph  

{

public:

	CGraphV *V;

	CGraphE *E;

	int		V_count;

	int		curV;

public:

	void Create(int mV_count);

	BOOL IsExist();

	void Destroy();

	void Null(int m_V,double len);

	void SetV(int m_Vpos, CPoint pt, CString m_Title);

	void SetE(int i, int j, double m_len);

	void SetRand(int A_space, int B_space, int m_Len, double m_p);

	void Show(CDC *pDC, COLORREF c  = RGB(0,0,0));

	void Save(CString fname);

	void Load(CString fname);

	void MoveV(int m_x, int m_y);

	void SetCurV(int m_cur) { curV = m_cur;};

	void DeleteV(int indexV);

	void AddV(CPoint pt, CString m_Title);

	void MakeFull();

public:

	CGraph();

	virtual ~CGraph();

public:

	CGraph& operator = (const CGraph& g){

		int i=0;



		Destroy();

		Create(g.V_count);

		for(i=0;i<V_count;i++) V[i]=g.V[i];

		for(i=0;i<V_count*V_count;i++) E[i]=g.E[i];

		curV = g.curV;

		return *this;

	}

	CGraph& operator ! (){

		int i=0,j=0;

		BOOL fl = FALSE;



		for(i=0;i<V_count;i++)

			for(j=0;j<V_count;j++)

				if(i!=j) {

					fl = !(E[i*V_count+j].state);

					E[i*V_count+j].state=fl;

				}

		return *this;

	}

};



#endif // !defined(AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_)



Файл Graph.cpp

// Graph.cpp: implementation of the CGraph class.

//

//////////////////////////////////////////////////////////////////////



#include "stdafx.h"

#include "KursovikMin.h"

#include "Graph.h"



#ifdef _DEBUG

#undef THIS_FILE

static char THIS_FILE[]=__FILE__;

#define new DEBUG_NEW

#endif



//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////



CGraph::CGraph()

{

	V_count = 0;

}



CGraph::~CGraph()

{

	Destroy();

}



//////////////////////////////////////////////////////////////////////

// Methods

//////////////////////////////////////////////////////////////////////



void CGraph::Create(int mV_count)

{

	Destroy();

	if(mV_count <= 0) return;

	curV = -1;

	V_count = mV_count;

	V = new CGraphV[V_count];

	E = new CGraphE[V_count*V_count];

	Null(-1,0.0);

}



BOOL CGraph::IsExist()

{

	return V_count > 0;

}



void CGraph::Null(int m_V=-1, double m_len = -1)

{

	for(int i=0;i<V_count;i++)

		for(int j=0;j<V_count;j++)

		{

			E[i*V_count+j].state = FALSE;

			E[i*V_count+j].len = m_len;

		}

}



void CGraph::Destroy()

{

	if(IsExist()) {

		delete [] V;

		delete [] E;

		V = NULL;

		E = NULL;

		V_count = 0;

	}

}



void CGraph::SetV(int m_Vpos, CPoint m_pt, CString m_Title)

{

	if(m_Vpos < V_count){

		V[m_Vpos].pt = m_pt;

		V[m_Vpos].Title = m_Title;

	}

}



void CGraph::SetE(int i, int j, double m_len)

{

	int pos = i*V_count+j;

	if(pos < V_count*V_count)

		{E[pos].state = TRUE;E[pos].len = m_len;}

}



void CGraph::SetRand(int A_space, int B_space, int m_Len, double m_p)

{

	int COUNT = V_count;

	CString str;



	srand(time(NULL));

	for(int i=0;i<COUNT;i++ )

	{

		str.Format("Point-%i",i);

		SetV(i,CPoint(A_space+rand()%(B_space-A_space+1),A_space+rand()%(B_space-A_space+1)),str);

	}

	for(i=0;i<COUNT*COUNT;i++)

		if((rand()+0.0)/RAND_MAX >= m_p) SetE(i / COUNT, i % COUNT, m_Len*rand()/RAND_MAX);

		else {E[i].state = FALSE;E[i].len = 0.0;}

}



void CGraph::Show(CDC *pDC, COLORREF c)

{

	int i=0, j=0, fn = V_count*V_count;

	const int sz = 4;

	CPoint pt1, pt2;

	CPen p(PS_SOLID,1,c), *old_p;

	CString str;



	old_p = pDC->SelectObject(&p);

	pDC->SetBkMode(TRANSPARENT);

	for(i=0;i<V_count;i++)

	{

		pDC->Ellipse(V[i].pt.x-sz,V[i].pt.y-sz,V[i].pt.x+sz,V[i].pt.y+sz);

		pDC->TextOut(V[i].pt.x,V[i].pt.y,V[i].Title);

	}

	for(i=0;i<fn;i++)

		if(E[i].state) 

		{	

			pt1 = V[i/V_count].pt; pt2 = V[i%V_count].pt;

			//str.Format("%7.3f",E[i].len);

			pDC->MoveTo(pt1);

			pDC->LineTo(pt2);

			//pDC->TextOut((pt1.x+pt2.x)/2,(pt1.y+pt2.y)/2,str);

		}

	pDC->SelectObject(old_p);

}



void CGraph::Save(CString fname)

{

	int i=0,j=0,len = 0;

	const UINT Separator = 0xffff;

	char buf[81];



	FILE *file = NULL;

	file = fopen(fname,"wb");

	if(file != NULL){

		fwrite(&V_count,sizeof(V_count),1,file);

		for(i=0;i<V_count;i++){

			fwrite(&V[i].pt.x,sizeof(V[i].pt.x),1,file);

			fwrite(&V[i].pt.y,sizeof(V[i].pt.y),1,file); len = V[i].Title.GetLength();

			fwrite(&len,sizeof(int),1,file);

			//fwrite(&V[i].Title,len,1,file);

			for(j=0;j<len;j++)

				buf[j] = V[i].Title[j];

			buf[len]=0;

			fwrite(&buf[0],len,1,file);

		}

		for(i=0;i<V_count*V_count;i++)

		{

			fwrite(&E[i].state,sizeof(E[i].state),1,file);

			fwrite(&E[i].len,sizeof(E[i].len),1,file);

		}

		fclose(file);

	}

}



void CGraph::Load(CString fname)

{

	int i=0, len = 0;

	const UINT Separator = 0xffff;

	char buf[81];



	FILE *file = NULL;

	file = fopen(fname,"rb");

	if(file != NULL){

		Destroy();

		fread(&i,sizeof(i),1,file);

		Create(i);

		for(i=0;i<V_count;i++){

			fread(&V[i].pt.x,sizeof(V[i].pt.x),1,file);

			fread(&V[i].pt.y,sizeof(V[i].pt.y),1,file);

			fread(&len,sizeof(int),1,file);

			fread(&buf[0],len,1,file); buf[len] = 0;

			V[i].Title = buf;

		}

		for(i=0;i<V_count*V_count;i++)

		{

			fread(&E[i].state,sizeof(E[i].state),1,file);

			fread(&E[i].len,sizeof(E[i].len),1,file);

		}

		fclose(file);

	}

}



void CGraph::MoveV(int m_x, int m_y)

{

	if(curV >=0 && curV < V_count)

		V[curV].pt = CPoint(m_x,m_y);

}



void CGraph::DeleteV(int indexV)

{

	int i=0, j=0;



	if(!IsExist()) return;

	if(indexV>=0 && indexV<V_count)

	{

		CGraph g;

		int i1 = 0, j1 = 0;

		g.Create(V_count-1);

		for(i=0;i<V_count;i++)

			if(i != indexV) g.V[i1++] = V[i];

		i1 = 0; j1 = 0;

		for(i=0;i<V_count;i++)

		{

			if(i != indexV){

			j1 = 0;

			for(j=0;j<V_count;j++)

				if(j != indexV) {g.E[i1*(V_count-1)+j1] = E[i*V_count+j];j1++;}

			i1++;

			}

		}

		Destroy();

		*this = g;

	}

}



void CGraph::AddV(CPoint pt, CString m_Title)

{

	int i=0;

	CGraphV *V1 = new CGraphV[V_count+1];

	CGraphE *E1 = new CGraphE[(V_count+1)*(V_count+1)];



	for(i=0;i<V_count;i++) {V1[i].pt = V[i].pt; V1[i].Title = V[i].Title;}

	V1[i].pt = pt; V1[i].Title = m_Title;

	for(i=0;i<V_count*V_count;i++) 

	{

		E1[i].state = E[i].state; 

		E1[i].len = E[i].len;

	}

	for(i=0;i<V_count*V_count;i++) {

		E1[(V_count-1)*V_count+i].state = FALSE; 

		E1[(V_count-1)*V_count+i].len = 0.0;

	}

	Create(V_count+1);

	for(i=0;i<V_count;i++) {V[i].pt = V1[i].pt; V[i].Title = V1[i].Title;}

	for(i=0;i<V_count*V_count;i++) 

	{

		E[i].state = E1[i].state; 

		E[i].len = E1[i].len;

	}

	delete [] V1;

	delete [] E1;

}



void CGraph::MakeFull()

{

	for(int i=0;i<V_count*V_count;i++)

		E[i].state = TRUE;

}

Файл KursovikMinView.h

// KursovikMinView.h : interface of the CKursovikMinView class

//

/////////////////////////////////////////////////////////////////////////////



#if !defined(AFX_KURSOVIKMINVIEW_H__8A69BF1A_16AF_4508_9EB6_7960CF0CBACD__INCLUDED_)

#define AFX_KURSOVIKMINVIEW_H__8A69BF1A_16AF_4508_9EB6_7960CF0CBACD__INCLUDED_



#include "Graph.h"



#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000



class CGrpah;

class CKursovikMinView : public CScrollView

{

protected: // create from serialization only

	CKursovikMinView();

	DECLARE_DYNCREATE(CKursovikMinView)



// Attributes

public:

	CKursovikMinDoc* GetDocument();

	int mode;

	CGraph m_graph;

	CGraph m_Ngraph;

// Operations

public:



// Overrides

	// ClassWizard generated virtual function overrides

	//{{AFX_VIRTUAL(CKursovikMinView)

	public:

	virtual void OnDraw(CDC* pDC);  // overridden to draw this view

	virtual BOOL PreCreateWindow(CREATESTRUCT& cs);

	protected:

	virtual void OnInitialUpdate(); // called first time after construct

	virtual BOOL OnPreparePrinting(CPrintInfo* pInfo);

	virtual void OnBeginPrinting(CDC* pDC, CPrintInfo* pInfo);

	virtual void OnEndPrinting(CDC* pDC, CPrintInfo* pInfo);

	//}}AFX_VIRTUAL



// Implementation

public:

	virtual ~CKursovikMinView();

#ifdef _DEBUG

	virtual void AssertValid() const;

	virtual void Dump(CDumpContext& dc) const;

#endif



protected:



// Generated message map functions

protected:

	//{{AFX_MSG(CKursovikMinView)

	afx_msg void OnLButtonUp(UINT nFlags, CPoint point);

	afx_msg void OnFileSave();

	afx_msg void OnFileOpen();

	afx_msg void OnMouseMove(UINT nFlags, CPoint point);

	afx_msg void OnRButtonUp(UINT nFlags, CPoint point);

	afx_msg void OnKeyUp(UINT nChar, UINT nRepCnt, UINT nFlags);

	afx_msg void OnEditDialog();

	afx_msg void OnEditMakefullgraph();

	afx_msg void OnEditTestOnFull();

	afx_msg void OnFileNew();

	afx_msg void OnShowGraph();

	afx_msg void OnShowGraphs();

	afx_msg void OnShowNgraph();

	//}}AFX_MSG

	DECLARE_MESSAGE_MAP()

};



#ifndef _DEBUG  // debug version in KursovikMinView.cpp

inline CKursovikMinDoc* CKursovikMinView::GetDocument()

   { return (CKursovikMinDoc*)m_pDocument; }

#endif



/////////////////////////////////////////////////////////////////////////////



//{{AFX_INSERT_LOCATION}}

// Microsoft Visual C++ will insert additional declarations immediately before the previous line.



#endif // !defined(AFX_KURSOVIKMINVIEW_H__8A69BF1A_16AF_4508_9EB6_7960CF0CBACD__INCLUDED_)

Файл KursovikMinView.cpp

// KursovikMinView.cpp : implementation of the CKursovikMinView class

//

#include "stdafx.h"

#include "KursovikMin.h"



#include "KursovikMinDoc.h"

#include "KursovikMinView.h"

#include "GraphSettinngs.h"

#include <math.h>



#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif



/////////////////////////////////////////////////////////////////////////////

// CKursovikMinView



IMPLEMENT_DYNCREATE(CKursovikMinView, CScrollView)



BEGIN_MESSAGE_MAP(CKursovikMinView, CScrollView)

	//{{AFX_MSG_MAP(CKursovikMinView)

	ON_WM_LBUTTONUP()

	ON_COMMAND(ID_FILE_SAVE, OnFileSave)

	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)

	ON_WM_MOUSEMOVE()

	ON_WM_RBUTTONUP()

	ON_WM_KEYUP()

	ON_COMMAND(ID_EDIT_DIALOG, OnEditDialog)

	ON_COMMAND(ID_EDIT_MAKEFULLGRAPH, OnEditMakefullgraph)

	ON_COMMAND(ID_EDIT_TEST_ON_FULL, OnEditTestOnFull)

	ON_COMMAND(ID_FILE_NEW, OnFileNew)

	ON_COMMAND(ID_SHOW_GRAPH, OnShowGraph)

	ON_COMMAND(ID_SHOW_GRAPHS, OnShowGraphs)

	ON_COMMAND(ID_SHOW_NGRAPH, OnShowNgraph)

	//}}AFX_MSG_MAP

	// Standard printing commands

	ON_COMMAND(ID_FILE_PRINT, CScrollView::OnFilePrint)

	ON_COMMAND(ID_FILE_PRINT_DIRECT, CScrollView::OnFilePrint)

	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CScrollView::OnFilePrintPreview)

END_MESSAGE_MAP()



/////////////////////////////////////////////////////////////////////////////

// CKursovikMinView construction/destruction



CKursovikMinView::CKursovikMinView()

{

	// TODO: add construction code here

	const int COUNT = 8;

	mode = 0;

	const CString fname = "Graph.dat";

	CString str;

	CFile f;



	if(f.Open(fname,CFile::modeRead))

	{

		f.Close();

		m_graph.Load(fname);

	}

	else{

		MessageBox("Ôàéë "+fname+" íå íàéäåí\nÃðàô áóäåò ñîçäàí ñëó÷àéíûì îáðàçîì","Íåò ôàéëà",MB_OK);

		m_graph.Create(COUNT);

		m_graph.SetRand(30,150,25,0.5);

	}

	/*

	srand(time(NULL));

	for(int i=0;i<COUNT;i++ )

	{

		str.Format("Point-%i",i);

		m_graph.SetV(i,CPoint(20+rand()%100,20+rand()%100),str);

	}

	for(i=0;i<COUNT*COUNT;i++)

		if(rand() % 5 == 0) m_graph.SetE(i / COUNT, i % COUNT, 5.0+(1.0+rand())/RAND_MAX);

	*/

}



CKursovikMinView::~CKursovikMinView()

{

}



BOOL CKursovikMinView::PreCreateWindow(CREATESTRUCT& cs)

{

	// TODO: Modify the Window class or styles here by modifying

	//  the CREATESTRUCT cs



	return CScrollView::PreCreateWindow(cs);

}



/////////////////////////////////////////////////////////////////////////////

// CKursovikMinView drawing



void CKursovikMinView::OnDraw(CDC* pDC)

{

	CKursovikMinDoc* pDoc = GetDocument();

	ASSERT_VALID(pDoc);

	switch(mode){

		case 0 :m_graph.Show(pDC,RGB(0,0,0)); break;

		case 1 :m_Ngraph.Show(pDC,RGB(0,255,0)); break;

		case 2 :m_graph.Show(pDC,RGB(0,0,0)); break;

		default : m_graph.Show(pDC); break;

	}

	// TODO: add draw code for native data here

}



void CKursovikMinView::OnInitialUpdate()

{

	CScrollView::OnInitialUpdate();



	CSize sizeTotal;

	// TODO: calculate the total size of this view

	sizeTotal.cx = sizeTotal.cy = 100;

	SetScrollSizes(MM_TEXT, sizeTotal);

}



/////////////////////////////////////////////////////////////////////////////

// CKursovikMinView printing



BOOL CKursovikMinView::OnPreparePrinting(CPrintInfo* pInfo)

{

	// default preparation

	return DoPreparePrinting(pInfo);

}



void CKursovikMinView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)

{

	// TODO: add extra initialization before printing

}



void CKursovikMinView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)

{

	// TODO: add cleanup after printing

}



/////////////////////////////////////////////////////////////////////////////

// CKursovikMinView diagnostics



#ifdef _DEBUG

void CKursovikMinView::AssertValid() const

{

	CScrollView::AssertValid();

}



void CKursovikMinView::Dump(CDumpContext& dc) const

{

	CScrollView::Dump(dc);

}



CKursovikMinDoc* CKursovikMinView::GetDocument() // non-debug version is inline

{

	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CKursovikMinDoc)));

	return (CKursovikMinDoc*)m_pDocument;

}

#endif //_DEBUG



/////////////////////////////////////////////////////////////////////////////

// CKursovikMinView message handlers



void CKursovikMinView::OnFileSave() 

{

	// TODO: Add your command handler code here

	CString fname;

	CFileDialog dlg(FALSE,"dat","*.dat");

	if(dlg.DoModal()==IDOK)

		m_graph.Save(dlg.GetFileName());

}



void CKursovikMinView::OnFileOpen() 

{

	// TODO: Add your command handler code here

	CString fname;

	CFileDialog dlg(TRUE,"dat","*.dat");

	if(dlg.DoModal()==IDOK)

		m_graph.Load(dlg.GetFileName());

	Invalidate();

}

void CKursovikMinView::OnLButtonUp(UINT nFlags, CPoint point) 

{

	// TODO: Add your message handler code here and/or call default

	//m_graph.SetRand(30,250,25,0.8);

	CScrollView::OnLButtonUp(nFlags, point);

}



void CKursovikMinView::OnMouseMove(UINT nFlags, CPoint point) 

{

	// TODO: Add your message handler code here and/or call default

	if(nFlags & MK_RBUTTON) {

		m_graph.MoveV(point.x,point.y);

		Invalidate();

	}

	CScrollView::OnMouseMove(nFlags, point);

}



void CKursovikMinView::OnRButtonUp(UINT nFlags, CPoint point) 

{

	// TODO: Add your message handler code here and/or call default

	mode = 0;

	m_graph.SetCurV(0);

	m_Ngraph.Destroy();

	for(int i=0;i<m_graph.V_count;i++)

		if((fabs(m_graph.V[i].pt.x-point.x) < 10) && (fabs(m_graph.V[i].pt.y-point.y) < 10))

		{ m_graph.SetCurV(i); break; }

	Invalidate();

	CScrollView::OnRButtonUp(nFlags, point);

}

void CKursovikMinView::OnKeyUp(UINT nChar, UINT nRepCnt, UINT nFlags) 

{

	// TODO: Add your message handler code here and/or call default

	switch(nChar)

	{

		case '0': 

			m_graph.SetRand(30,250,25,0.8);

			Invalidate();

		break;

		//default: MessageBox("key = "+nChar); break;

	}

	CScrollView::OnKeyUp(nChar, nRepCnt, nFlags);

}



void CKursovikMinView::OnEditDialog() 

{

	// TODO: Add your command handler code here

	CGraphSettinngs dlg;

	dlg.Init(&m_graph);

	dlg.DoModal();

	Invalidate();

}



void CKursovikMinView::OnEditMakefullgraph() 

{

	// TODO: Add your command handler code here

	int i=0,j=0,Vs = m_graph.V_count*m_graph.V_count;

	BOOL IsFull = FALSE;

	for(i=0;i<Vs;i++)

		m_graph.E[i].state = TRUE;

	Invalidate();

}



void CKursovikMinView::OnEditTestOnFull() 

{

	int i=0,j=0,Vs = m_graph.V_count;

	BOOL IsFull = FALSE;

	CString str;



	for(i=0;i<Vs;i++)

	{

		for(j=0;j<Vs-i;j++)

			if(i != j && (!m_graph.E[i*Vs+j].state || !m_graph.E[j*Vs+i].state)) {IsFull = TRUE; break;}

		if(IsFull) break;

	}

	if(!IsFull) MessageBox("Äàííûé ãðàô - ïîëíûé","Test results",MB_OK);

	else{ 

		str.Format("Äàííûé ãðàô - íå ÿâëÿåòñÿ ïîëíûì\nÍåò ñîåäèíåíèÿ âåðøèí (%i,%i)",i,j);

		MessageBox(str,"Test results",MB_OK);

	}

}



void CKursovikMinView::OnFileNew() 

{

	// TODO: Add your command handler code here

	m_graph.SetRand(30,250,25,0.8);

	Invalidate();

}

void CKursovikMinView::OnShowGraph() 

{

	// TODO: Add your command handler code here

	mode = 0;

	Invalidate();

}



void CKursovikMinView::OnShowGraphs() 

{

	// TODO: Add your command handler code here

	mode = 0;

	

	/*

	m_Ngraph.Destroy();

	m_Ngraph = m_graph;

	!m_Ngraph;

	*/

	m_graph.MakeFull();

	Invalidate();

}



void CKursovikMinView::OnShowNgraph() 

{

	// TODO: Add your command handler code here

	mode = 1;

	m_Ngraph = m_graph;

	!m_Ngraph;

	Invalidate();

}