/*
	Author:	Pate Williams (c) 2000

	Morris' next descent breakout algorithm
	Our steepest descent breakout algorithms
	Preprocessing phase
	Minton's et al. min-conflicts hill-climbing algorithm
	Wallace and Freuder's min-conflicts hill-climbing algorithm
	Static constraint satisfaction problems
	Order n cost function
*/

#include <assert.h>
#include <iomanip.h>
#include <iostream.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>

//#define DEBUG 1

const int MaxColors = 8;	// maximum number of colors
const int MaxN = 180;	// maximum number of vertices
const int MaxBreakouts = 10 * MaxN;	// maximum number of breakouts
const int Number = 7;	// number of algorithms

extern "C" void sgenrand(unsigned long seed);
extern "C" unsigned long genrand(void);

int candidateSolutions, MaxCandSol;

class RoutingTable {
private:
	short hops[MaxN], line[MaxN];
public:
	void init(int n, int iHops) {
		for (int i = 0; i < n; i++) {
			hops[i] = iHops;
			line[i] = - 1;
		}
	}
	RoutingTable(void) {}
	RoutingTable(int n, int iHops) {
		init(n, iHops);
	}
	int getHops(int i) {
		return hops[i];
	}
	int getLine(int i) {
		return line[i];
	}
	void setHops(int i, int h) {
		hops[i] = h;
	}
	void setLine(int i, int l) {
		line[i] = l;
	}
};

void update(int destin, int n, RoutingTable &newRoutingTable, RoutingTable &oldRoutingTable) {
	int i, hops;

	for (i = 0; i < n; i++) {
		if (newRoutingTable.getLine(i) == - 1) {
			if (oldRoutingTable.getLine(i) != - 1) {
				hops = oldRoutingTable.getHops(i) + 1;
				if (hops < newRoutingTable.getHops(i)) {
					newRoutingTable.setHops(i, hops);
					newRoutingTable.setLine(i, destin);
				}
			}
		}
		else {
			if (oldRoutingTable.getLine(i) != - 1) {
				hops = oldRoutingTable.getHops(i) + 1;
				if (hops < newRoutingTable.getHops(i)) {
					newRoutingTable.setHops(i, hops);
					newRoutingTable.setLine(i, destin);
				}
			}	
		}
	}
}

bool distanceVectorRouter(int n, bool matrix[MaxN][MaxN],
						  RoutingTable newRoutingTable[MaxN],
						  RoutingTable oldRoutingTable[MaxN]) {
	bool done;
	int i, j, k;
	
	for (k = 0; k < n; k++) {
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++)
				if (matrix[i][j])
					update(j, n, newRoutingTable[i], oldRoutingTable[j]);
			oldRoutingTable[i] = newRoutingTable[i];
		}
		done = true;
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				if (newRoutingTable[i].getLine(j) == - 1)
					done = false;
		if (done)
			break;
	}
	return done;
}

