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

Федеральное государственное образовательное учреждение высшего профессионального образования "Саровский государственный физико-технический институт"
Экономико-математический факультет

пояснительная записка к курсовой работе
На тему: Программа решения задачи о графах



СТУДЕНТ (группа ИС-45Д) РУКОВОДИТЕЛЬ Беляев С.П.









г. Саров 2008 г
Оглавление

ВВЕДЕНИЕ 4

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

Граф 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();

}