wanlinksolve.cc 20.2 KB
Newer Older
1 2 3 4 5
/**** 
 wanlinksolve - 
 A Reasonably Effective Algorithm for Genetically Assigning Nodes.
 Chad Barb, May 3, 2002

6
 Applies a standard genetic algorithm (with crossover)
7 8 9 10 11 12 13 14 15
 to solve the problem of mapping a smaller "virtual" graph
 into a larger "physical" graph, such that the actual 
 weights between acquired nodes are similar to desired weights.

 The penalty function is the sum of error square roots.

 For the application this was designed for,
 "weights" are values of latency time in milliseconds.

Chad Barb's avatar
Chad Barb committed
16
 switches: 
Chad Barb's avatar
Chad Barb committed
17 18
   -v     Extra verbosity
   -v -v  Jumbo verbosity 
Chad Barb's avatar
Chad Barb committed
19 20

   -2 <weight>
21
       Solve for 2nd (bandwidth) dimension;
Chad Barb's avatar
Chad Barb committed
22 23 24 25 26
       Penalty for error is sum of differences of natural logs,
       multiplied by <weight>.
       A good weight seems to be around 7, but the appropriate
       value is pretty much application-dependent.

27 28 29
   -m <plexpenalty>
       Handle multiple virtual->physical mapping.
       For each vnode beyond 1 assigned to a pnode, <plexpenalty> will be assessed.
30 31 32
       Asks for 'p' lines of input, with the maximum number of virtual
       nodes allowed on a given physical node, per line (See below)

33 34 35
   -s <seed>
       Use a specific random seed.

Chad Barb's avatar
Chad Barb committed
36 37 38
   -r <minrounds>
       Specify the minimum number of rounds to go before stopping.
       Note that the algorithm won't actually stop until
39
       round 2n, where "n" is the round which found the best solution so far,
Chad Barb's avatar
Chad Barb committed
40 41 42 43 44 45
       or if it hits maxrounds.
       default: DEFAULT_ROUNDS

   -R <maxrounds>
       Specify the absolute maximum number of rounds.
       default: -1 (infinite)
46 47 48 49 50 51 52

 takes input from stdin, outputs to stdout.

 input format:

 * One line containing a single number 'p'-- the number of physical nodes.
 * 'p' lines containing the name of each physical node
53 54
 ? 'p' lines containing the maximum number of virtual nodes each 
       physical node can accommodate. ('-m' switch only)
55 56 57
 * 'p' lines each containing 'p' space-delimited numbers;
       this is a P x P matrix of the _actual_ weight from pnodes to 
       pnodes. For latencies, there are zeros along the diagonal.
Chad Barb's avatar
Chad Barb committed
58 59
 ? 'p' lines, a P x P matrix of actual bandwidth ('-2' switch only)

60 61

 * One line containing a single number 'v'-- the number of virtual nodes.
62
 * 'v' lines containing the name of each virtual node.
Chad Barb's avatar
Chad Barb committed
63 64
       appending a space then the name of a physical node will permanently
       "fix" the mapping of this vnode to the named pnode.
65 66 67 68 69 70
 * 'v' lines each containing 'v' space delimited numbers;
       this is a V x V matrix of the _desired_ weight between vnodes.
       '-1's indicate "don't care"s.. (e.g. for the weight between two
       not-connected vnodes.) 
       If link weights are symmetrical, this matrix will be its own
       transpose (symmetric over the diagonal.)
Chad Barb's avatar
Chad Barb committed
71
 ? 'v' lines, a V x V matrix of desired bandwidth ('-2' switch only)
72 73 74 75

 output format:
 
 Easily inferred. Note that the perl regexp:
76
 /(\S+)\smapsTo\s(\S+)/
77 78 79 80 81 82
 will grab vnode to pnode mappings (in $1 and $2, respectively.)
 
****/