class Adjacency {
private:
	bool matrix[MaxN][MaxN];
	int n;
	RoutingTable newRoutingTable[MaxN], oldRoutingTable[MaxN];
public:
	Adjacency(int K, int m, int nn) {
		bool selected;
		int i, j, k, icount;
		int color[MaxN];

		n = nn;
		for (;;) {
			for (i = 0; i < K; i++)
				for (j = i * n / K; j < (i + 1) * n / K; j++)
					color[j] = i;
			for (i = 0; i < n; i++)
				for (j = 0; j < n; j++)
					matrix[i][j] = false;
			for (k = 0; k < m; k++) {
				do {
					do {
						i = genrand() % n;
						j = genrand() % n;
					} while (i == j);
					if (!matrix[i][j] && (color[i] != color[j])) {
						matrix[i][j] = true;
						matrix[j][i] = true;
						selected = true;
					}
					else
						selected = false;
				} while (!selected);
			}
			for (i = 0; i < n; i++) {
				for (icount = j = 0; j < n; j++)
					if (matrix[i][j])
						icount++;
				if (icount == 0)
					break;
			}
			if (icount == 0)
				continue;
			for (i = 0; i < n; i++) {
				newRoutingTable[i].init(n, SHRT_MAX);
				oldRoutingTable[i].init(n, - 1);
				oldRoutingTable[i].setHops(i, 0);
				oldRoutingTable[i].setLine(i, i);
				newRoutingTable[i].setHops(i, 0);
				newRoutingTable[i].setLine(i, i);
				for (j = 0; j < n; j++) {
					if (matrix[i][j]) {
						oldRoutingTable[i].setHops(j, 1);
						oldRoutingTable[i].setLine(j, j);
						newRoutingTable[i].setHops(j, 1);
						newRoutingTable[i].setLine(j, j);
					}
				}
			}
			if (distanceVectorRouter(n, matrix, newRoutingTable, oldRoutingTable))
				break;
		}
	}
	bool getElementAt(int i, int j) {
		return matrix[i][j];
	}
	int getHops(int i, int j) {
		return newRoutingTable[i].getHops(j);
	}
	int getLine(int i, int j) {
		return newRoutingTable[i].getLine(j);
	}
	int getN(void) {
		return n; 
	}
	friend istream &operator >> (istream &input, Adjacency &adjacency) {
		char c;

		input >> adjacency.n;
		for (int i = 0; i < adjacency.n; i++) {
			for (int j = 0; j < adjacency.n; j++) {
				input >> c;
				if (c == '0')
					adjacency.matrix[i][j] = false;
				else
					adjacency.matrix[i][j] = true;
			}
		}
		return input;
	}
	friend ostream &operator << (ostream &output, const Adjacency &adjacency) {
		output << "adjacency matrix: " << endl << endl;
		for (int i = 0; i < adjacency.n; i++) {
			for (int j = 0; j < adjacency.n; j++) {
				if (adjacency.matrix[i][j])
					output << "1 ";
				else
					output << "0 ";
			}
			output << endl;
		}
		return output;
	}
};

class Breakout {
private:
	int ltTuple, ltValue, rtTuple, rtValue, weight;
public:
	Breakout(void) { ltTuple = rtTuple = weight = - 1; };
	Breakout(int ltTup, int ltVal, int rtTup, int rtVal) {
		ltTuple = ltTup;
		ltValue = ltVal;
		rtTuple = rtTup;
		rtValue = rtVal;
	};
	Breakout(int ltTup, int ltVal, int rtTup, int rtVal, int w) {
		ltTuple = ltTup;
		ltValue = ltVal;
		rtTuple = rtTup;
		rtValue = rtVal;
		weight = w;
	};
	Breakout(Breakout &breakout) {
		ltTuple = breakout.ltTuple;
		ltValue = breakout.ltValue;
		rtTuple = breakout.rtTuple;
		rtValue = breakout.rtValue;
		weight = breakout.weight;
	};
	bool operator == (Breakout &breakout) {
		return ltTuple == breakout.ltTuple &&
			   ltValue == breakout.ltValue &&
			   rtTuple == breakout.rtTuple &&
			   rtValue == breakout.rtValue;
	};
	bool operator < (Breakout &breakout) {
		if (ltTuple < breakout.ltTuple)
			return true;
		if (ltTuple > breakout.ltTuple)
			return false;
		if (ltValue < breakout.ltValue)
			return true;
		if (ltValue > breakout.ltValue)
			return false;
		if (rtTuple < breakout.rtTuple)
			return true;
		if (rtTuple > breakout.rtTuple)
			return false;
		if (rtValue < breakout.rtValue)
			return true;
		return false;
	};
	int getLtTuple(void) { return ltTuple; };
	int getLtValue(void) { return ltValue; };
	int getRtTuple(void) { return rtTuple; };
	int getRtValue(void) { return rtValue; };
	int getWeight(void) { return weight; };
	void setLtTuple(int lt) { ltTuple = lt; };
	void setRtTuple(int rt) { rtTuple = rt; };
	void setWeight(int w) { weight = w; };
	void incrementWeight(void) { weight++; };
	friend ostream &operator << (ostream &output, const Breakout &breakout) {
		cout << breakout.ltTuple << ' ' << breakout.ltValue << ' '
			 << breakout.rtTuple << ' ' << breakout.rtValue << ' '
			 << breakout.weight;
		return output;
	};
};

