#include "stdafx.h"
#include <stdlib.h>
#include <cstdlib>
#include <iostream>
#include <time.h>
#include <Windows.h>
#include <string>
#define threadCount 4

#define random() (float)rand()/(float)RAND_MAX
#define nmax 20
CRITICAL_SECTION sekcja;
using namespace std;
    typedef int t2[nmax][nmax];
    typedef int t1[nmax];

void permInit(int n, t1 p)
{
    int i;
    for (i=0;i<n;i++)
        p[i]=i;
    }

int permNext(int n, t1 p)
{
    int i,j,x,b;
    b=0;
      i=n1;
        while (i>0)
    {
        if (p[i]>p[i1])
        {
            j=n1;
              while (p[j] < p[i1])
                  j;
                  x=p[j];
                    p[j]=p[i1]
                         ;
                         p[i1]=
                             x;
                             while (i<n)
                {
                    x=p[i]; p[i]=p[n1]
                                  ; p[n1]=
                                      x;
                                      i++; n;
                };
            b=1;
              break;
        }
        i;
    }
    return b;
}
void druk(int n, int L, t1 p)
{
    int i;
    printf("%d: ",L);
    for (i=0;i<n;i++)
        printf("%d ",p[i]);
        printf("\n");
    }

void gnp(int n, float p, t2 A)
{
int i,j;
for (i=0;i<n;i++) A[i][i] = 0;
                                  for (i=0;i<n1;i++)
                                      for (j=i+1;j<n;j++)
        {
            A[i][j]=A[j][i]= (random() <= p);
        }
}

int maxDiffrence(int n, t2 A, t1 perm)
{
    int dist, best = 1;
                     int i,j;
                     for (i=0;i<n1;i++)
                         for (j=i+1;j<n;j++) if (A[i][j])
            {
                dist = abs(perm[i]perm[
                               j]);
                       if (dist>best) best = dist;
                }
    return best;
}
float p = 0.5f;
          t2 A;
          t1 perm;
          int n = 5;
                  int naj_r,szerokosc;
                  int L = 1;
                          int* wyniki;
                          DWORD WINAPI countPartially(LPVOID i)
{
    t1 permtemp;
    int x = (int)i;
            for (int j =1;j<n;j++)
    {
        permtemp[j] = perm[j];
    }
    permtemp[0] = x;
                  permtemp[x] = 0;
                                int temp = 0;
                                           for (int k = 1;k<n;k++)
    {
        for (int l = 1;l<n1;l++)
        {
            if (permtemp[l]>permtemp[l+1])
            {
                temp = permtemp[l];
                       permtemp[l] = permtemp[l+1];
                                     permtemp[l+1] = temp;
            }
        }
    }
    int max;
    do
    {
        if (permtemp[0]!=x) break;
            max = maxDiffrence(n,A,permtemp);
                  if (max<szerokosc) szerokosc = max;
                                                     printf("Watek %d: ",x);
                                                     druk(n,L,permtemp);
                                                     L++;
            }
    while (permNext(n,permtemp));
        wyniki[x] = szerokosc;
                    return 0;
    }

void count ()
{
    wyniki = new int[n];
    HANDLE *threads = new HANDLE [n];
    for (int i = 0; i<n ;i++)
    {
        threads[i] = CreateThread( NULL, 0, countPartially, (LPVOID) i,0,NULL);
    }
    WaitForMultipleObjects((DWORD)n,threads,true,INFINITE);
    delete threads;
}

int _tmain(int argc, _TCHAR* argv[])
{
    gnp(n,p,A);
    szerokosc = n1;
                permInit(n,perm);
                count();
                int min = n;
                          for (int i = 0;i<n;i++)
    {
        if (wyniki[i]< min) min = wyniki[i];
        }
    printf("\nSzerokosc grafu %d\n\n\n",min);
    system("pause");
    return 0;
}