#define V 19				// Number of vertices or sessions
#define E 43				// Number of edges or session conflicts
int color[V];  				// To enter coloring
int nc;				 	// To count number of colors used
int edges[E][2];			// For the data:
							// most popular vertices first

int earlier[E], nghbrs[V];			// Sparse data structures

2lp_main()
{
	data();				// Entries from Table 5.1
	build_data_structures();
	color_the_graph();
	output();
}

color_first_vertex()
{
	color[0] = 0; 				// Actually the default
	nc = 1;  					// One color has been used
}

color_the_vertex(int v,c)
{
	conflict_free(v,c);				// Check color c available

	color[v] = c;					// Color vertex v with color c
	if nc == c;  					// If color c is new
	then nc = c + 1; 					// then increment number of colors
}

color_the_graph()
{
	color_first_vertex();
	and(int v=1;v<V;v++)
		c_or(int c=0;c<=nc;c++)
			color_the_vertex(v,c);
}

conflict_free(int v,c)
{
int begin,end;

	begin = nghbrs[v-1]; 			 // v >= 1 
	end = nghbrs[v];

	and(int k=begin;k<end;k++)
		color[earlier[k]] != c;
}

connected(int v,w)
{
	c_or(int e=0;e<E;e++)
		c_either {
			edges[e][0] == v; 
			edges[e][1] == w;
		}
		or  {
			edges[e][0] == w; 
			edges[e][1] == v;
		}
}

build_data_structures()
{
int cnt;
	cnt = 0;

	and(int v=1;v<V;v++) 
		and(int k=0;k<v;k++)
			if connected(k,v);						
			then {			// k is an earlier neighbor of v
				earlier[cnt] = k;				// Enter neighbor 
				nghbrs[v] = nghbrs[v]+1;			//Count neighbors
				cnt = cnt + 1;					// Increment placeholder
			}	
	
	and(int v=1;v<V;v++)		// Readjust indexing scheme 
		nghbrs[v] = nghbrs[v] + nghbrs[v-1];
}

data()
{
	edges = {
		0,8, 0,3, 0,5, 0,4, 0,9, 0,12, 0,13, 
		1,10, 1,7, 1,11, 1,6, 1,4, 1,12, 1,5, 
		2,6, 2,10, 2,13, 2,4, 2,9, 2,7, 2,12,
		3,14, 3,8, 3,11, 3,16, 3,12,
		4,15, 4,8, 4,17, 
		5,10, 5,6, 5,15, 5,16,
		6,7, 6,15, 
		7,9, 8,11, 9,18, 10,18, 11,14, 13,17, 14,17, 16,18
	} ;
}

output()
{
	printf("The meeting can be run with %d parallel sessions \n",nc);
}


#define UNCOLORED -1
dual_color_the_graph()
{
	and(int i=0;i<V;i++)						// Initialize vertices
		color[i] = UNCOLORED; 
	color[0] = 0;				// Assign first color to first vertex
	and(int c=0;c<V;c++) {							// Cycle through colors
		and(int i=1;i<V;i++) 						// Apply color where possible
			if  { 
				color[i] == UNCOLORED; 
				conflict_free(i,c); 
			} 
			then color[i] = c;
		if and(int v=0;v<V;v++) 			// All vertices colored ?
			color[v] != UNCOLORED;
		then { 
			printf("It took %d colors\n",c+1); 
			break; 
		}
	}
}
#undef UNCOLORED
 