sagraph.txt

模拟退火算法求解经典图论中的图着色问题的源程序

/* 
 * Module: Graph Drawing using Simulated Annealing
 * Programmer: Girish Keshav Palshikar
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "simann.h"
#include "graph.h"
#include "g_draw.h"

// global variables
GRAPH G;  
STATE S;  

// Generate a random placement for the given graph
// return 0 upon completion
int RandomState(STATE *pS)
{
   int i, j, n, x, y;
   BOOL duplicate;

   n = pS->pG->nVertexCount; // no. of vertices in the graph
   for ( i = 0; i < n; i++ )
   {
       x = RANDOM(0,(MAX_X - 1));
       y = RANDOM(0,(MAX_Y - 1));
       
       // ensure that the position generated is not already allocated to
       // some other vertex
       for ( j = 0, duplicate = FALSE; j < i; j++ )
       {
	   if ( pS->aXPos[j] == x && pS->aYPos[j] == y )
	   {
	      duplicate = TRUE;
	      break;
	   }
       } // end for
       if ( duplicate )
	   --i;  // force retry for ith vertex
       else
       {
	   pS->aXPos[i] = x;
	   pS->aYPos[i] = y;
       }
   } // end for
   
   pS->aXPos[n] = END_MARKER;
   pS->aYPos[n] = END_MARKER;
   return(0);
}

int PrintState(STATE *pS)
{
   int i, n;
   
   n = pS->pG->nVertexCount; // no. of vertices in the graph
   for ( i = 0; i < n; i++ )
   {
       printf("vertex i=%d: X = %d Y = %d\n", i, pS->aXPos[i], pS->aYPos[i]);
   } // end for

   return(0);
}


// get a random integer between 0 and Max (inclusive). Max must be > 0.
// return -1 on error
int GetRandom(int Max)
{
   if ( Max < 1 )
       return(-1);

   return( rand() % (Max+1) );
}

// return a state within the neighbourhood of given state
// Essentially, picks up a vertex randomly and moves it randomly to a
// neighbouring sqaure (up, down, left, right, right-up, right-down,
// left-up, left-down)
BOOL NeighbourState(STATE *pS, STATE *pNew)
{
   int n, j, v_index, x, y, x1, y1, delta_x, delta_y, sign_x, sign_y;
   BOOL duplicate;

   n = pS->pG->nVertexCount;
   do  // till the position of selected vertex is successfully changed 
   {
       v_index = RANDOM(0, (n - 1)); // select vertex randomly
       x = pS->aXPos[v_index]; // current pos of the selected vertex
       y = pS->aYPos[v_index];

       delta_x = RANDOM(0,1);
       delta_y = RANDOM(0,1);
       sign_x = RANDOM(0,1);
       sign_y = RANDOM(0,1);
       if ( sign_x ) // increment x coordinate
	  x1 = ( (x + delta_x >= MAX_X) ? (x) : (x + delta_x) );
       else // decrement x coordinate
	  x1 = ( (x - delta_x < 0) ? (x) : (x - delta_x) );
       if ( sign_y ) // increment y coordinate
	  y1 = ( (y + delta_y >= MAX_Y) ? (y) : (y + delta_y) );   
       else // decrement y coordinate
	  y1 = ( (y - delta_y < 0) ? (y) : (y - delta_y) );
       
       // ensure that the position generated is not already allocated to
       // some other vertex
       for ( j = 0, duplicate = FALSE; j < n; j++ )
       {
	   if ( pS->aXPos[j] == x1 && pS->aYPos[j] == y1 )
	   {
	      duplicate = TRUE;
	      break;
	   }
       } // end for
   } while ( duplicate || (x == x1 && y == y1) ); // do till position of vertex changes
   
   pNew->aXPos[v_index] = x1; // report the new position
   pNew->aYPos[v_index] = y1;

   return(TRUE);
}

// TRUE if given state is an acceptable solution
BOOL IsSolution(STATE s)
{
   return(FALSE); // no fixed final state for graph drawing
}

// compute and return cost or energy of given state
ENERGY Energy(STATE *pS)
{
   int i, j, n, x1, y1, x2, y2, v1, v2;
   ENERGY e = 0.0;
   double d, d1, d2, d3, d4;
   double c1, c2, c3;

   n = pS->pG->nVertexCount; // no. of vertices in the graph

   for (i = 0; i < n; i++)
   {
       x1 = pS->aXPos[i];  // position of ith vertex in the graph
       y1 = pS->aYPos[i];
       v1 = pS->pG->aVertexID[i];

       d1 = DIST_SQR(x1,y1,(MAX_X-1),y1); // right border
       d2 = DIST_SQR(x1,y1,0,y1);         // left border
       d3 = DIST_SQR(x1,y1,x1,(MAX_Y-1)); // top border
       d4 = DIST_SQR(x1,y1,x1,0);         // bottom border
       e = e + LAMBDA_2 * (
		   ( (d1 > 0.0) ? (1 / d1) : (MAX_ENERGY) ) + // 0.0
		   ( (d2 > 0.0) ? (1 / d2) : (MAX_ENERGY) ) + // 0.0                  
		   ( (d3 > 0.0) ? (1 / d3) : (MAX_ENERGY) ) + // 0.0
		   ( (d4 > 0.0) ? (1 / d4) : (MAX_ENERGY) ) ); // 0.0
       for (j = 0; j < n; j++)
       {
	   x2 = pS->aXPos[j];
	   y2 = pS->aYPos[j];
	   v2 = pS->pG->aVertexID[j];

	   // sqr of distance between (x1,y1) and (x2,y2)
	   d = DIST_SQR(x1,y1,x2,y2); 

	   if ( j < i )
	   {
	       e = e + ( (d > 0.0) ? (LAMBDA_1 / d) : (MAX_ENERGY) );
	   }

	   if ( j < i && adjacent_v(pS->pG, v1, v2) ) // only once for an edge
	   {
	       e = e + LAMBDA_3 * d;
	   }
       }
   } // end for

   return(e);
}

int CopyState(STATE *pDest, STATE *pSrc)
{
   int i, n;
   
   n = pSrc->pG->nVertexCount; // no. of vertices in the graph

   pDest->pG = pSrc->pG;
   for ( i = 0; i <= n; i++ ) // copy END_MARKER also
   {
       pDest->aXPos[i] = pSrc->aXPos[i];
       pDest->aYPos[i] = pSrc->aYPos[i];
   }
   return(0);
}

// return true if given vertices are adjacent in given graph
BOOL adjacent_v(GRAPH *pGraph, int V1, int V2)
{
   int i;

   for ( i = 0; i < pGraph->nEdgeCount; i++ )
       if ( ((pGraph->aEdge[i].nVertexID1 == V1 && 
	     pGraph->aEdge[i].nVertexID2 == V2)) ||
	    ((pGraph->aEdge[i].nVertexID1 == V2 && 
	      pGraph->aEdge[i].nVertexID2 == V1)) )
	   return(TRUE);
   return(FALSE);
}

int main()
{
   STATE SFinal;
 
   InitGraph(&G); // initialize G to contain K3,3
   S.pG = &G;
   RandomState(&S); // create a random layout for G
   SimAnneal(&S, MAX_TEMP, 600, &SFinal);
   PrintState(&SFinal);
}

// init the given graph to contain a hexagon
int InitGraph(GRAPH *pG)
{
   pG->nGraphID = 10;
   pG->eIsDirected = 0;
   pG->eIsDisconnected = 0;
   pG->eHasParallelEdge = 0;
   pG->eHasSelfLoop = 0;
   pG->nVertexCount = 6;
   pG->nEdgeCount = 6;
   pG->aVertexID[0] = 100;
   pG->aVertexID[1] = 101;
   pG->aVertexID[2] = 102;
   pG->aVertexID[3] = 103;
   pG->aVertexID[4] = 104;
   pG->aVertexID[5] = 105;
   pG->aVertexID[6] = END_MARKER;
   pG->aEdge[0].nVertexID1 = 100; pG->aEdge[0].nVertexID2 = 101;
   pG->aEdge[1].nVertexID1 = 101; pG->aEdge[1].nVertexID2 = 102;
   pG->aEdge[2].nVertexID1 = 102; pG->aEdge[2].nVertexID2 = 103;
   pG->aEdge[3].nVertexID1 = 103; pG->aEdge[3].nVertexID2 = 104;
   pG->aEdge[4].nVertexID1 = 104; pG->aEdge[4].nVertexID2 = 105;
   pG->aEdge[5].nVertexID1 = 105; pG->aEdge[5].nVertexID2 = 100;
   pG->aEdge[6].nVertexID1 = END_MARKER; pG->aEdge[6].nVertexID2 = END_MARKER;
   return(0);
}

/* File: g_draw.h */
#ifndef G_DRAW_H
#define G_DRAW_H