#include <stdio.h>
#include <stdlib.h>
Chad Barb's avatar
Chad Barb committed
83 84
#include <stdarg.h>
#include <unistd.h>
Chad Barb's avatar
Chad Barb committed
85
#include <assert.h>
86 87 88 89 90 91 92
#include <math.h>

// To keep things lightweight, 
// structures are statically sized to
// accommodate up to MAX_NODES nodes.
// These could be changed to STL vectors in the future.
#define MAX_NODES 20
Chad Barb's avatar
Chad Barb committed
93 94
#define MAX_DIMENSIONS 2

95
#define DEFAULT_ROUNDS 512
96 97 98

// The size of our "population."
// (100,000 seems to work well.)
99 100
//#define SOLUTIONS 100000
#define SOLUTIONS 500
101 102 103

// The number of new children to produce each round.
// (20,000 seems to work well.)
104
//define CHILDREN_PER_ROUND 20000
105 106 107 108 109 110

// The probability a given child will NOT have a mutation.
// (out of 1000). 990 means 1% of children will mutate.
// (.01% will mutate twice, .0001% three times, etc.)
// 500 means 50% of children will mutate (25% twice, 12% three times, etc.)
// 500, incidentally, seems to be optimal.
111 112 113
//#define MUTATE_PROB 500
//#define MUTATE_PROB 700
#define MUTATE_PROB 950
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

// A score below Epsilon means we've found a perfect solution,
// so stop immediately.
#define EPSILON 0.0001f

// lets STL it up a notch.
#include <map>
#include <string>

// BAM!
using namespace std;

// keep freebsd from mumbling about gets(3) being unsafe.
#define gets( x ) fgets( x, sizeof( x ), stdin  )

Chad Barb's avatar
Chad Barb committed
129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
#ifdef DEBUG
int wedgecount;
static inline void BEGIN_LOOP() { wedgecount = 0; } 
static inline void IN_LOOP_hlp( int line ) 
{ 
  ++wedgecount;
  if (wedgecount == 66666) { 
    printf( "possibly wedged in line %i.\n", line );
    assert(false);
  }
}
#define IN_LOOP() IN_LOOP_hlp(__LINE__)
#else

#define BEGIN_LOOP()
#define IN_LOOP()

#endif

148 149
// keep track of user names for nodes.
static map< int, string > pnodeNames;
150
static map< string, int > reversePNodeNames;
151 152 153 154
static map< int, string > vnodeNames;

static int pnodes, vnodes;

Chad Barb's avatar
Chad Barb committed
155 156 157
static int pLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];
static int vDesiredLatency[MAX_DIMENSIONS][MAX_NODES][MAX_NODES];

158
static float plexPenalty = 0.0f;
159 160 161 162 163
static int maxplex[MAX_NODES];
static int userSpecifiedMultiplex = 0;

static int fixed[MAX_NODES];

Chad Barb's avatar
Chad Barb committed
164 165 166 167 168 169
static int dimensions;
static float d2weight;

static int verbose = 0;

static int minrounds, maxrounds;
170 171 172 173

class Solution
{
public:
174
  int vnode_mapping[MAX_NODES];
175 176 177 178 179 180

  // Keep around a list of how many times each physical node is used
  // in this solution, rather than recomputing it each time it is needed
  // (which is often.)
  unsigned char pnode_uses[MAX_NODES];

181
  float error;
182
  float prob;
183 184 185
};

static Solution pool[SOLUTIONS];
186
static Solution pool2[SOLUTIONS];
187

188
static inline void prepick( Solution * currentPool )
189
{
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
  float totalFitness = 0.0f;
  int i;

  for (i = 0; i < SOLUTIONS; i++) {
    totalFitness += 1.0f / currentPool[i].error;
  }

  for (i = 0; i < SOLUTIONS; i++) {
    currentPool[i].prob = (1.0f / currentPool[i].error) / totalFitness;
  }
}