class BreakoutList {
private:
	int length;
	Breakout breakout[MaxBreakouts];
public:
	BreakoutList(void) { length = 0; };
	int getLength(void) { return length; };
	void setLength(int len) { length = len; };
	void add(Breakout &bo) {
		add(bo.getLtTuple(), bo.getLtValue(),
			bo.getRtTuple(), bo.getRtValue(), bo.getWeight());
	};
	void add(int ltTuple, int ltValue, int rtTuple, int rtValue, int weight) {
		bool found;
		int i, index;
		Breakout bo(ltTuple, ltValue, rtTuple, rtValue, weight);

		assert(length < MaxBreakouts);
		for (found = false, i = index = 0; !found && i < length; i++) {
			if (bo < breakout[i]) {
				found = true;
				index = i;
			}
		}
		if (!found) {
			breakout[length++] = bo;
			return;
		}
		for (i = length; i >= index + 1; i--)
			breakout[i] = breakout[i - 1];
		breakout[index] = bo;
		length++;
	};
	int binarySearch(Breakout bo) {
		int lo = 0, hi = length - 1, mid;

		while (hi >= lo) {
			mid = (lo + hi) / 2;
			if (bo == breakout[mid])
				return mid;
			if (bo < breakout[mid])
				hi = mid - 1;
			else
				lo = mid + 1;
		}
		return - 1;
	};
	Breakout &operator [](int i) { return breakout[i]; };
	friend ostream &operator << (ostream &output, const BreakoutList &breakoutList) {
		for (int i = 0; i < breakoutList.length; i++)
			output << breakoutList.breakout[i] << endl; 
		return output;
	};
};

class Vertex {
private:
	int color, index;
	static Adjacency *adjacency;
public:
	static int constraintChecks;
	static Adjacency *getAdjacency(void) {
		return adjacency;
	};
	static void setAdjacency(Adjacency *a) {
		adjacency = a;
	};
	// constructors
	Vertex(void) {};
	Vertex(int col, int ind) {
		color = col;
		index = ind;
	};
	Vertex(const Vertex &vertex) {
		color = vertex.color;
		index = vertex.index;
	};
	// getters
	int getColor(void) { return color; };
	int getIndex(void) { return index; };
	// setters
	void setColor(int col) { color = col; };
	void setIndex(int ind) { index = ind; };
	// functions
	bool operator == (Vertex &vertex) {
		return color == vertex.color && index == vertex.index;
	};
	bool violation(Breakout &breakout, Vertex &vertex) {
		constraintChecks++;
		if (color == breakout.getLtValue() &&
			vertex.color == breakout.getRtValue())
			if (adjacency->getElementAt(index, vertex.index))
				return true;
		return false;
	};
	bool violation(Vertex &vertex) {
		constraintChecks++;
		if (color == vertex.color)
			if (adjacency->getElementAt(index, vertex.index)) 
				return true;
		return false;
	};
	bool operator != (Vertex &vertex) {
		if (color != vertex.color) return true;
		if (index != vertex.index) return true;
		return false;
	};
};

int Vertex::constraintChecks;
Adjacency *Vertex::adjacency;

