Помощь - Поиск - Пользователи - Календарь
Полная версия: си и паскаль
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Прогр@ммиsт
// lb-sim-batch
// © A.C. Kaporis, L.K. Kirousis, and E.C. Stavropoulos, 2006
//
// Purpose:
//
// Computes the maximum cut of a random generated graph G in G(n,m)
// from average degree dl to average degree du, with step dstep
// n=2^k is the number of nodes of G
// m=d*n/2 is the number of edges of G
//
// Syntax:
//
// lb-sim-batch [k] [dl] [du] [step] [output file name]
// k is the exponent of a power of 2, while
// dl is the lower value of average degree of G
// du is the upper value of average degree of G
// dstep is the value of increasing the average degree of G
// The output is directed to output file name (also to the standand output)
//
// Output format:
//
// number of nodes, average degree, and the maximum cut of graph G
//
// Reference paper:
//
// A.C. Kaporis, L.K. Kirousis, and E.C. Stavropoulos,
// Approximating almost all instances of Max-Cut within a ratio above the H{\aa}stad threshold.
// In Proc. of ESA 2006, LNCS 4168, pp. 432--443, 2006
//


#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>


#define UNCOLORED -1
#define RED 0
#define BLUE 1
#define MAXVARS 100

typedef struct _Tneigh
{
int who;
struct _Tneigh *next;
} Tneigh;

typedef struct
{
Tneigh *neigh;
int degree;
} Tnode;

typedef struct
{
int neighcolored[2];
int mycolor;
} Tnodecolor;

Tnode *nodes;
Tnodecolor *nodecolors;

int k, numofnodes, numofedges;
double c, cl, cu, cstep;
double d, dl, du, dstep;

FILE *fp;
int decimation_cut=0;


void *alloc (size_t n)
{
void *ret;

ret = malloc(n);
if (ret == 0)
{
printf ("out of memory! Exiting...\n");
exit(0);
}
return (ret);
}

int randomnumber (int size)
{
return (rand() % size);
}

void initgraph ()
{
int i;

nodes = (Tnode *) alloc (numofnodes*sizeof (Tnode));
nodecolors = (Tnodecolor *) alloc (numofnodes*sizeof(Tnodecolor));

for (i=0;i<numofnodes;++i)
{
nodes[i].degree = 0;
nodes[i].neigh = 0;
}

}

void freegraph ()
{
int i;
Tneigh *p, *pnext;

for (i=0;i<numofnodes;++i)
{
p=nodes[i].neigh;
while (p)
{
pnext = p->next;
free (p);
p=pnext;
}
}

free (nodes);
free (nodecolors);
}

void randomgraph ()
{
int i, distinct, endpoint1, endpoint2;
Tneigh *p, *prev;

for (i=0;i<numofedges;++i)
{
endpoint1 = randomnumber (numofnodes);
distinct = 0;
while (!distinct)
{
endpoint2 = randomnumber (numofnodes);
if (endpoint2 != endpoint1)
distinct = 1;
}
if (nodes[endpoint1].degree == 0)
{
nodes[endpoint1].neigh = (Tneigh *) alloc (sizeof(Tneigh));
nodes[endpoint1].neigh->who = endpoint2;
nodes[endpoint1].neigh->next = 0;
}
else
{
p = nodes[endpoint1].neigh;
while (p)
{
prev = p;
p = p->next;
}
p = (Tneigh *) alloc (sizeof(Tneigh));
prev->next = p;
p->who = endpoint2;
p->next = 0;
}
nodes[endpoint1].degree++;

if (nodes[endpoint2].degree == 0)
{
nodes[endpoint2].neigh = (Tneigh *) alloc (sizeof(Tneigh));
nodes[endpoint2].neigh->who = endpoint1;
nodes[endpoint2].neigh->next = 0;
}
else
{
p = nodes[endpoint2].neigh;
while (p)
{
prev = p;
p = p->next;
}
p = (Tneigh *) alloc (sizeof(Tneigh));
prev->next = p;
p->who = endpoint1;
p->next = 0;
}
nodes[endpoint2].degree++;
}

for (i=0;i<numofnodes;++i)
{
nodecolors[i].mycolor = UNCOLORED;
nodecolors[i].neighcolored[RED] = 0;
nodecolors[i].neighcolored[BLUE] = 0;
}
}

int countcut ()
{
int i,cut;

cut =0;
for (i=0;i<numofnodes;++i)
if (nodecolors[i].mycolor == BLUE)
cut += nodecolors[i].neighcolored[RED];
return (cut);

}


//delete edge (endpoint1, endpoint2) where deg(endpoint1)=0
void delete_edge(int endpoint1, int endpoint2)
{
Tneigh *p, *pnext;
int found=0;

if (nodes[endpoint1].degree == 1)
nodes[endpoint1].neigh = 0;
nodes[endpoint1].degree--;

if (nodes[endpoint2].degree == 1)
nodes[endpoint2].neigh = 0;
else{
if (nodes[endpoint2].neigh->who == endpoint1)
nodes[endpoint2].neigh = nodes[endpoint2].neigh->next;
else
{
p=nodes[endpoint2].neigh;
while(!found){
pnext = p->next;
if (pnext->who == endpoint1){
found=1;
p->next = pnext->next;
}
else
p=p->next;
}
}
}
nodes[endpoint2].degree--;
}//delete_edge


