Смекни!
smekni.com
Математика

Алгоритм раскраски графа (точный) (стр. 3 из 4)

{

//{{AFX_DATA_INIT(CKursovojDlg)

//}}AFX_DATA_INIT

// Note that LoadIcon does not require a subsequent DestroyIcon in Win32

m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

}

void CKursovojDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CKursovojDlg)

DDX_Control(pDX, IDC_BUTTON4, m_r1);

DDX_Control(pDX, IDC_LIST3, m_l3);

DDX_Control(pDX, IDC_LIST2, m_l2);

DDX_Control(pDX, IDC_LIST1, m_l1);

DDX_Control(pDX, IDC_STATIC1, m_n1);

DDX_Control(pDX, IDC_BUTTON3, m_sbros);

DDX_Control(pDX, IDC_BUTTON2, m_primizm);

DDX_Control(pDX, IDC_BUTTON1, m_nach);

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP(CKursovojDlg, CDialog)

//{{AFX_MSG_MAP(CKursovojDlg)

ON_WM_SYSCOMMAND()

ON_WM_PAINT()

ON_WM_QUERYDRAGICON()

ON_BN_CLICKED(IDC_BUTTON1, OnButton1)

ON_BN_CLICKED(IDC_RADIO1, OnRadio1)

ON_BN_CLICKED(IDC_RADIO2, OnRadio2)

ON_BN_CLICKED(IDC_STATIC1, OnStatic1)

ON_WM_LBUTTONDOWN()

ON_BN_CLICKED(IDC_BUTTON2, OnButton2)

ON_BN_CLICKED(IDC_BUTTON3, OnButton3)

ON_BN_CLICKED(IDC_BUTTON4, OnButton4)

ON_BN_CLICKED(IDC_BUTTON5, OnButton5)

ON_BN_CLICKED(IDC_BUTTON6, OnButton6)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

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

// CKursovojDlg message handlers

BOOL CKursovojDlg::OnInitDialog()

{

CDialog::OnInitDialog();

// Add "About..." menu item to system menu.

// IDM_ABOUTBOX must be in the system command range.

ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);

ASSERT(IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu(FALSE);

if (pSysMenu != NULL)

{

CString strAboutMenu;

strAboutMenu.LoadString(IDS_ABOUTBOX);

if (!strAboutMenu.IsEmpty())

{

pSysMenu->AppendMenu(MF_SEPARATOR);

pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

}

}

// Set the icon for this dialog. The framework does this automatically

// when the application's main window is not a dialog

SetIcon(m_hIcon, TRUE);// Set big icon

SetIcon(m_hIcon, FALSE);// Set small icon

// TODO: Add extra initialization here

return TRUE; // return TRUE unless you set the focus to a control

}

//------------------------------------------------------------------------------------------

void CKursovojDlg::ud(void)