bool ndboAlgorithm(int K, int n, int &breakouts, Vertex *vertex) {
	bool commit;
	int c, i, index, j, newCost, oldCost, oldValue, t, tempCost, value, wt;
	int cv[MaxN], tempCV[MaxN];
	BreakoutList list;

	breakouts = 0;
	for (i = oldCost = 0; i < n; i++) {
		for (c = j = 0; j < n; j++)
			if (j != i && vertex[i].violation(vertex[j]))
				c++;
		cv[i] = c;
		oldCost += c;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		tempCost = oldCost;
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = vertex[i].getColor();
				for (j = 0; j < n; j++)
					tempCV[j] = cv[j];
				for (commit = false, value = 0; !commit && oldCost != 0 
					&& value < K; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							if (j != i && vertex[i].violation(vertex[j]))
								cv[j]--;
						vertex[i].setColor(value);
						for (c = j = 0; j < n; j++) {
							if (j != i && vertex[i].violation(vertex[j])) {
								c++;
								cv[j]++;
							}
						}
						cv[i] = c;
						for (j = t = 0; j < n; j++)
							t += cv[j];
						for (j = wt = 0; j < list.getLength(); j++) {
							Breakout breakout = list[j];
							if (vertex[breakout.getLtTuple()].
								violation(breakout, vertex[breakout.getRtTuple()]))
								wt += breakout.getWeight();
						}
						newCost = t / 2 + wt;
						if (newCost < oldCost) {
							oldCost = newCost;
							commit = true;
						}
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
				}
				if (!commit) {
					vertex[i].setColor(oldValue);
					for (j = 0; j < n; j++)
						cv[j] = tempCV[j];
				}
			}
		}
		if (oldCost == tempCost) {
			breakouts++;
			for (i = oldCost = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (vertex[i].violation(vertex[j])) {
						Breakout breakout(i, vertex[i].getColor(),
							j, vertex[j].getColor(), 1);
						index = list.binarySearch(breakout);
						if (index != - 1) {
							list[index].incrementWeight();
							oldCost += 1 + list[index].getWeight();
						}
						else {
							list.add(breakout);
							oldCost += 2;
						}
					}
				}
			}
		}
	}
	return true;
}

bool sdboAlgorithm1(int K, int n, int &breakouts, Vertex *vertex) {
	int minCost, tempCost, oldValue;
	int c, i, index, j, oldCost, value, wt, t;
	int array[MaxN], cv[MaxN], newCost[MaxColors], tempCV[MaxColors][MaxN];
	BreakoutList list;

	breakouts = 0;
	for (i = oldCost = 0; i < n; i++) {
		for (c = j = 0; j < n; j++)
			if (j != i && vertex[i].violation(vertex[j]))
				c++;
		cv[i] = c;
		oldCost += c;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		tempCost = oldCost;
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = vertex[i].getColor();
				for (value = 0; value < K; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							tempCV[value][j] = cv[j];
						for (j = 0; j < n; j++)
							if (j != i && vertex[i].violation(vertex[j]))
								tempCV[value][j]--;
						vertex[i].setColor(value);
						for (c = j = 0; j < n; j++) {
							if (j != i && vertex[i].violation(vertex[j])) {
								c++;
								tempCV[value][j]++;
							}
						}
						tempCV[value][i] = c;
						for (j = t = 0; j < n; j++)
							t += tempCV[value][j];
						for (j = wt = 0; j < list.getLength(); j++) {
							Breakout breakout = list[j];
							if (vertex[breakout.getLtTuple()].
								violation(breakout, vertex[breakout.getRtTuple()]))
								wt += breakout.getWeight();
						}
						newCost[value] = t / 2 + wt;
						vertex[i].setColor(oldValue);
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
					else
						newCost[value] = oldCost;
				}
				minCost = newCost[0];
				for (value = 1; value < K; value++)
					if (newCost[value] < minCost)
						minCost = newCost[value];
				for (j = value = 0; value < K; value++)
					if (minCost == newCost[value])
						array[j++] = value;
				value = array[0];
				if (value != oldValue) {
					oldCost = minCost;
					vertex[i].setColor(value);
					for (j = 0; j < n; j++)
						cv[j] = tempCV[value][j];
				}	
			}
		}
		if (oldCost == tempCost) {
			breakouts++;
			for (i = oldCost = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (vertex[i].violation(vertex[j])) {
						Breakout breakout(i, vertex[i].getColor(),
							j, vertex[j].getColor(), 1);
						index = list.binarySearch(breakout);
						if (index != - 1) {
							list[index].incrementWeight();
							oldCost += 1 + list[index].getWeight();
						}
						else {
							list.add(breakout);
							oldCost += 2;
						}
					}
				}
			}
		}
	}
	return true;
}