void decimation()
{
Tneigh *p;
int i,j;

int endpoint1, endpoint2;
for (j=0; j<numofnodes; j++)
for (i=0;i<numofnodes;++i){
if (nodes[i].degree == 1) {
endpoint1 = i;
p=nodes[i].neigh;
endpoint2 = p->who;
delete_edge(endpoint1, endpoint2);
decimation_cut++;
}
}
}


//////////////////////////////////////////////////////////////////////////////
///////////////////////// Coloring Algorithm /////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
void color_ESA2006 ()
{
int i,j,n;
int discrepancy;
int max_discrepancy = -1;
int uncolored_degree;
int min_uncolored_degree = numofedges;
int numofcolorednodes = 0;

Tneigh *p;

for (i=0;i<numofnodes;++i)
{
nodecolors[i].mycolor = UNCOLORED;
nodecolors[i].neighcolored[RED] = 0;
nodecolors[i].neighcolored[BLUE] = 0;
}

while (numofcolorednodes < numofnodes)
{

//color all nodes with uncolored_degree=0
for (j=0;j<numofnodes;++j)
{
if (nodecolors[j].mycolor == UNCOLORED )
{
uncolored_degree = nodes[j].degree - nodecolors[j].neighcolored[BLUE] - nodecolors[j].neighcolored[RED];
if (uncolored_degree == 0) //color it now
{
n = j;
numofcolorednodes++;
//printf("%d \t color node %d with uncolored_degree %d \n", numofcolorednodes, n, uncolored_degree);
if (nodecolors[n].neighcolored[RED] > nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = BLUE;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[BLUE]++;
p=p->next;
}
}
else if (nodecolors[n].neighcolored[RED] < nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = RED;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[RED]++;
p=p->next;
}
}
else
{
nodecolors[n].mycolor = randomnumber (2);
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[nodecolors[n].mycolor]++;
p=p->next;
}
}
}
}
}


// find an uncolored node with max discrepancy
max_discrepancy = -1;
for (j=0;j<numofnodes;++j)
{
if (nodecolors[j].mycolor == UNCOLORED && nodes[j].degree > 1)
{
discrepancy = abs(nodecolors[j].neighcolored[BLUE]-nodecolors[j].neighcolored[RED]);
if (discrepancy > max_discrepancy)
{
n = j;
max_discrepancy = discrepancy;
}
}
}

//find an uncolored node with max_discrepancy having the minimun number of uncolored neighbors
min_uncolored_degree = numofedges;
for (j=0;j<numofnodes;++j)
{
if (nodecolors[j].mycolor == UNCOLORED && nodes[j].degree > 1)
{
discrepancy = abs(nodecolors[j].neighcolored[BLUE]-nodecolors[j].neighcolored[RED]);
if (discrepancy == max_discrepancy)
{
uncolored_degree = nodes[j].degree-nodecolors[j].neighcolored[RED]-nodecolors[j].neighcolored[BLUE];
if (uncolored_degree < min_uncolored_degree)
{
min_uncolored_degree = uncolored_degree;
n = j;
}
}

}
}

//color node n
if (nodecolors[n].mycolor == UNCOLORED && nodes[n].degree > 1)
{
numofcolorednodes++;
if (nodecolors[n].neighcolored[RED] > nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = BLUE;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[BLUE]++;
p=p->next;
}
}
else if (nodecolors[n].neighcolored[RED] < nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = RED;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[RED]++;
p=p->next;
}
}
else
{
nodecolors[n].mycolor = randomnumber (2);
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[nodecolors[n].mycolor]++;
p=p->next;
}
}
}
}
}




//////////////////////////////////////////////////////////////////////////////
////////////////////////////////// MAIN //////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
int main(int argc,char *argv[])
{

if (argc != 6) {
printf("Syntax: lb-sim [k] [dl] [du] [dstep] [output file name] \n");
exit(1);
}

srand( (unsigned)time( NULL ) );

k = atoi(argv[1]);
numofnodes = (int) pow(2,k);

dl = atof(argv[2]);
cl = 0.5*dl;

du = atof(argv[3]);
cu = 0.5*du;

dstep = atof(argv[4]);
cstep = 0.5*dstep;

d = dl;
c = 0.5*d;


while (c < cu + cstep)
{
numofedges = (int) (c*numofnodes);

initgraph ();

randomgraph ();

decimation_cut=0;
decimation ();

color_ESA2006 ();

printf ("n=%d \t d=%4.1f \t cut=%10.8f \n",
numofnodes, 2.0*c, (double) (countcut()+ decimation_cut) / (double) numofedges);

fp = fopen(argv[5], "a");

fprintf (fp, "n=%d \t d=%4.1f \t cut=%10.8f \n",
numofnodes, 2.0*c, (double) (countcut()+ decimation_cut) / (double) numofedges);

fclose(fp);

freegraph();

c = c + cstep;
}

return 0;
}//main




помогите реализоват это на паскале
Michael_Rybak
начни сам и задавай конкретные вопросы.
Прогр@ммиsт
я си не знаю.Как эта программа будет на паскале нужен исходник .
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.