static inline int pickABest( Solution * currentPool )
{
  float x = (float)rand() / (float)RAND_MAX;

  int i = 0;
  while (1) { 
    x -= currentPool[i].prob; 
    if (x < 0.0f) break;
    i++;
    if (i == SOLUTIONS) { i = 0; }
  }
  return i - 1;
}

/*
217 218 219 220
  // a hacky (but damn fast) probibility curve to
  // favor mating better solutions.

  switch (rand() % 4) {
221 222 223 224
  case 0: return rand() % SOLUTIONS / 32;
  case 1: return rand() % SOLUTIONS / 16;
  case 2: return rand() % SOLUTIONS / 4;
  case 3: return rand() % SOLUTIONS;
225
  default: return 0; // can't happen, but -Wall doesn't realize this.
226 227 228 229 230 231 232
  }
}

static inline int pickAWorst()
{
  return SOLUTIONS - pickABest();
}
233
*/
234
// uses a template to avoid massive numbers
235 236 237 238 239 240 241 242 243 244 245
// of "if" choices.. compiler should generate two versions,
// one with dump and one without.
template <bool verbose>
static inline void calcError( Solution * t )
{ 
  float err = 0.0f;

  if (verbose) {
    printf("Error listing:\n");
  }

246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
  if (userSpecifiedMultiplex) {
    for (int x = 0; x < pnodes; x++) {
      if (t->pnode_uses[x] > 1) { 
	float errDelta = (float)(t->pnode_uses[x] - 1) * plexPenalty;
	if (verbose) {
	  printf("%i nodes multiplexed on physical node %s, (err [(vnodes - 1) * plexPenalty] %4.3f)\n",
		 t->pnode_uses[x],
		 pnodeNames[x].c_str(),
		 errDelta );
	}
	err += errDelta;
      }
    }
  }

261
  {
Chad Barb's avatar
Chad Barb committed
262 263 264 265 266
    for (int z = 0; z < dimensions; z++) {
      for (int x = 0; x < vnodes; x++) {
	for (int y = 0; y < vnodes; y++) {
	  int should = vDesiredLatency[z][x][y];
	  if (should != -1) {
267
	    int is     = pLatency[z][ t->vnode_mapping[x] ][ t->vnode_mapping[y] ];
Chad Barb's avatar
Chad Barb committed
268 269 270 271 272 273 274
	    if (should != is) { 
	      float errDelta;

	      if (z == 0) {
		errDelta = sqrtf((float)(abs(should - is)));
	      } else {
		errDelta = d2weight * (float)(abs(should - is));
275
		if (should < is) { errDelta *= 0.5f; }
Chad Barb's avatar
Chad Barb committed
276 277 278 279 280 281 282 283
	      }

	      if (verbose) {
		if (z == 0) {
		  printf("%s -> %s latency (ms) should be %i; is %i (err [sqrt |a-b|] %4.3f)\n", 
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 should, is, errDelta );
		} else {
284
		  printf("%s -> %s bandwidth (kB/s) should be ~%i; is ~%i (err [wt %s* ln (a/b)] %4.3f)\n", 
Chad Barb's avatar
Chad Barb committed
285 286 287
			 vnodeNames[x].c_str(), vnodeNames[y].c_str(), 
			 (int)expf((float)should / 1000.0f), 
			 (int)expf((float)is / 1000.0f),
288
			 (should < is) ? "* 0.5 " : "",
Chad Barb's avatar
Chad Barb committed
289 290 291 292
			 errDelta );
		}
	      }
	      err += errDelta;
293 294 295 296 297 298 299
	    }
	  }
	}
      }
    }
  }

Chad Barb's avatar
Chad Barb committed
300
  if (verbose) { printf("error of %4.3f\n", err ); }
301 302 303 304 305 306 307 308 309 310 311 312 313
  t->error = err;
} 

static int compar( const void * a , const void * b )
{
  Solution * sa = (Solution *)a;
  Solution * sb = (Solution *)b;

  if (sa->error > sb->error) { return  1; } else
  if (sa->error < sb->error) { return -1; } else
  { return 0; }
}

