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

Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 27.12.2008
Размер файла 493,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

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

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

На тему:

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

СТУДЕНТ (группа ИС-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 в противном случае. Таким образом, существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (рхр)т матрицами с нулями на диагонали.

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

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

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

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

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

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

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

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

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

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

Матрицей смежностей 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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

ь Холзенер С. 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("Oaee "+fname+" ia iaeaai\nA?ao aoaao nicaai neo?aeiui ia?acii","Iao oaeea",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("Aaiiue a?ao - iieiue","Test results",MB_OK);

else{

str.Format("Aaiiue a?ao - ia yaeyaony iieiui\nIao niaaeiaiey aa?oei (%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();

}


Подобные документы

  • Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.

    курсовая работа [525,6 K], добавлен 14.07.2012

  • Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.

    курсовая работа [145,5 K], добавлен 27.01.2013

  • Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.

    курсовая работа [783,2 K], добавлен 18.02.2013

  • Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.

    курсовая работа [2,0 M], добавлен 12.02.2013

  • Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.

    курсовая работа [1,1 M], добавлен 26.06.2012

  • Общее понятие графа, его виды и сущность вершинного покрытия. Написание точного алгоритма решения задачи о надежности сети, нахождение минимального покрытия. Реализация данного алгоритма на языке TurboC++. Код программы, решающий поставленную задачу.

    курсовая работа [1,3 M], добавлен 27.06.2014

  • Разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog. Составление графа "Карта Саратовской области" и решение проблемы поиска кратчайшего пути между двумя пунктами на карте.

    курсовая работа [366,4 K], добавлен 12.05.2009

  • История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.

    контрольная работа [646,9 K], добавлен 19.01.2016

  • Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.

    курсовая работа [1010,4 K], добавлен 10.08.2014

  • Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.

    презентация [22,8 K], добавлен 16.09.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.