Федеральное государственное образовательное учреждение
высшего профессионального образования
«Саровский государственный физико-технический институт»
Экономико-математический факультет
пояснительная записка
к курсовой работе
На тему:
Программа решения задачи о графах
СТУДЕНТ (группа ИС-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 в противном случае. Таким образом, существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (рхр) – матрицами с нулями на диагонали.
/>
Рисунок 3 Помеченный граф и его матрица смежностей
Матрицей смежностей B = ||b(i,j)|| для инварианта помеченного графа G с р вершинами называется (рхр)-матрица, в которой b(i,j)=1 если a(i,j)=0 и b(i,j)=0 в противном случае.
/>
Рисунок 3 Инвариант помеченного граф и его матрица смежностей
Матрицей смежностей C = ||c(i,j)|| для полного графа G с р вершинами называется (рхр)-матрица, в которой с(i,j)=0 если i=j и c(i,j)=1 в противном случае.
/>
Рисунок 3 Полный граф и его матрица смежностей
ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ
Курсовая работа выполнена с помощью программы Microsoft Visual C++ 6.0, одной из наиболее передовых, мощных и современных сред разработки Windows-приложений с богатым инструментарием разработки приложений. Средства работы с контекстом устройства позволяет быстро справиться с задачей и выдать графическое отображение результатов.
ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ
После запуска программы, программа ищет файл с описанием графа Graph.dat
/>
Далее выбираются следующие пиктограммы окна
/>
Отображение графа по его матрице смежностей
Отображение инварианта графа
Отображение полного графа
Редактор графа
Проверка графа на полноту
Перестраивает исходный граф в полный граф
Выбираем вторую пиктограмму
/>
Теперь выберем последнюю пиктограмму
/>
КОНТРОЛЬНЫЙ ПРИМЕР
/>
/>/>
/>/>
ЗАКЛЮЧЕНИЕ
В результате выполнения работы был изучен алгоритм решения задачи поиска инвариантного и полного графа. На основе алгоритма реализована программа с графическим интерфейсом пользователя. Также реализован удобный редактор графа и вывод полученных результатов в простой и понятной форме.--PAGE_BREAK--
СПИСОК ЛИТЕРАТУРЫ
Холзенер С. X71 VisualC++ 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
for(i=0;i
curV = g.curV;
return *this;
}
CGraph& operator! (){
int i=0,j=0;
BOOL fl = FALSE;
for(i=0;i
for(j=0;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
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
for(int j=0;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[m_Vpos].pt = m_pt;
V[m_Vpos].Title = m_Title;
}
} продолжение
--PAGE_BREAK--
void CGraph::SetE(int i, int j, double m_len)
{
int pos = i*V_count+j;
if(pos
{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
{
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
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
{
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
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
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
buf[j] = V[i].Title[j];
buf[len]=0;
fwrite(&buf[0],len,1,file);
}
for(i=0;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
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
{
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[curV].pt = CPoint(m_x,m_y);
}
void CGraph::DeleteV(int indexV)
{
int i=0, j=0;
if(!IsExist()) return;
if(indexV>=0 && indexV
{
CGraph g;
int i1 = 0, j1 = 0;
g.Create(V_count-1);
for(i=0;i
if(i != indexV) g.V[i1++] = V[i];
i1 = 0; j1 = 0;
for(i=0;i
{
if(i != indexV){
j1 = 0;
for(j=0;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
V1[i].pt = pt; V1[i].Title = m_Title;
for(i=0;i
{
E1[i].state = E[i].state;
E1[i].len = E[i].len;
}
for(i=0;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
for(i=0;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
E[i].state = TRUE;
}
ФайлKursovikMinView.h
// KursovikMinView.h: interface of the CKursovikMinView class
//
///////////////////////////////////////////////////////////////////////////// продолжение
--PAGE_BREAK--
#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
#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
{
str.Format(«Point-%i»,i);
m_graph.SetV(i,CPoint(20+rand()%100,20+rand()%100),str);
}
for(i=0;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){ продолжение
--PAGE_BREAK--
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
if((fabs(m_graph.V[i].pt.x-point.x)
{ 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
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
{
for(j=0;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();
}