314
static inline void sortByError( Solution * t )
315 316
{
  // Ahh.. sweet, sweet qsort.
317
  qsort( t, SOLUTIONS, sizeof( Solution ), compar );
318 319 320 321 322 323 324
}

// "Mutating" is swapping what vnode a pnode maps to in
// the solution with what vnode a different pnode maps to.
// (if both are -1, e.g. not mapped to vnodes, nothing happens.)
static inline void mutate( Solution * t )
{
Chad Barb's avatar
Chad Barb committed
325
  BEGIN_LOOP();
326
  while(1) {
Chad Barb's avatar
Chad Barb committed
327
    IN_LOOP();
328 329
    // forecast calls for a 1% chance of mutation...
    if ((rand() % 1000) < MUTATE_PROB) { break; }
330 331 332 333
    
    if ((rand() % 3)) {
      // swap mutation. 
      int a, b;
Chad Barb's avatar
Chad Barb committed
334 335

      BEGIN_LOOP();
336
      do {
Chad Barb's avatar
Chad Barb committed
337
	IN_LOOP();
338
	a = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
339 340 341 342 343
      } while (fixed[a] != -1);

      BEGIN_LOOP();
      do {
	IN_LOOP();
344
	b = rand() % vnodes;
Chad Barb's avatar
Chad Barb committed
345 346 347 348 349 350 351
      } while (fixed[b] != -1);

      if (a != b) {
	int temp = t->vnode_mapping[a];
	t->vnode_mapping[a] = t->vnode_mapping[b];
	t->vnode_mapping[b] = temp;
      }
352 353 354 355 356 357 358 359 360 361 362 363 364 365
    } else {
      // reassign mutation
      /*
      int pnode_uses[MAX_NODES];

      bzero( pnode_uses, sizeof( pnode_uses ) );

      for (int i = 0; i < vnodes; i++) {
	++pnode_uses[ t->vnode_mapping[i] ];
      }
      */

      int a, b;
      // find which vnode to remap
Chad Barb's avatar
Chad Barb committed
366
      BEGIN_LOOP();
367
      do {
Chad Barb's avatar
Chad Barb committed
368
	IN_LOOP();
369 370 371 372 373 374 375
	a = rand() % vnodes;
      } while (fixed[a] != -1);

      // de-map it.
      --t->pnode_uses[ t->vnode_mapping[a] ];

      // now find a suitable physical node.
Chad Barb's avatar
Chad Barb committed
376
      BEGIN_LOOP();
377
      do {
Chad Barb's avatar
Chad Barb committed
378
	IN_LOOP();
379 380 381 382 383 384 385
	b = rand() % pnodes;
      } while (t->pnode_uses[b] >= maxplex[b]);

      // now map it.
      t->vnode_mapping[a] = b;
      ++t->pnode_uses[b];
    }
386 387 388 389 390 391 392 393
  }
}