bool sdboAlgorithm2(int K, int n, int &breakouts, Vertex *vertex) {
	int minCost, tempCost, oldValue;
	int c, i, index, j, oldCost, value, wt, t;
	int array[MaxColors], cv[MaxN], newCost[MaxColors], tempCV[MaxColors][MaxN];
	BreakoutList list;

	breakouts = 0;
	for (i = oldCost = 0; i < n; i++) {
		for (c = j = 0; j < n; j++)
			if (j != i && vertex[i].violation(vertex[j]))
				c++;
		cv[i] = c;
		oldCost += c;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		tempCost = oldCost;
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldValue = vertex[i].getColor();
				for (value = 0; value < K; value++) {
					if (value != oldValue) {
						for (j = 0; j < n; j++)
							tempCV[value][j] = cv[j];
						for (j = 0; j < n; j++)
							if (j != i && vertex[i].violation(vertex[j]))
								tempCV[value][j]--;
						vertex[i].setColor(value);
						for (c = j = 0; j < n; j++) {
							if (j != i && vertex[i].violation(vertex[j])) {
								c++;
								tempCV[value][j]++;
							}
						}
						tempCV[value][i] = c;
						for (j = t = 0; j < n; j++)
							t += tempCV[value][j];
						for (j = wt = 0; j < list.getLength(); j++) {
							Breakout breakout = list[j];
							if (vertex[breakout.getLtTuple()].
								violation(breakout, vertex[breakout.getRtTuple()]))
								wt += breakout.getWeight();
						}
						newCost[value] = t / 2 + wt;
						vertex[i].setColor(oldValue);
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
					else
						newCost[value] = oldCost;
				}
				minCost = newCost[0];
				for (value = 1; value < K; value++)
					if (newCost[value] < minCost)
						minCost = newCost[value];
				for (j = value = 0; value < K; value++)
					if (minCost == newCost[value])
						array[j++] = value;
				value = array[rand() % j];
				if (value != oldValue) {
					oldCost = minCost;
					vertex[i].setColor(value);
					for (j = 0; j < n; j++)
						cv[j] = tempCV[value][j];
				}
			}
		}
		if (oldCost == tempCost) {
			breakouts++;
			for (i = oldCost = 0; i < n - 1; i++) {
				for (j = i + 1; j < n; j++) {
					if (vertex[i].violation(vertex[j])) {
						Breakout breakout(i, vertex[i].getColor(),
							j, vertex[j].getColor(), 1);
						index = list.binarySearch(breakout);
						if (index != - 1) {
							list[index].incrementWeight();
							oldCost += 1 + list[index].getWeight();
						}
						else {
							list.add(breakout);
							oldCost += 2;
						}
					}
				}
			}
		}
	}
	return true;
}

void preprocessing(int K, int n, Vertex *vertex) {
	int color, con, i, j, minConflict;
	int c[MaxColors], conflict[MaxColors];

	for (i = 0; i < n; i++) {
		for (color = 0; color < K; color++) {
			vertex[i].setColor(color);
			for (con = j = 0; j < i; j++)
				if (j != i && vertex[i].violation(vertex[j]))
					con++;
			conflict[color] = con;
		}
		minConflict = conflict[0];
		for (color = 1; color < K; color++)
		if (conflict[color] < minConflict)
			minConflict = conflict[color];
		for (color = j = 0; color < K; color++)
			if (minConflict == conflict[color])
				c[j++] = color;
		vertex[i].setColor(c[rand() % j]);	
	}
}

