Поиск максимального независимого множества графа с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска η-областей

Приложение  А: Экранные формы.

Рисунок А.1: пустое рабочее поле

Рисунок А.2: загрузка графа из файла

Рисунок А.3: построение графа

Рисунок А.4: поиск МНМ 
 

 

Приложение  Б: Код программы.

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

#define IMG Form1->Image1->Canvas 

#include <vcl.h>

#include <math.h>

#include <cstdio>

#include <conio.h>

#include <iostream.h>

#pragma hdrstop 

#include "Unit1.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1; 

const int N = 1000;

const int R = 6;

int QPnt = 0;

int QEdg = 0;

bool Select1 = false;

bool Select2 = false;

bool fBuild = true;

bool fMove = false;

int icurr, xm, ym;

int AdjMatr[50][50];

int MNM[50];

int MNM2[50];

int MNM3[50];

int size;

int size2; 

struct XY

{

        int x;

        int y;

        int inc;

}Points[N],edge1,edge2; 

struct EDGE

{

        XY p1;

        XY p2;

}Edges[N]; 

struct STACK

{

       int data[50];

       int size;

};

void Push(STACK &a, int d)

{

     a.size++;

     a.data[a.size] = d;

}

int Pop(STACK &a)

{

    int d;

    d = a.data[a.size];

    a.data[a.size] = 0;

    a.size--;

    return d;

} 

void CleanWind()

{

        QPnt = 0;

        QEdg = 0;

        Select1 = false;

        Select2 = false;

        IMG->Brush->Color = clWhite;

        IMG->FillRect(Form1->Image1->ClientRect);

        IMG->Brush->Color = clBlack;

        IMG->FrameRect(Form1->Image1->ClientRect);

} 

void PutPoint(int x, int y)

{

        IMG->Ellipse(x-R,y-R,x+R,y+R);

        Points[QPnt].x = x;

        Points[QPnt].y = y;

        QPnt++;

} 

void PutEdge(XY pnt1, XY pnt2)

{

        IMG->MoveTo(pnt1.x,pnt1.y);

        IMG->LineTo(pnt2.x,pnt2.y); 

        Edges[QEdg].p1 = pnt1;

        Edges[QEdg].p2 = pnt2;

        QEdg++;

} 

void DelEdge(int i_del)

{

    IMG->Pen->Color = clWhite;

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

    {

        IMG->MoveTo(Points[icurr].x,Points[icurr].y);

        if ((Edges[i].p1.x==Points[i_del].x)&&(Edges[i].p1.y==Points[i_del].y))

        {

                IMG->LineTo(Edges[i].p2.x,Edges[i].p2.y);

                for (int j = i; j<QEdg-1; j++)

                    Edges[j] = Edges[j+1];

                QEdg--;

                i--;

        }

        IMG->MoveTo(Points[icurr].x,Points[icurr].y);

        if ((Edges[i].p2.x==Points[i_del].x)&&(Edges[i].p2.y==Points[i_del].y))

        {

                IMG->LineTo(Edges[i].p1.x,Edges[i].p1.y);

                for (int j = i; j<QEdg-1; j++)

                    Edges[j] = Edges[j+1];

                QEdg--;

                i--;

        }

    }

} 

void DelPoint(int i_del)

{

       DelEdge(i_del);

       IMG->Pen->Color = clWhite;

       IMG->Brush->Color = clWhite;

       IMG->Ellipse(Points[i_del].x-R,Points[i_del].y-R,Points[i_del].x+R,Points[i_del].y+R); 

       for (int i = i_del; i<QPnt-1; i++)

          Points[i] = Points[i+1];

       QPnt--;

} 
 

void Tkach()

{

        int i=0;

        int j=0;

        size = QPnt;

        for (int y = 0; y<QPnt; y++)

                MNM[y] = y; 

        for (int Ki = 0; Ki<size; Ki++)

        {

            i = MNM[Ki];

            for (int Kj = 0; Kj<size; Kj++)

            {

                 j = MNM[Kj];

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

                 {

                     int s1=0,s2=0;

                     for (int j1=0; j1<size; j1++)

                        s1+=AdjMatr[i][MNM[j1]];

                     for (int i1=0; i1<size; i1++)

                        s2+=AdjMatr[MNM[i1]][j];

                     if (s2>=s1)

                     {

                           for (int k=Kj; k<size-1; k++)

                                MNM[k] = MNM[k+1];

                           MNM[size-1]=0;

                           size--;

                           Kj--;

                     }

                     if (s2<s1)

                     {

                           for (int k=Ki; k<size-1; k++)

                                MNM[k] = MNM[k+1];

                           MNM[size-1]=0;

                           size--;

                           Ki--;

                           break;

                     }

                 }

            }

        }

} 
 

void Bron()

{                

    STACK comp;

    int elem[10];

    comp.size = -1;

    int ne = 0;

    int ce = QPnt-1;

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

          elem[i] = i; 

    int cnt = 1;

    bool newn = true;

    size2 = 0;

    int lim = QPnt-1; 

    while (ne!=(QPnt-1))

    {

       if (newn)

       {

          Push(comp,elem[ne]);

          newn = false;

          lim = QPnt-1;

          for (int i=QPnt-1; i>=0; i--)

                if (AdjMatr[ne][i]==0)

                {

                    ce = i;

                    break;

                }

       }

      

       for (int i=ne+1; i<=lim; i++)

       {

           bool f=true;

           for (int k=0; k<=comp.size; k++)

              if (AdjMatr[comp.data[k]][i]==1)

              {

                f=false;

                break;

              }

           if (f)

              Push(comp,i);

       } 

       if (size2 < comp.size+1)

           {

                size2 = comp.size+1;

                for (int i=0; i<=comp.size; i++)

                        MNM2[i] = comp.data[i];

           } 

       if (ne!=ce)

       {

           ne = Pop(comp);

           lim = ce;    

       }

       else

       {

           ne = cnt;

           cnt++;

           comp.size = -1;

           if ((QPnt-ne)<=size2) return;

           newn = true;

       }

    }

} 
 

void Eta()

{

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

            MNM3[i]=i; 

        bool flag = false, f1=false,f2=false;

        int sp1,se1,sp2,se2; 

        while (!flag)