#define MAX_X   30
#define MAX_Y   20
#define SQR(x)  ((x) * (x))
#define DIST_SQR(x1,y1,x2,y2) ( SQR(((x1)-(x2))) + SQR(((y1)-(y2))) )
#define MAX_ENERGY      100000.0 // max energy (infinity)
#define LAMBDA_1        0.5
#define LAMBDA_2        0.001
#define LAMBDA_3        0.000001
typedef struct {
   GRAPH *pG;
   int aXPos[MAX_VERTEX];
   int aYPos[MAX_VERTEX];
} STATE;
#endif

/* File: graph.h */
#ifndef GRAPH_H
#define GRAPH_H

#define END_MARKER      -1  // terminator for lists
// max. no. of vertices and edges in a graph
#define MAX_VERTEX      25
#define MAX_EDGE        ((MAX_VERTEX * (MAX_VERTEX - 1)) / 2) 
#define MAX_DEGREE      (MAX_VERTEX - 1)
#define MAX_WIDTH       (MAX_VERTEX - 1)
#define RANDOM(Min,Max) ((Min) + GetRandom((Max-Min)))

typedef struct {
    int nVertexID1;  
    int nVertexID2;
} EDGE;

typedef struct
{
    int nGraphID;      // a unique ID for a graph
    BOOL eIsDirected;  
    BOOL eIsDisconnected; 
    BOOL eHasParallelEdge;
    BOOL eHasSelfLoop;
    int nVertexCount;  // no. of vertices in the graph
    int nEdgeCount;    // no. of edges in the graph
    int aVertexID[MAX_VERTEX]; // IDs of vertices in this graph
    EDGE aEdge[MAX_EDGE]; // list of edges in the graph
} GRAPH;
extern BOOL adjacent_v(GRAPH *pGraph, int V1, int V2);
#endif

/* File: sim_app.h */
#ifndef SIM_APP_H
#define SIM_APP_H
#include "graph.h"
#include "g_draw.h"
#endif