bool MintonMchcAlgorithm(int K, int n, Vertex *vertex) {
	int color, con, count, i, j, min, oldColor, oldCost, t;
	int conflict[MaxColors], cost[MaxColors], index[MaxColors];
	int cv[MaxN], tempCV[MaxColors][MaxN];

	for (i = oldCost = 0; i < n; i++) {
		for (con = j = 0; j < n; j++)
			if (j != i && vertex[i].violation(vertex[j]))
				con++;
		cv[i] = con;
		oldCost += con;
	}
	oldCost /= 2;
	while (oldCost != 0) {
		for (i = 0; oldCost != 0 && i < n; i++) {
			if (cv[i] != 0) {
				oldColor = vertex[i].getColor();
				for (color = 0; color < K; color++) {
					if (color != oldColor) {
						for (j = 0; j < n; j++)
							tempCV[color][j] = cv[j];
						for (j = 0; j < n; j++)
							if (j != i && vertex[i].violation(vertex[j]))
								tempCV[color][j]--;
						vertex[i].setColor(color);
						for (con = j = 0; j < n; j++) {
							if (j != i && vertex[i].violation(vertex[j])) {
								con++;
								tempCV[color][j]++;
							}
						}
						tempCV[color][i] = con;
						for (j = t = 0; j < n; j++)
							t += tempCV[color][j];
						conflict[color] = con;
						cost[color] = t / 2;
						vertex[i].setColor(oldColor);
						candidateSolutions++;
						if (candidateSolutions == MaxCandSol)
							return false;
					}
					else
						conflict[oldColor] = cv[i];
				}
				min = n * n;
				for (color = 0; color < K; color++)
					if (conflict[color] < min)
						min = conflict[color];
				count = 0;
				for (color = 0; color < K; color++)
					if (min == conflict[color])
						index[count++] = color;
				color = index[rand() % count];
				if (color != oldColor) {
					vertex[i].setColor(color);
					oldCost = cost[color];
					for (j = 0; j < n; j++)
						cv[j] = tempCV[color][j];
				}
			}
		}
	}
	return true;
}

bool WFMchcAlgorithm(int k, int n, Vertex *vertex) {
	double p = 0.1, r;
	int col, color, con, i, j, minConflict, t;
	int c[MaxN], conflict[MaxN];
	int cv[MaxN], tempCV[MaxColors][MaxN];

	for (i = 0; i < n; i++) {
		for (con = j = 0; j < n; j++)
			if (j != i && vertex[i].violation(vertex[j]))
				con++;
		cv[i] = con;
	}
	for (;;) {
		for (i = 0, j = 0; i < n; i++)
			if (cv[i] >= 1)
				c[j++] = i;
		if (j == 0)
			break;
		i = c[rand() % j];
		r = (double) rand() / RAND_MAX;
		if (r <= p) {
			for (j = 0; j < n; j++)
				if (j != i && vertex[i].violation(vertex[j]))
					cv[j]--;
			color = rand() % k;
			vertex[i].setColor(color);
			for (con = j = 0; j < n; j++) {
				if (j != i && vertex[i].violation(vertex[j])) {
					con++;
					cv[j]++;
				}
			}
			cv[i] = con;
			candidateSolutions++;
			if (candidateSolutions == MaxCandSol)
				return false;
		}
		else {
			col = vertex[i].getColor();
			for (color = 0; color < k; color++) {
				if (color != col) {
					for (j = 0; j < n; j++)
						tempCV[color][j] = cv[j];
					for (j = 0; j < n; j++)
						if (j != i && vertex[i].violation(vertex[j]))
							tempCV[color][j]--;
					vertex[i].setColor(color);
					for (con = j = 0; j < n; j++) {
						if (j != i && vertex[i].violation(vertex[j])) {
							con++;
							tempCV[color][j]++;
						}
					}
					tempCV[color][i] = con;
					for (j = t = 0; j < n; j++)
						t += tempCV[color][j];
					conflict[color] = con;
					vertex[i].setColor(col);
					candidateSolutions++;
					if (candidateSolutions == MaxCandSol)
						return false;
				}
				else
					conflict[color] = cv[i];
			}
			minConflict = conflict[0];
			for (color = 1; color < k; color++)
				if (conflict[color] < minConflict)
					minConflict = conflict[color];
			for (color = 0, j = 0; color < k; color++)
				if (minConflict == conflict[color])
					c[j++] = color;
			color = c[rand() % j];
			if (color != col) {
				vertex[i].setColor(color);
				for (j = 0; j < n; j++)
					cv[j] = tempCV[color][j];
			}
		}
	}
	return true;
}

