graph-coloring/colorize.cpp at master · jargnar/graph-coloring · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "graph.h"
#include "colorize.h"

int colors;
int Vcolor[100];
int possible[100][100];
int spilledV[100];
int spilledVsize=0;
int Psize;

void setColors(int colr) {
	colors = colr;
}

/* The possibility heuristic checks for possible colors
   that can be assigned to a vertex V
   based on its neighbors colors
   and keeps track of this intelligence in an array 'possible[]'
*/
void buildPossibility(int pos) {
	Psize = colors;
	for(int i=0; i<colors; ++i) {
		possible[pos][i]=i;
	}
}

void removePossibility(int pos, int colr) {
	int Index = -1;
	for(int i=0; i<Psize; ++i) {
		if(possible[pos][i]==colr) Index = i;
	}
	if(Index!=-1) {
		for(int i=Index; i<Psize-1; ++i) {
			possible[pos][i] = possible[pos][i+1];
		}
		Psize = Psize - 1;
	}
}

int getColor(int pos) {
	return Vcolor[pos];
}

/* Those variables which need to be stored in the mem */
void spill(int pos) {
	spilledV[spilledVsize] = V[pos];
	eraseVertex(pos);
	eraseEdge(pos);
	for(int i=0; i<Vsize; ++i) {
		for(int j=0; j<Esize[i]; ++j) {
			if(spilledV[spilledVsize]==E[i][j]) {
			eraseSingleEdge(i,j);
			break;
			}
		}
	}
	spilledVsize = spilledVsize + 1;
}

/* Reduces interference Graph */
void simplify() {

	bool SpillCondition = true;
	int DeletionIndex = 0;

	while (Vsize!=1) {

		for(int j=0; j<Vsize; ++j) {
			if(Esize[j]<colors) {
				SpillCondition = false;
				DeletionIndex = j;
			}
		}

		if(SpillCondition) {
			spill(0);
		} else if (Esize[DeletionIndex]<colors) {
			printGraph();
			deleteVertex(V[DeletionIndex]);
		}

		SpillCondition = true;
	}
}

/* Greedily Selects Colors */
void select(int pos) {


	buildPossibility(pos);

	if((Vsize == 1)&&(V[0]==V[pos])&&(getIndex(V[pos])==0)) {
		Vcolor[0] = possible[pos][0];
		return;
	}

	int Vpos = getIndex(V[pos]);

	/*Traverse thru all edges of Vertex v,
	  which we are about to color,
	  to eliminate the colors which are already taken
          using the possibility heuristic
	*/

	int tmpV;
	for(int i=0; i<Esize[Vpos]; ++i) {
		tmpV = E[Vpos][i];
		removePossibility(Vpos,getColor(getIndex(tmpV)));
	}

	Vcolor[getIndex(V[pos])] = possible[pos][0];
}