{

int q;

int min,buf;

for (int u=0 ; u<masskol*2; u++)

for (int i=1 ; i<mass[u][0] ; i++)

{

min=i;

for (int j=i+1 ; j<mass[u][0]+1 ; j++)

if (mass[u][j]<mass[u][min]) min=j;

if (i!=min)

{

buf= mass[u][i];

mass[u][i] = mass[u][min];

mass[u][min]= buf;

}

}

for (int i=0 ; i<masskol*2 ; i++)

for (int y=0 ; y<masskol*2 ; y++)

if (i!=y)

{

q=0;

if ((mass[i][0]==mass[y][0])&&(mass[i][0]>0))

for (int k=1; k<mass[y][0]+1; k++)

if (mass[i][k]==mass[y][k]) q++;

if (q==mass[y][0])

{

mass[y][0]=-1;

}

}

for (i=0 ; i<masskol*2 ; i++)

for (int y=0 ; y<masskol*2 ; y++)

if (i!=y)

{

q=0;

if ((mass[i][0]+1)==mass[y][0])

for (int j=1; j<mass[i][0]+1; j++)

for (int k=1; k<mass[y][0]+1; k++)

if (mass[i][j]==mass[y][k]) q++;

if (q==mass[i][0])

{

mass[y][0]=-1;

}

}

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::perre(void)

{

int q;

for (int i=0 ; i<masskol*2 ; i++)

{

q=0;

for (int j=1; j<mass[i][0]+1; j++)

for (int k=1; k<mass[i][0]+1; k++)

if (j!=k)

if (mass[i][j]==mass[i][k]) q=k;

if (q!=0)

{

for ( j=1; j<mass[i][0]+1; j++)

if (j>=q) mass[i][j]=mass[i][j+1];

mass[i][0]=mass[i][0]-1;

}

}

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::peremf(int st1)

{

int k;

masskol=2;

for (int i=2 ; i<kolv+1 ; i++)

{

k=umnf[i][0];

for (int s=1; s<k; s++)

for (int ki=0 ; ki<masskol ; ki++)

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

mass[masskol*s+ki][j]=mass[ki][j];

for (s=0 ; s<k; s++)

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

if (mass[masskol*s+j][0]>0)

{

mass[masskol*s+j][0]=mass[masskol*s+j][0]+1;

mass[masskol*s+j][mass[masskol*s+j][0]]=umnf[i][s+1];

}

k=masskol;

masskol=1000;

perre();

ud();

masskol=k*umnf[i][0];

}

masskol=1000;

perre();

ud();

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::perem(int st1)

{

int k=0;

masskol=0;

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

if (mass[i][0]!=0) masskol++;

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

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

mass[masskol+i][j]=mass[i][j];

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

{

if (mass[j][0]>0){

mass[j][0]=mass[j][0]+1;

mass[j][mass[j][0]]=umn[st1].x1;}

if (mass[masskol+j][0]>0){

mass[masskol+j][0]=mass[masskol+j][0]+1;

mass[masskol+j][mass[masskol+j][0]]=umn[st1].x2;}

}

perre();

ud();

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::provf(void)

{

int min,buf;

for (int u=0 ; u<kolv+1; u++)

for (int i=1 ; i<umnf[u][0] ; i++)

{

min=i;

for (int j=i+1 ; j<umnf[u][0]+1 ; j++)

if (umnf[u][j]<umnf[u][min]) min=j;

if (i!=min)

{

buf= umnf[u][i];

umnf[u][i] = umnf[u][min];

umnf[u][min]= buf;

}

}

int k;

for (int i=1; i<kolv+1 ; i++)

for (int j=1; j<kolv+1 ; j++)

if (i!=j)

if (umnf[i][0]==umnf[j][0])

{

k=0;

for (int t=1 ; t<umnf[i][0]+1 ; t++)

if(umnf[i][t]==umnf[j][t]) k++;

if (k==umnf[i][0]) umnf[j][0]=-1;

}

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::prov(void)

{

int k;

for (int i=1; i<colvo+1 ; i++)

for (int j=1; j<colvo+1 ; j++)

if (i!=j)

{

k=0;

if ((umn[i].x1==umn[j].x1)&&(umn[i].x2==umn[j].x2)) umn[j].x1=-1;

if ((umn[i].x2==umn[j].x1)&&(umn[i].x1==umn[j].x2)) umn[j].x1=-1;

}

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::raskr(void)

{

const int rad=15;

CClientDCdc(this);

//Создать новое перо

CPen MyNewPen;

MyNewPen.CreatePen(PS_SOLID, 1, RGB(0,0,0));

CBrush br;

br.CreateSolidBrush(RGB(0,200,200));

//Выбрать перо

CPen* pOriginalPen;

CBrush* pbr;

pOriginalPen=dc.SelectObject(&MyNewPen);

pbr=dc.SelectObject(&br);

//Нарисовать круг

SetBkMode(dc,TRANSPARENT);

int kp,nea;

char buf[3];

int pr[1000];

int p=rat;

rat++;

if (rat==rav+1) {rask=-1; rat=1;}

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

if ((mass[i][0]>0)&&(mass[i][1]>0)) if (((i>rask)&&(p!=rat))||(rat==rav))

{

pr[0]=0; p=rat; rask=i;

for (int t=1; t<mass[i][0]+1 ; t++)

{

nea=0;

for (int u=1; u<fff[mass[i][t]][0]+1; u++)

if (fff[mass[i][t]][u]!=0)

{

kp=0;

for (int y=1; y<pr[0]+1; y++)

if (pr[y]==u) kp=1;

if (kp==0) {

pr[0]++; pr[pr[0]]=u;

CRect MyRectangle(versh[u].x-rad,versh[u].y-rad,versh[u].x+rad,versh[u].y+rad);

dc.Ellipse(&MyRectangle);

itoa(u,buf,10);

if (u>9)

dc.TextOut(versh[u].x-8,versh[u].y-8,buf);

else dc.TextOut(versh[u].x-4,versh[u].y-8,buf);}

}

br.DeleteObject();

br.CreateSolidBrush(RGB(rand(),rand(),rand()));

pbr=dc.SelectObject(&br);

}

}

UpdateData(TRUE);

m_l3.SetCurSel(m_l3.GetCount()-1-rav+rat);

}

//------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------

void CKursovojDlg::k(void)

{

CString str;

char ch[5];

for (int i=1; i<kolv+1 ; i++)

for (int j=1; j<kolv+1 ; j++)

if (matsm[i][j]==1)

{

if (i<j)

{

colvo++;

umn[colvo].x1=i;

umn[colvo].x2=j;

} else

{

colvo++;

umn[colvo].x1=j;

umn[colvo].x2=i;

}

}

for ( i=1; i<1000 ; i++)

for (int j=1; j<100 ; j++)

mass[i][j]=0;

prov();

str="";

m_l3.ResetContent();

int nea=0;

for ( i=1; i<colvo+1 ; i++)

if (umn[i].x1!=-1)

{

nea=1;

str+="(x";

itoa(umn[i].x1,ch,10);

str+=ch;

str+="+x";

itoa(umn[i].x2,ch,10);

str+=ch;

str+=")";

if (str.GetLength()>40) {m_l3.AddString(str);str="";nea=0;}

}

if (nea!=0) m_l3.AddString(str);

mass[0][0]=1;

mass[1][0]=1;

mass[0][1]=umn[1].x1;

mass[1][1]=umn[1].x2;

masskol=2;

for ( i=2 ; i<colvo+1; i++)

if (umn[i].x1>-1) perem(i);

ud();

str="";

int kp=0;

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

if (mass[i][0]>0)

{

nea=1;

if (kp>0) str+="+";

kp++;

for (int j=1; j<mass[i][0]+1 ; j++)

if (mass[i][j]>0) {str+="x";

itoa(mass[i][j],ch,10);

str+=ch;}

if (str.GetLength()>40) {m_l3.AddString(str);str="";nea=0;}

}

if (nea!=0) m_l3.AddString(str);

for ( i=1; i<1000 ; i++)

for (int j=1; j<100 ; j++)

fff[i][j]=0;

m_l2.ResetContent();

colf=0;

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

if (mass[i][0]>0)

{

if (kolv!=mass[i][0])

{

colf++;

fff[colf][0]=0;

for (int t=1; t<kolv+1 ; t++)

{

nea=0;

for (int j=1; j<mass[i][0]+1 ; j++)

if ((mass[i][j]>0)&&(mass[i][j]==t)) nea=1;

if (nea==0) { fff[colf][0]++; fff[colf][fff[colf][0]]=1;}

else { fff[colf][0]++; fff[colf][fff[colf][0]]=0;}

}

}

}

m_l2.ResetContent();

str="";

for ( i=1 ; i<fff[1][0]+1 ; i++)

{

for (int j=1 ; j<colf+1; j++)

{

itoa(fff[j][i],ch,10);

str+=ch;

str+=" ";

}

m_l2.AddString(str);

str="";

}

for ( i=1; i<1000 ; i++)

for (int j=1; j<100 ; j++)

mass[i][j]=0;

for ( i=1; i<1000 ; i++)

for (int j=1; j<100 ; j++)

umnf[i][j]=0;

for ( i=1; i<colf+1; i++)

for (int j=1; j<fff[i][0]+1; j++)

if (fff[i][j]!=0) {umnf[j][0]++; umnf[j][umnf[j][0]]=i;}

provf();

str="";

for ( i=1 ; i<kolv+1 ; i++)

if (umnf[i][0]>0)

{

nea=1;

str+="(";

kp=0;

for (int j=1 ; j<umnf[i][0]+1 ; j++)

{

if (kp!=0) str+="+";

kp++;

str+="F";

itoa(umnf[i][j],ch,10);

str+=ch;

}

str+=")";

if (str.GetLength()>40) {m_l3.AddString(str);str="";nea=0;}

}

masskol=0;

if (nea!=0) m_l3.AddString(str);

for (int j=1 ; j<umnf[1][0]+1 ; j++)

if (umnf[1][j]!=0)

{

mass[masskol][0]=1;

mass[masskol][1]=umnf[1][j];

masskol++;

}

peremf(1);

str="";

kp=0;

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

if (mass[i][0]>0)

{

nea=1;

if (kp>0) str+="+";

kp++;

for (int j=1; j<mass[i][0]+1 ; j++)

if (mass[i][j]>0) {str+="F";

itoa(mass[i][j],ch,10);

str+=ch;}

if (str.GetLength()>40) {m_l3.AddString(str);str="";nea=0;}

}

if (str[str.GetLength()-1]=='+') m_l3.AddString("0");

if (nea!=0) m_l3.AddString(str);

str="";

rav=0;

int pr[1000];

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

if ((mass[i][0]>0)&&(mass[i][1]>0))

{

for (int j=1; j<mass[i][0]+1 ; j++)

if (mass[i][j]>0) {str+="F";

itoa(mass[i][j],ch,10);

str+=ch;}

str+="={";

pr[0]=0;

rav++;

for (int t=1; t<mass[i][0]+1 ; t++)

{

nea=0;

for (int u=1; u<fff[mass[i][t]][0]+1; u++)

if (fff[mass[i][t]][u]!=0)

{

kp=0;

for (int y=1; y<pr[0]+1; y++)

if (pr[y]==u) kp=1;

if (kp==0) {

pr[0]++; pr[pr[0]]=u;

if (nea>0) str+=",";

nea++;

str+="x";

itoa(u,ch,10);

str+=ch;}

}

str+=";";

}

str+="}";

m_l3.AddString(str);

str="";

}

rask=-1; rat=0; raskr();

}

//------------------------------------------------------------------------------------------

void CKursovojDlg::OnSysCommand(UINT nID, LPARAM lParam)

{

if ((nID & 0xFFF0) == IDM_ABOUTBOX)

{

CAboutDlg dlgAbout;

dlgAbout.DoModal();

}

else

{

CDialog::OnSysCommand(nID, lParam);

}

}

// If you add a minimize button to your dialog, you will need the code below

// to draw the icon. For MFC applications using the document/view model,

// this is automatically done for you by the framework.

void CKursovojDlg::OnPaint()

{

if (IsIconic())

{

CPaintDC dc(this); // device context for painting

SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

// Center icon in client rectangle

int cxIcon = GetSystemMetrics(SM_CXICON);

int cyIcon = GetSystemMetrics(SM_CYICON);

CRect rect;

GetClientRect(&rect);

int x = (rect.Width() - cxIcon + 1) / 2;

int y = (rect.Height() - cyIcon + 1) / 2;

// Draw the icon

dc.DrawIcon(x, y, m_hIcon);

}

else

{

CDialog::OnPaint();

}

const int rad=15;

CClientDCdc(this);

//Создать новое перо

CPen MyNewPen;

MyNewPen.CreatePen(PS_SOLID, 1, RGB(0,0,0));

CBrush br;

br.CreateSolidBrush(RGB(200,200,200));

//Выбрать перо

CPen* pOriginalPen;

CBrush* pbr;

pOriginalPen=dc.SelectObject(&MyNewPen);

pbr=dc.SelectObject(&br);

//Нарисовать круг

SetBkMode(dc,TRANSPARENT);

for (int j=1; j<kolreb+1; j++)

{

dc.MoveTo(versh[rebro[j].n].x,versh[rebro[j].n].y);

dc.LineTo(versh[rebro[j].k].x,versh[rebro[j].k].y);

}

for (int i=1 ; i<kolv+1; i++)

{

char buf[3];

CRect MyRectangle(versh[i].x-rad,versh[i].y-rad,versh[i].x+rad,versh[i].y+rad);

dc.Ellipse(&MyRectangle);

itoa(i,buf,10);

if (i>9)

dc.TextOut(versh[i].x-8,versh[i].y-8,buf);

else dc.TextOut(versh[i].x-4,versh[i].y-8,buf);

}

if (rav!=0)

{

int k,l;

k=rask;

l=rat;

raskr();

rask=k;

rat=l;

}

}

// The system calls this to obtain the cursor to display while the user drags

// the minimized window.

HCURSOR CKursovojDlg::OnQueryDragIcon()

{

return (HCURSOR) m_hIcon;

}

void CKursovojDlg::OnButton1()

{

// TODO: Add your control notification handler code here

UpdateData(TRUE);

m_nach.EnableWindow(false);

k();

m_r1.EnableWindow(true);

}

void CKursovojDlg::OnRadio1()

{

// TODO: Add your control notification handler code here

radio=1;

}

void CKursovojDlg::OnRadio2()

{

// TODO: Add your control notification handler code here

radio=2;

}

void CKursovojDlg::OnStatic1()

{

}

void CKursovojDlg::OnLButtonDown(UINT nFlags, CPoint point)

{

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

 
назад
читать дальше
1
2
3
4
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.