// TODO: make sure that failed matings don't happen too
// often for difficult graphs.
// (perhaps have a limited retry)
static inline void splice( Solution * t, Solution * a, Solution * b)
{
394 395 396
  // temp storage so we don't clobber t unless the child turns out to be
  // cromulent.
  int vnode_mapping_t[MAX_NODES]; 
397
  int pnode_uses_t[MAX_NODES];
398

399
  bzero( pnode_uses_t, sizeof( pnode_uses_t ) );
400 401 402 403

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      vnode_mapping_t[i] = fixed[i];
404
      ++pnode_uses_t[ fixed[i] ];
405 406 407 408 409 410 411 412 413 414 415 416 417 418
    }
  }

  // go through each mapping, and pick randomly
  // which one of the two parents' mappings the child
  // will inherit.
  // Inherit the one that makes sense if the other would
  // conflict with a previously chosen mapping.
  // If both would conflict with a previously chosen mapping.
  // its a failed mating, and we return.

  int pos = rand() % vnodes;
  for (int i = 0; i < vnodes; i++) {
    pos = (pos + 1) % vnodes;
419
    if (fixed[pos] != -1) continue;
420
    if (rand() % 2) {
421
      if (pnode_uses_t[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) {
422
	vnode_mapping_t[pos] = a->vnode_mapping[pos];
423
	++pnode_uses_t[ a->vnode_mapping[pos] ];
424
      } else {
425
	if (pnode_uses_t[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) {
426
	  vnode_mapping_t[pos] = b->vnode_mapping[pos];
427
	  ++pnode_uses_t[ b->vnode_mapping[pos] ];
428
	} else {
429 430 431 432 433 434 435 436
	  // failed mating (clone a parent)
	  for (int x = 0; x < vnodes; x++) {
	    vnode_mapping_t[x] = a->vnode_mapping[x];
	  }
	  for (int y = 0; y < vnodes; y++) {
	    pnode_uses_t[y] = a->pnode_uses[y];
	  }
	  break;
437 438 439
	}
      }
    } else {
440
      if (pnode_uses_t[ b->vnode_mapping[pos] ] < maxplex[ b->vnode_mapping[pos] ]) {
441
	vnode_mapping_t[pos] = b->vnode_mapping[pos];
442
	++pnode_uses_t[ b->vnode_mapping[pos] ];
443
      } else {
444
	if (pnode_uses_t[ a->vnode_mapping[pos] ] < maxplex[ a->vnode_mapping[pos] ]) {
445
	  vnode_mapping_t[pos] = a->vnode_mapping[pos];
446
	  ++pnode_uses_t[ a->vnode_mapping[pos] ];
447
	} else {
448 449 450 451 452 453 454 455
	  // failed mating (clone a parent)
	  for (int x = 0; x < vnodes; x++) {
	    vnode_mapping_t[x] = b->vnode_mapping[x];
	  }
	  for (int y = 0; y < vnodes; y++) {
	    pnode_uses_t[y] = b->pnode_uses[y];
	  }
	  break;
456 457 458 459 460
	}
      }
    }
  }

461
  // since we have a cromulent child, we now clobber t.
462
  for(int d = 0; d < vnodes; d++) {
463 464 465 466 467
    t->vnode_mapping[d] = vnode_mapping_t[d];
  }

  for(int e = 0; e < pnodes; e++) {
    t->pnode_uses[e] = pnode_uses_t[e];
468 469 470 471 472 473 474 475 476 477 478 479
  }

  // Mazeltov!

  mutate( t );
  calcError<false>( t );  
} 

// Generate a random solution 
// for the initial population.
static inline void generateRandomSolution( Solution * t )
{
480 481
  //int pnode_uses[MAX_NODES];
  bzero( t->pnode_uses, sizeof( t->pnode_uses ) );
482 483 484 485

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] != -1) {
      t->vnode_mapping[i] = fixed[i];
486
      ++t->pnode_uses[ fixed[i] ];
487 488
    }
  }
489 490 491 492

  for (int i = 0; i < vnodes; i++) {
    if (fixed[i] == -1) {
      int x;
Chad Barb's avatar
Chad Barb committed
493
      BEGIN_LOOP();
494
      do {
Chad Barb's avatar
Chad Barb committed
495
	IN_LOOP();
496
	x = rand() % pnodes;
497 498
      } while( t->pnode_uses[x] >= maxplex[x] );
      ++t->pnode_uses[x];
499 500 501 502
      t->vnode_mapping[i] = x;
    }
  }

503 504 505
  calcError<false>( t );
}