int main(int argc, char *argv[]) {
	bool value;
	char name[Number][4] = {"NDB", "SD1", "SD2"/*, "WF1", "WF2", "MT1", "MT2"*/};
	double totalBO[Number] = {0}, totalCandSol[Number] = {0}, totalCC[Number] = {0};
	int bo, i, j, k, l, m, n, t, seed;
	int totalCV[Number] = {0};
	clock_t clock0, clock1, clocks[Number] = {0};
	time_t startTime = time(NULL), finishTime;

#ifdef DEBUG
	if (argc != 5) {
		cout << "usage: " << argv[0] << " m n k s" << endl;
#else
	if (argc != 7) {
		cout << "usage: " << argv[0] << " m n k s t x" << endl;
#endif
		cout << "where m is the number of edges" << endl;
		cout << "      n is the number of vertices" << endl;
		cout << "      k is the number of colors" << endl;
		cout << "      s is the random number generator seed" << endl;
#ifndef DEBUG
		cout << "      t is the number of trials" << endl;
		cout << "      x is the maximum number of candidate solutions" << endl;
#endif
		exit(0);
	}
	m = atoi(argv[1]);
	n = atoi(argv[2]);
	k = atoi(argv[3]);
	seed = atoi(argv[4]);
#ifndef DEBUG
	t = atoi(argv[5]);
	MaxCandSol = atoi(argv[6]);
#endif
	sgenrand(seed);
	srand(seed);
	Vertex *vertex[Number];
	for (i = 0; i < Number; i++) {
		vertex[i] = new Vertex[n];
		for (j = 0; j < n; j++)
			vertex[i][j].setIndex(j);
	}
#ifdef DEBUG
	Adjacency adjacency(k, m, n);
	Vertex::setAdjacency(&adjacency);
	for (i = 0; i < Number; i++)
		for (j = 0; j < n; j++)
			vertex[i][j].setColor(rand() % k);
	ndboAlgorithm(k, n, bo, vertex[0]);
	sdboAlgorithm1(k, n, bo, vertex[1]);
	sdboAlgorithm2(k, n, bo, vertex[2]);
	MintonMchcAlgorithm(k, n, vertex[3]);
	WFMchcAlgorithm(k, n, vertex[4]);
	cout << adjacency << endl;
	for (i = 0; i < 5; i++) {
		for (j = 0; j < n; j++)
			cout << vertex[i][j].getColor() << endl;
		cout << endl;
	}
	return 0;
#endif
	for (i = 0; i < t; i++) {
		Adjacency adjacency(k, m, n);
		Vertex::setAdjacency(&adjacency);
		//initialize vertex colors to random values
		clock0 = clock();
		for (j = 0; j < n; j++)
			vertex[0][j].setColor(rand() % k);
		clock1 = clock() - clock0;
		for (j = 0; j < Number; j++)
			clocks[j] += clock1;
		for (j = 1; j < Number; j++)
			for (l = 0; l < n; l++)
				vertex[j][l] = vertex[0][l];
		clock0 = clock();
		Vertex::constraintChecks = 0;
		preprocessing(k, n, vertex[4]);
		clock1 = clock();
		clocks[4] += clock1 - clock0;
		clocks[6] += clock1 - clock0;
		totalCC[4] += Vertex::constraintChecks;
		totalCC[6] += Vertex::constraintChecks;
		for (j = 0; j < n; j++)
			vertex[6][j] = vertex[4][j];
		cout << (i + 1) << '\t';
		for (j = 0; j < Number; j++) {
			bo = 0;
			candidateSolutions = 1;
			Vertex::constraintChecks = 0;
			clock0 = clock();
			if (j == 0)
				value = ndboAlgorithm(k, n, bo, vertex[j]);
			else if (j == 1)
				value = sdboAlgorithm1(k, n, bo, vertex[j]);
			else if (j == 2)
				value = sdboAlgorithm2(k, n, bo, vertex[j]);
			else if (j == 5 || j == 6)
				value = MintonMchcAlgorithm(k, n, vertex[j]);
			else if (j == 3 || j == 4)
				value = WFMchcAlgorithm(k, n, vertex[j]);
			clock1 = clock();
			if (value) {
				clocks[j] += clock1 - clock0;
				totalBO[j] += bo;
				totalCandSol[j] += candidateSolutions;
				totalCC[j] += Vertex::constraintChecks;
				totalCV[j]++;
			}
			cout << candidateSolutions << '\t' << Vertex::constraintChecks << '\t';
			cout << clock1 - clock0 << '\t';
			if (candidateSolutions < MaxCandSol) {
				for (int p = 0; p < n - 1; p++) {
					for (int q = p + 1; q < n; q++) {
						if (vertex[j][p].violation(vertex[j][q])) {
							cout << "abort: solution error!" << endl;
							exit(0);
						}
					}
				}
			}
		}
		cout << endl;
	}
	cout << "random num gen seed = " << seed << endl;
	cout << "number of edges     = " << m << endl;
	cout << "number of vertices  = " << n << endl;
	cout << "number of colors    = " << k << endl;
	cout << "number of trials    = " << t << endl << endl;
	cout << "ALGO\tCS\tBO\tCC\tCLKS\t%" << endl;
	for (i = 0; i < Number; i++)
		if (totalCV[i] != 0)
			cout << name[i] << '\t'
				 << totalCandSol[i] / totalCV[i] << '\t'
				 << totalBO[i] / totalCV[i] << '\t'
				 << totalCC[i] / totalCV[i] << '\t'
				 << clocks[i] / totalCV[i] << '\t'
				 << 100.0 * totalCV[i] / t << endl;
		else
			cout << name[i] << '\t'
			     << 0 << '\t' << 0 << '\t' << 0 << '\t'
			     << 0 << '\t' << 0 << endl;
	cout << "Legend:" << endl;
	cout << "ALGO = algorithm, CS = candidate solutions" << endl;
	cout << "BO = breakouts, CLKS = clock cycles," << endl;
	cout << "all results are averages" << endl;
	cout << "NDB = next descent breakout" << endl;
	cout << "SD1 = steepest descent breakout non-sliding" << endl;
	cout << "SD2 = steepest descent breakout sliding" << endl;
	cout << "WF1 = Wallace and Freuder's MCHC without preprocessing" << endl;
	cout << "WF2 = Wallace and Freuder's MCHC with preprocessing" << endl << endl;
	cout << "MT1 = Minton's MCHC without preprocessing" << endl;
	cout << "MT2 = Minton's MCHC with preprocessing" << endl;
	finishTime = time(NULL) - startTime;
	cout << "total time in seconds = " << finishTime << endl;
	return 0;
}