assign.cc 19.8 KB
Newer Older
Robert Ricci's avatar
Robert Ricci committed
1 2 3 4 5 6
/*
 * EMULAB-COPYRIGHT
 * Copyright (c) 2000-2003 University of Utah and the Flux Group.
 * All rights reserved.
 */

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
#include "port.h"

#include <hash_map>
#include <rope>
#include <queue>

#include <boost/config.hpp>
#include <boost/utility.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>

#include <fstream.h>
22
#include <iostream.h>
23
#include <time.h>
24
#include <stdlib.h>
25
#include <math.h>
26 27
#include <sys/types.h>
#include <sys/time.h>
28
#include <sys/resource.h>
29 30
#include <signal.h>
#include <sys/signal.h>
31 32

using namespace boost;
33 34

#include "common.h"
35
#include "delay.h"
36
#include "physical.h"
37
#include "virtual.h"
38
#include "vclass.h"
39
#include "pclass.h"
40
#include "score.h"
41 42 43
#include "solution.h"
#include "maps.h"
#include "anneal.h"
44 45 46

// Here we set up all our graphs.  Need to create the graphs
// themselves and then setup the property maps.
47
tb_pgraph PG;
48 49 50 51 52 53 54 55 56 57
tb_pgraph_vertex_pmap pvertex_pmap = get(vertex_data, PG);
tb_pgraph_edge_pmap pedge_pmap = get(edge_data, PG);
tb_sgraph SG;
tb_sgraph_vertex_pmap svertex_pmap = get(vertex_data, SG);
tb_sgraph_edge_pmap sedge_pmap = get(edge_data, SG);
tb_vgraph VG;
tb_vgraph_vertex_pmap vvertex_pmap = get(vertex_data, VG);
tb_vgraph_edge_pmap vedge_pmap = get(edge_data, VG);

// A simple list of physical types.
58
name_count_map ptypes;
59 60

// List of virtual types by name.
61
name_count_map vtypes;
62
name_list_map vclasses;
63 64

// A list of all pclasses.
65
pclass_list pclasses;
66 67 68
 	
// Map from a pnode* to the the corresponding pvertex.
pnode_pvertex_map pnode2vertex;
69 70 71

// Map of a type to a tt_entry, a vector of pclasses and the size of
// the vector.
72
pclass_types type_table;
73 74 75
#ifdef PER_VNODE_TT
pclass_types vnode_type_table;
#endif
76

77 78 79 80 81
// This datastructure contains all the information needed to calculate
// the shortest path between any two switches.  Indexed by svertex,
// the value will be a predicate map (indexed by svertex as well) of
// the shortest paths for the given vertex.
switch_pred_map_map switch_preds;
82

83 84
// Same, but for distances 
switch_dist_map_map switch_dist;
85

86 87
// Time started, finished, and the time limit
double timestart, timeend, timelimit, timetarget;
88

89 90 91
// An amount to scale the neighborhood size by
double scale_neighborhood = 1.0;

92 93 94 95 96
#ifdef GNUPLOT_OUTPUT
FILE *scoresout, *tempout, *deltaout;
#endif
// Whether or not assign is allowed to generate trivial links
bool allow_trivial_links = true;
97

98
// Whether or not assign should use pclasses
99
bool disable_pclasses = false;
100

101 102 103
// Whether or not assign should prune out pclasses that it knows can
// never be used
bool prune_pclasses = false;
104 105 106

// Whether or not we should use the experimental support for dynamic pclasses
bool dynamic_pclasses = false;
107 108 109

// Whether or not to allow assign to temporarily over-subscribe pnodes
bool allow_overload = false;
110 111 112 113
  
// XXX - shouldn't be in this file
double absbest;
int absbestviolated, iters, iters_to_best;
114

115 116 117
/*
 * Internal functions
 */
118

119
// Return the CPU time (in seconds) used by this process
120 121 122 123 124 125 126 127
float used_time()
{
  struct rusage ru;
  getrusage(RUSAGE_SELF,&ru);
  return ru.ru_utime.tv_sec+ru.ru_utime.tv_usec/1000000.0+
    ru.ru_stime.tv_sec+ru.ru_stime.tv_usec/1000000.0;
}