Chad Barb's avatar
Chad Barb committed
506
void usage( char * appname )
507
{
Chad Barb's avatar
Chad Barb committed
508 509 510 511
  fprintf(stderr,
	  "Usage:\n"
	  "%s [-v] [-2 <weight>] [-r <minrounds>] [-R <maxrounds>]\n\n"
	  "  -v              extra verbosity\n"
Chad Barb's avatar
Chad Barb committed
512
	  "  -v -v           jumbo verbosity\n"
513 514
	  "  -m <penalty>    enable many-to-one virtual to physical mappings\n"
	  "  -s <seed>       seed the random number generator with a specific value\n"
Chad Barb's avatar
Chad Barb committed
515 516 517 518 519 520
	  "  -2 <weight>     enable solving for bandwidth;\n"
	  "                  multiply bandwidth penalties by <weight>.\n"
	  "  -r <minrounds>  set minimum rounds (a.k.a. generations)\n"
	  "                  default: %i\n"
	  "  -R <maxrounds>  set maximum rounds\n"
	  "                  default: infinite (-1)\n\n", appname, DEFAULT_ROUNDS );
Chad Barb's avatar
Chad Barb committed
521
  exit(1);
Chad Barb's avatar
Chad Barb committed
522 523 524 525
}

int main( int argc, char ** argv )
{
Chad Barb's avatar
Chad Barb committed
526 527 528
  int available = 0;
  int fixedNodeCount = 0;

Chad Barb's avatar
Chad Barb committed
529 530 531 532 533 534 535 536 537
  verbose = 0;
  dimensions = 1;
  d2weight = 1.0f / 1000.0f;

  minrounds = DEFAULT_ROUNDS;
  maxrounds = -1;

  int ch;

538
  while ((ch = getopt(argc, argv, "v2:r:R:s:m:")) != -1) {
Chad Barb's avatar
Chad Barb committed
539
    switch (ch) {
540 541 542
    case 's':
      srand( atoi( optarg ) );
      break;
Chad Barb's avatar
Chad Barb committed
543 544 545
    case 'v': 
      verbose++; 
      break;
546
    case 'm':
547
      plexPenalty = atof( optarg );
548 549
      userSpecifiedMultiplex++;
      break;
Chad Barb's avatar
Chad Barb committed
550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565
    case '2': 
      dimensions = 2;
      d2weight = atof( optarg ) / 1000.0f; 
      break;
    case 'r':
      minrounds = atoi( optarg );
      break;
    case 'R':
      maxrounds = atoi( optarg );
      break;
    default: 
      usage( argv[0] );
    }
  }


566 567 568
  char line[1024];

  {
Chad Barb's avatar
Chad Barb committed
569
    if (verbose > 1) { printf("How many physical nodes?\n"); }
570 571 572
    gets( line );
    sscanf( line, "%i", &pnodes );

Chad Barb's avatar
Chad Barb committed
573
    if (verbose > 1) { printf("Okay, enter %i names for the physical nodes, one per line.\n", pnodes ); }
574 575 576 577 578
    for (int i = 0; i < pnodes; i++) {
      char name[1024];
      gets( line );
      sscanf( line, "%s", name );
      pnodeNames[i] = string( name );
579 580 581 582
      reversePNodeNames[string(name)] = i;
    }

    if (userSpecifiedMultiplex) {
Chad Barb's avatar
Chad Barb committed
583
      if (verbose > 1) { printf("Enter %i numbers, one per line, indicating the"
584 585 586 587 588
			    " maximum number of virtual nodes allowed on each"
			    " physical node.\n", pnodes ); }
      for (int i = 0; i < pnodes; i++) {
	gets( line );
	sscanf( line, "%i", &(maxplex[i]));
Chad Barb's avatar
Chad Barb committed
589
	available += maxplex[i];
590 591 592 593
      }
    } else {
      for (int i = 0; i < pnodes; i++) {
	maxplex[i] = 1;
Chad Barb's avatar
Chad Barb committed
594
	++available;
595
      }
596 597
    }

Chad Barb's avatar
Chad Barb committed
598
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
599
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
600 601 602 603 604 605 606 607 608 609 610 611 612
	printf("Enter %ix%i grid o' actual %s.\n", pnodes, pnodes, 
	     (z == 0) ? "latency" : "bandwidth");
      }
      for (int y = 0; y < pnodes; y++) {
	char * linePos = line;
	gets( line );
	while (*linePos == ' ') { linePos++; } // skip leading whitespace
	for (int x = 0; x < pnodes; x++) {
	  sscanf( linePos, "%i", &pLatency[z][x][y] );
	  if (z == 1) { pLatency[z][x][y] = (int)( logf(pLatency[z][x][y]) * 1000.0f ); }
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
613 614 615 616 617
      }
    }
  } 

  {
Chad Barb's avatar
Chad Barb committed
618
    if (verbose > 1) { printf("How many virtual nodes?\n"); }
619 620 621
    gets( line );
    sscanf( line, "%i", &vnodes );

Chad Barb's avatar
Chad Barb committed
622 623 624 625 626 627 628 629 630 631 632
    if (vnodes > available) {
      fprintf(stderr, 
	      "More nodes required (%i) than can be mapped (%i).\n", 
	      vnodes, available );
      exit(2);
    }

    if (verbose > 1) { printf("Okay, enter %i names for the virtual nodes, one per line.\n"
			      "to fix a node, suffix a space then the name of the physical node.\n", 
			      vnodes ); }

633 634
    for (int i = 0; i < vnodes; i++) {
      char name[1024];
Chad Barb's avatar
Chad Barb committed
635
      char pname[1024];
636
      gets( line );
Chad Barb's avatar
Chad Barb committed
637 638
      if (sscanf( line, "%s %s", name, pname ) == 2) {
	map< string, int >::iterator it = reversePNodeNames.find( string( pname ) );
639
	if (it == reversePNodeNames.end()) {
Chad Barb's avatar
Chad Barb committed
640 641
	  fprintf(stderr,"pnode '%s' does not exist; can't fix.\n", pname );
	  exit(3);
642
	}
Chad Barb's avatar
Chad Barb committed
643 644
	if (verbose > 1) { 
	  printf("Fixing assignment from vnode %s to pnode %s.\n", name, pname );
645
	}
Chad Barb's avatar
Chad Barb committed
646 647
	fixed[i] = reversePNodeNames[ string( pname ) ];
	fixedNodeCount++;
648 649 650
      } else {
	fixed[i] = -1;
      }
Chad Barb's avatar
Chad Barb committed
651
      vnodeNames[i] = string( name );
652 653
    }

Chad Barb's avatar
Chad Barb committed
654
    for (int z = 0; z < dimensions; z++) {
Chad Barb's avatar
Chad Barb committed
655
      if (verbose > 1) {
Chad Barb's avatar
Chad Barb committed
656 657
	printf("Enter %ix%i grid o' desired %s (-1 is don't care.)\n", vnodes, vnodes, 
	       (z == 0) ? "latency" : "bandwidth");
658
      }
Chad Barb's avatar
Chad Barb committed
659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675
      for (int y = 0; y < vnodes; y++) {
	char * linePos = line;
	gets( line );
	while (*linePos == ' ') { linePos++; } // skip leading whitespace
	for (int x = 0; x < vnodes; x++) {
	  sscanf( linePos, "%i", &vDesiredLatency[z][x][y] );
	  if (z == 1) { 
	    if (vDesiredLatency[z][x][y] != -1) {
	      vDesiredLatency[z][x][y] = (int)(logf(vDesiredLatency[z][x][y]) * 1000.0f); 
	    }
	  }
	  while (*linePos != ' ' && *linePos != '\n') { linePos++; }
	  while (*linePos == ' ') { linePos++; }
	}
      }
    } 
  }