128
// Read in the .ptop file
129 130 131 132
void read_physical_topology(char *filename)
{
  ifstream ptopfile;
  ptopfile.open(filename);
133 134 135 136
  if (!ptopfile.is_open()) {
      cerr << "Unable to open ptop file " << filename << endl;
      exit(2);
  }
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
  cout << "Physical Graph: " << parse_ptop(PG,SG,ptopfile) << endl;

#ifdef DUMP_GRAPH
  {
    cout << "Physical Graph:" << endl;
    
    pvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(PG);
    
    for (;vit != vendit;vit++) {
      tb_pnode *p = get(pvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    pedge_iterator eit,eendit;
    tie(eit,eendit) = edges(PG);

    for (;eit != eendit;eit++) {
      tb_plink *p = get(pedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,PG) << " <-> " <<
	target(*eit,PG) << ")\t" << *p;
    }
  }
160
#endif // DUMP_GRAPH
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183

#ifdef GRAPH_DEBUG
  {
    cout << "Switch Graph:" << endl;
    

    svertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(SG);
    
    for (;vit != vendit;vit++) {
      tb_switch *p = get(svertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    sedge_iterator eit,eendit;
    tie(eit,eendit) = edges(SG);

    for (;eit != eendit;eit++) {
      tb_slink *p = get(sedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,SG) << " <-> " <<
	target(*eit,SG) << ")\t" << *p;
    }
  }
184
#endif // GRAPH_DEBUG
185

186 187
  // Set up pnode2vertex - a mapping between vertices in the physical graph and
  // the pnodes that we just read in from the ptop file
188 189 190 191 192 193 194 195
  pvertex_iterator pvit,pvendit;
  tie(pvit,pvendit) = vertices(PG);
  for (;pvit != pvendit;pvit++) {
    pnode2vertex[get(pvertex_pmap,*pvit)]=*pvit;
  }

}

196 197
// Calculate the minimum spanning tree for the switches - we only consider one
// potential path between each pair of switches.
198
void calculate_switch_MST()
199
{
200
  cout << "Calculating shortest paths on switch fabric." << endl;
201 202

  // Set up the weight map for Dijkstra's
203 204 205 206 207 208 209 210 211 212
  tb_sgraph_weight_pmap sweight_pmap = get(edge_weight, SG);
  sedge_iterator seit,seendit;
  tie(seit,seendit) = edges(SG);
  for (;seit != seendit;seit++) {
    tb_slink *slink = get(sedge_pmap,*seit);
    // XXX should we make this more complicated depending on
    // latency/loss as well?
    put(sweight_pmap,*seit,
	100000000-get(pedge_pmap,slink->mate)->delay_info.bandwidth);
  }
213

214
  // Let boost do the Disjktra's for us, from each switch
215 216 217 218 219 220 221 222
  svertex_iterator svit,svendit;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    switch_preds[*svit] = new switch_pred_map(num_vertices(SG));
    switch_dist[*svit] = new switch_dist_map(num_vertices(SG));
    dijkstra_shortest_paths(SG,*svit,
    			    predecessor_map(&((*switch_preds[*svit])[0])).
			    distance_map(&((*switch_dist[*svit])[0])));
223 224
  }

225 226 227 228 229 230 231 232 233
#ifdef GRAPH_DEBUG
  cout << "Shortest paths" << endl;
  tie(svit,svendit) = vertices(SG);
  for (;svit != svendit;svit++) {
    cout << *svit << ":" << endl;
    for (unsigned int i = 0;i<num_vertices(SG);++i) {
      cout << i << " " << (*switch_dist[*svit])[i] << endl;
    }
  }
234
#endif // GRAPH_DEBUG
235 236
}

237
// Read in the .top file
238 239 240 241
void read_virtual_topology(char *filename)
{
  ifstream topfile;
  topfile.open(filename);
242 243 244 245
  if (!topfile.is_open()) {
      cerr << "Unable to open top file " << filename << endl;
      exit(2);
  }
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271
  cout << "Virtual Graph: " << parse_top(VG,topfile) << endl;

#ifdef DUMP_GRAPH
  {
    cout << "Virtual Graph:" << endl;
    

    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
    
    for (;vit != vendit;vit++) {
      tb_vnode *p = get(vvertex_pmap,*vit);
      cout << *vit << "\t" << *p;
    }
    
    vedge_iterator eit,eendit;
    tie(eit,eendit) = edges(VG);

    for (;eit != eendit;eit++) {
      tb_vlink *p = get(vedge_pmap,*eit);
      cout << *eit << " (" << source(*eit,VG) << " <-> " <<
	target(*eit,VG) << ")\t" << *p;
    }
  }  
#endif
}
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297
/*
 * Make a pass through the pclasses, looking for ones that no node can use, and
 * nuking them.
 */
void prune_unusable_pclasses() {
    cout << "Pruning pclasses." << endl;
    int pruned = 0;
    pclass_list::iterator pclass_iterator = pclasses.begin();
    while (pclass_iterator != pclasses.end()) {
	if ((*pclass_iterator)->refcount == 0) {
	    pclass_list::iterator nukeme = pclass_iterator;
	    pclass_iterator++;
#ifdef PCLASS_DEBUG
	    cout << "Pruning " << (*nukeme)->name << endl;
#endif
	    pruned++;
	    delete *nukeme;
	    pclasses.erase(nukeme);
	} else {
	    pclass_iterator++;
	}
    }
    cout << "pclass pruning complete: removed " << pruned << " pclasses, " <<
	pclasses.size() << " remain." << endl;
}

298
void print_help()
299
{
300 301 302 303
  cerr << "assign [options] ptopfile topfile [config params]" << endl;
  cerr << "Options: " << endl;
#ifdef TIME_TERMINATE
  cerr << "  -l <time>   - Limit runtime." << endl;
304
#endif
305 306 307 308 309
  cerr << "  -s <seed>   - Set the seed." << endl;
  cerr << "  -v <viz>    - Produce graphviz files with given prefix." <<
    endl;
  cerr << "  -r          - Don't allow trivial links." << endl;
  cerr << "  -p          - Disable pclasses." << endl;
310
  cerr << "  -d          - Enable dynamic pclasses." << endl;
311 312
#ifdef PER_VNODE_TT
  cerr << "  -P          - Prune unusable pclasses." << endl;
313
#endif
314
  cerr << "  -T          - Doing some scoring self-testing." << endl;
315
  cerr << "  -H <float>  - Try <float> times harder." << endl;
316
  cerr << "  -o          - Allow overloaded pnodes to be considered." << endl;
317 318 319 320 321 322 323 324
  exit(2);
}
 
// Perfrom a pre-cehck to make sure that there are enough free nodes of the
// proper types. Returns 1 if the proper types exist, 0 if they do not.
// TODO - move away from using global variables
int type_precheck() {
    cout << "Type precheck:" << endl;
325

326
    bool ok = true;
327

328
    // First, check the regular types
329 330 331 332 333 334
    for (name_count_map::iterator vtype_it=vtypes.begin();
	    vtype_it != vtypes.end();++vtype_it) {
    
	// Check to see if there were any pnodes of the type at all
	name_count_map::iterator ptype_it = ptypes.find(vtype_it->first);
	if (ptype_it == ptypes.end()) {
335
	    cout << "  *** No physical nodes of type " << vtype_it->first
336 337
		<< " found" << endl;
	    ok = false;
338
	} else {
339 340
	    // Okay, there are some - are there enough?
	    if (ptype_it->second < vtype_it->second) {
341
		cout << "  *** " << vtype_it->second << " nodes of type " <<
342 343 344 345
		    vtype_it->first << " requested, but only "
		    << ptype_it->second << " found" << endl;
		ok = false;
	    }
346
	}
347
    }
348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367

    // Check the vclasses, too
    for (name_list_map::iterator vclass_it = vclasses.begin();
	    vclass_it != vclasses.end(); ++vclass_it) {
	bool found_match = false;
	for (vector<crope>::iterator vtype_it = vclass_it->second.begin();
		vtype_it != vclass_it->second.end(); vtype_it++) {
	    if (ptypes.find(*vtype_it) != ptypes.end()) {
		found_match = true;
		break;
	    }
	}

	if (!found_match) {
	    cout << "  *** No physical nodes can satisfy vclass " <<
		vclass_it->first << endl;
	    ok = false;
	}
    }

368 369 370 371 372 373 374 375
    if (ok) {
      cout << "Type preecheck passed." << endl;
      return 1;
    } else {
      cout << "Type precheck failed!" << endl;
      return 0;
    }
}
376

377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
// Perfrom a pre-cehck to make sure that every vnode has at least one possible
// mapping.  Returns 1 if this is the case, 0 if not.
// TODO - move away from using global variables
int mapping_precheck() {
#ifdef PER_VNODE_TT
    cout << "Node mapping precheck:" << endl;
    /*
     * Build up an entry in the type table for each vnode, by first looking at
     * the type table entry for the vnode's type, then checking each entry to
     * make sure that it:
     * (1) Has enough interfaces
     * (2) Has enough total bandwidth (for emulated links)
     * (3) Meets any 1.0-weight features and/or desires
     */
    vvertex_iterator vit,vendit;
    tie(vit,vendit) = vertices(VG);
393

394 395 396 397
    /*
     * Indicates whether all nodes have potential matches or not
     */
    bool ok = true;
398

399 400
    for (;vit != vendit;vit++) {
	tb_vnode *v = get(vvertex_pmap,*vit);
401

402 403 404 405 406 407 408 409 410 411 412 413 414 415 416
	pclass_vector *vec = new pclass_vector();
	vnode_type_table[v->name] = tt_entry(0,vec);

	// This constitutes a list of the number of ptypes that matched the
	// criteria. We use to guess what's wrong with the vnode.
	int matched_links = 0;
	int matched_bw = 0;
	// Keep track of desires had how many 'hits', so that we can tell
	// if any simply were not matched
	tb_vnode::desires_count_map matched_desires;

	tb_vclass *vclass = v->vclass;
	tb_vclass::members_map::iterator mit;
	if (vclass) {
	    mit = vclass->members.begin();
417
	}
418 419 420 421 422 423 424 425 426
	for (;;) {
	    // Loop over all types this node can take on, which might be only
	    // one, if it's not part of a vclass
	    crope this_type;
	    if (vclass) {
		this_type = mit->first;
	    } else {
		this_type = v->type;
	    }
427

428 429
	    for (pclass_vector::iterator it = type_table[this_type].second->begin();
		    it != type_table[this_type].second->end(); it++) {
430

431 432 433
		bool potential_match = true;
		// Grab the first node of the pclass as a representative sample
		tb_pnode *pnode = *((*it)->members[this_type]->L.begin());
434

435 436 437 438 439 440
		// Check the number of interfaces - if the pnode is a switch,
		// for now, we don't check this, since it can end up with more
		// 'interfaces' due to the fact that it can have interswitch
		// links
		if ((pnode->total_interfaces >= v->num_links) ||
			pnode->current_type.compare("switch")) {
441 442 443 444
		    matched_links++;
		} else {
		    potential_match = false;
		}
445

446 447 448 449 450 451
		// Check bandwidth on emulated links
		if (pnode->total_bandwidth >= v->total_bandwidth) {
		    matched_bw++;
		} else {
		    potential_match = false;
		}
452

453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477
		//
		// Check features and desires
		//

		// Desires first
		for (tb_vnode::desires_map::iterator desire_it = v->desires.begin();
			desire_it != v->desires.end();
			desire_it++) {
		    crope name = (*desire_it).first;
		    float value = (*desire_it).second;
		    // Only check for desires that would result in a violation if
		    // unsatisfied
		    if (value >= FD_VIOLATION_WEIGHT) {
			if (matched_desires.find(name) == matched_desires.end()) {
			    matched_desires[name] = 0;
			}
			tb_pnode::features_map::iterator feature_it =
			    pnode->features.find(name);
			if (feature_it != pnode->features.end()) {
			    matched_desires[name]++;
			} else {
			    potential_match = false;
			}
		    }
		}
478

479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
		// Next, features
		for (tb_pnode::features_map::iterator feature_it = pnode->features.begin();
			feature_it != pnode->features.end(); feature_it++) {
		    crope name = (*feature_it).first;
		    float value = (*feature_it).second;
		    // Only check for feature that would result in a violation if
		    // undesired
		    if (value >= FD_VIOLATION_WEIGHT) {
			tb_vnode::desires_map::iterator desire_it =
			    v->desires.find(name);
			if (desire_it == v->desires.end()) {
			    potential_match = false;
			}
		    }
		}
494

495

496 497 498 499 500 501
		if (potential_match) {
		    vec->push_back(*it);
		    vnode_type_table[v->name].first++;
		    (*it)->refcount++;
#ifdef PCLASS_DEBUG
		    cerr << v->name << " can map to " << (*it)->name << endl;
502
#endif
503 504
		}
	    }
505

506 507 508 509 510 511 512 513 514
	    if (vclass) { 
		mit++;
		if (mit == vclass->members.end()) {
		    break;
		}
	    } else {
		// If not a vtype, we only had to do this once
		break;
	    }
515
	}
516

517
	if (vnode_type_table[v->name].first == 0) {
518
	    cout << "  *** No possible mapping for " << v->name << endl;
519 520
	    // Make an attempt to figure out why it didn't match
	    if (!matched_links) {
521
		cout << "      Too many links!" << endl;
522
	    }
523

524
	    if (!matched_bw) {
525
		cout << "      Too much bandwidth on emulated links!" << endl;
526
	    }
527

528 529 530 531
	    for (tb_vnode::desires_count_map::iterator dit = matched_desires.begin();
		    dit != matched_desires.end();
		    dit++) {
		if (dit->second == 0) {
532
		    cout << "      No physical nodes have feature " << dit->first
533 534
			<< "!" << endl;
		}
535
	    }
536
	    ok = false;
537
	}
538 539 540
#ifdef PCLASS_DEBUG
	cerr << v->name << " can map to " << vnode_type_table[v->name].first << " pclasses"
	    << endl;
541
#endif
542

543
    }
544

545 546 547
    if (ok) {
	cout << "Node mapping precheck succeeded" << endl;
	return 1;
548
    } else {
549 550
	cout << "Node mapping precheck failed!" << endl;
	return 0;
551 552
    }

553 554 555
#else // PER_VNODE_TT
    // PER_VNODE_TT is required for this check, just pretend it's OK.
    return 1;
556
#endif
557
}
558

559 560 561 562
// Signal handler - add a convneint way to kill assign and make it return an
// unretryable error
void exit_unretryable(int signal) {
    cerr << "Killed with signal " << signal << " - exiting!" << endl;
563
    _exit(2);
564 565
}

566 567 568 569
int main(int argc,char **argv)
{
  int seed = 0;
  crope viz_prefix;
570
  bool scoring_selftest = false;
571 572 573 574 575
  
  // Handle command line
  char ch;
  timelimit = 0.0;
  timetarget = 0.0;
576
  while ((ch = getopt(argc,argv,"s:v:l:t:rpPTdH:o")) != -1) {
577 578 579 580
    switch (ch) {
    case 's':
      if (sscanf(optarg,"%d",&seed) != 1) {
	print_help();
581
      }
582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
      break;
    case 'v':
      viz_prefix = optarg;
      break;
#ifdef TIME_TERMINATE
    case 'l':
      if (sscanf(optarg,"%lf",&timelimit) != 1) {
	print_help();
      }
      break;
#endif
#ifdef TIME_TARGET
    case 't':
      if (sscanf(optarg,"%lf",&timetarget) != 1) {
	print_help();
      }
      break;
599
#endif
600 601 602
    case 'r':
      allow_trivial_links = false; break;
    case 'p':
603
      disable_pclasses = true; break;
604 605 606 607
#ifdef PER_VNODE_TT
    case 'P':
      prune_pclasses = true; break;
#endif
608 609
    case 'T':
      scoring_selftest = true; break;
610 611
    case 'd':
      dynamic_pclasses = true; break;
612 613 614 615 616
    case 'H':
      if (sscanf(optarg,"%lf",&scale_neighborhood) != 1) {
	print_help();
      }
      break;
617 618
    case 'o':
      allow_overload = true; break;
619 620
    default:
      print_help();
621
    }
622
  }
623 624 625 626 627 628 629 630 631
  argc -= optind;
  argv += optind;
  
  if (seed == 0) {
    if (getenv("ASSIGN_SEED") != NULL) {
      sscanf(getenv("ASSIGN_SEED"),"%d",&seed);
    } else {
      seed = time(NULL)+getpid();
    }
632
  }
633 634 635 636

  if (viz_prefix.size() == 0) {
    if (getenv("ASSIGN_GRAPHVIZ") != NULL) {
      viz_prefix = getenv("ASSIGN_GRAPHVIZ");
637
    }
638
  }
639

640 641 642 643
  if (argc == 0) {
    print_help();
  }

644 645 646 647 648 649 650 651

  // Set up a signal handler for USR1 that exits with an unretryable error
  struct sigaction action;
  action.sa_handler = exit_unretryable;
  sigemptyset(&action.sa_mask);
  action.sa_flags = 0;
  sigaction(SIGUSR1,&action,NULL);

652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670
  // Convert options to the common.h parameters.
  parse_options(argv, options, noptions);
#ifdef SCORE_DEBUG
  dump_options("Configuration options:", options, noptions);
#endif

#ifdef GNUPLOT_OUTPUT
  scoresout = fopen("scores.out","w");
  tempout = fopen("temp.out","w");
  deltaout = fopen("delta.out","w");
#endif

  cout << "seed = " << seed << endl;
  std::srandom(seed);

  read_physical_topology(argv[0]);
  calculate_switch_MST();
  
  cout << "Generating physical equivalence classes:";
671
  generate_pclasses(PG,disable_pclasses,dynamic_pclasses);
672
  cout << pclasses.size() << endl;
673

674 675 676
#ifdef PCLASS_DEBUG
  pclass_debug();
#endif
677 678

  read_virtual_topology(argv[1]);
679

680 681
  // Run the type precheck
  if (!type_precheck()) {
682
      exit(2);
683
  }
684

685 686
  // Run the mapping precheck
  if (!mapping_precheck()) {
687
      exit(2);
688
  }
689

690
#ifdef PER_VNODE_TT
691 692 693
  if (prune_pclasses) {
      prune_unusable_pclasses();
  }
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713
#endif

  // Output graphviz if necessary
  if (viz_prefix.size() != 0) {
    crope vviz = viz_prefix + "_virtual.viz";
    crope pviz = viz_prefix + "_physical.viz";
    crope sviz = viz_prefix + "_switch.viz";
    ofstream vfile,pfile,sfile;
    vfile.open(vviz.c_str());
    write_graphviz(vfile,VG,vvertex_writer(),vedge_writer(),graph_writer());
    vfile.close();
    pfile.open(pviz.c_str());
    write_graphviz(pfile,PG,pvertex_writer(),pedge_writer(),graph_writer());
    pfile.close();
    sfile.open(sviz.c_str());
    write_graphviz(sfile,SG,svertex_writer(),sedge_writer(),graph_writer());
    sfile.close();
  }
 
  timestart = used_time();
714
  anneal(scoring_selftest, scale_neighborhood);
715
  timeend = used_time();
716

717 718 719 720 721 722
#ifdef GNUPLOT_OUTPUT
  fclose(scoresout);
  fclose(tempout);
  fclose(deltaout);
#endif

723
  if ((get_score() > absbest) || (violated > absbestviolated)) {
724
    cerr << "Internal error: Invalid migration assumptions." << endl;
725
    cerr << "score:" << get_score() << " absbest:" << absbest <<
726 727 728 729
      " violated:" << violated << " absbestviolated:" <<
      absbestviolated << endl;
    cerr << "  Contact calfeld" << endl;
  }
730
  
731
  cout << "   BEST SCORE:  " << get_score() << " in " << iters <<
732 733 734 735
    " iters and " << timeend-timestart << " seconds" << endl;
  cout << "With " << violated << " violations" << endl;
  cout << "Iters to find best score:  " << iters_to_best << endl;
  cout << "Violations: " << violated << endl;
736
  cout << vinfo;
737

738
  print_solution();
739 740 741 742 743 744 745 746 747 748 749

  if (viz_prefix.size() != 0) {
    crope aviz = viz_prefix + "_solution.viz";
    ofstream afile;
    afile.open(aviz.c_str());
    write_graphviz(afile,VG,solution_vertex_writer(),
		   solution_edge_writer(),graph_writer());
    afile.close();
  }
  
  if (violated > 0) {
750
      return 1;
751 752 753
  } else {
      return 0;
  }
754
}
755