676

677 678 679
  Solution * currentPool = pool;
  Solution * nextPool = pool2;

Chad Barb's avatar
Chad Barb committed
680 681
  if (fixedNodeCount < vnodes) {
    if (verbose) { printf("Now running...\n"); }
682

Chad Barb's avatar
Chad Barb committed
683 684
    {
      for (int i = 0; i < SOLUTIONS; i++) {
685
	generateRandomSolution( &(currentPool[i]) );
Chad Barb's avatar
Chad Barb committed
686
      }
687
      sortByError( currentPool );
688 689 690
    }

    int highestFoundRound = 0;
691 692 693 694 695 696 697 698 699 700 701 702 703
    float last = currentPool[0].error;

    for (int i = 0; i != maxrounds && (i < minrounds || i < highestFoundRound * 2); i++) {
      /*
      {
	float blah = 0.0f;
	for (int xy = 0; xy < SOLUTIONS; xy++) { blah += currentPool[xy].error; }
	printf("Avg = %7.2f\n", (blah / (float)SOLUTIONS) );
      }
      */
      
      if (verbose && !(i % (minrounds / 8))) {
	printf("Round %i. (best %4.3f)\n", i, currentPool[0].error);
704
      }
Chad Barb's avatar
Chad Barb committed
705
      
706
      if (currentPool[0].error < last) {
Chad Barb's avatar
Chad Barb committed
707 708
	if (verbose) {
	  printf("Better solution found in round %i (error %4.3f)\n", 
709
		 i, currentPool[0].error);
Chad Barb's avatar
Chad Barb committed
710
	}
711
	last = currentPool[0].error;
712 713
	highestFoundRound = i;
      }
714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729

      memcpy( &(nextPool[0]), &(currentPool[0]), sizeof( Solution ) );
      prepick( currentPool );

      int j;

      for (j = 1; j < SOLUTIONS - 10; j++) {
	splice( &(nextPool[j]),
		&(currentPool[pickABest( currentPool )]),
		&(currentPool[pickABest( currentPool )]) );
      }

      for (;j != SOLUTIONS; j++) {
	generateRandomSolution( &(nextPool[j]) );	
      }
      /*      
730 731 732 733 734 735
      for (int j = 0; j < CHILDREN_PER_ROUND; j++) {
	// Overwrite a "bad" solution with the child of two "good" ones.
	splice( &(pool[pickAWorst()]), 
		&(pool[pickABest()]), 
		&(pool[pickABest()]) ); 
      }
736 737 738 739 740 741 742 743
      */
      sortByError( nextPool );

      Solution * temp = currentPool;
      currentPool = nextPool;
      nextPool = temp;

      if (currentPool[0].error < EPSILON) { 
Chad Barb's avatar
Chad Barb committed
744
	if (verbose > 1) { printf("Found perfect solution.\n"); }
745 746 747
	break;
      }
    }
Chad Barb's avatar
Chad Barb committed
748 749
  } else {
    if (verbose) { printf("No non-fixed vnodes (or no vnodes at all,) so nothing to be done!\n"); }
750 751 752
  }

  {
Chad Barb's avatar
Chad Barb committed
753
    if (verbose) { printf("\nYour solution is as follows:\n"); }
754
    for (int x = 0; x < vnodes; x++) {
755 756
      if (pnodeNames.find( currentPool[0].vnode_mapping[x] ) == pnodeNames.end()) {
	pnodeNames[ currentPool[0].vnode_mapping[x] ] = "CRAP";
Chad Barb's avatar
Chad Barb committed
757 758 759
      }
      printf("%s mapsTo %s\n", 
	     vnodeNames[x].c_str(),
760
	     pnodeNames[currentPool[0].vnode_mapping[x]].c_str() );
761
    }
762

763 764 765
    printf("\n");

    // dump a detailed report of the returned solution's errors.
766
    if (verbose > 1) { calcError<true>( &(currentPool[0]) ); }
767 768
  }

Chad Barb's avatar
Chad Barb committed
769
  if (verbose > 1) { printf("Bye now.\n"); }
770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785
  return 0;
}