Welsh-Powell Algorithm

Reading time: 20 minutes | Coding time: 9 minutes

In graph theory, Welsh Powell is used to implement graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
In 1967 Welsh and Powell introduced in an upper bound to the chromatic number of a graph . It provides a greedy algorithm that runs on a static graph.
The vertices are ordered according to their degrees, the resulting greedy coloring uses at most $max_i min{ d(x_i) + 1, i}$ colors, at most one more than the graph’s maximum degree. This heuristic is called the Welsh–Powell algorithm.

Welsh–Powell algorithm

Pseudocode



Welsh Powell Algorithm 
* Find the degree of each vertex . 
* List the vertices in order of descending valence i.e.valence degree(v(i)) >= degree(v(i+1)) .
* Colour the first vertex in the list.  
* Go down the sorted list and color every vertex not connected to the colored  vertices above the same color then cross  out all colored vertices in the list.
* Repeat the process on the uncolored vertices with a new color-always working in descending order of degree until all in descending order of degree until all vertices are colored.

ALGORITHM IMPLEMENTATION USING IMAGES
wp1

wp2

wp3

wp4

wp5

wp6-1


Implementations


  • C++

C++


#include <iostream>
#include <algorithm>
#include <cstring>
const int x = 10;   //vertex no.
const int colors[x] = { 0,1,2,3,4,5,6,7,8,9 };
int counter = 0;
bool problem = false;
/*  Example graph
	 B      G---------J
	/ \      \        |
       /   \      \       |
      /     \      \      |
     A------C-------E-----K
     \     /       /      |
      \   /       /       |
       \ /       /        |
        D-------F---------L
*/
bool graf[x][x] = { //adj. matrix
	0,1,1,1,0,0,0,0,0,0,
	1,0,1,0,0,0,0,0,0,0,
	1,1,0,1,1,0,0,0,0,0,
	1,0,1,0,0,1,0,0,0,0,
	0,0,1,0,0,1,1,0,1,0,
	0,0,0,1,1,0,0,0,1,1,
	0,0,0,0,1,0,0,1,0,0,
	0,0,0,0,0,0,1,0,1,0,
	0,0,0,0,1,0,0,1,0,1,
	0,0,0,0,0,1,0,0,1,0
};
char vertex_names[x] = {'A','B','C','D','E','F','G','J','K','L'};
int rate_list[x]; //{ 0,0,0,0,0,0,0,0,0,0};
struct Graf 
{
	char vertex_id[x];
	int vertex_rates[x];
	bool adj[x][x];
	int colors[x];
	bool colored[x];
};
//welsh powell
void colorIt(Graf g) {
	counter++;
	int biggest=0;
	int temp_rate = 0;
	//rate listing from adj matrix (counting edges)
	if (counter == 1)
		for (int i = 0; i < x; i++)
			for (int j = 0; j < x; j++)
				if (g.adj[i][j])
					rate_list[i]++;
	for (int w = 0; w < x; w++)
		if (!g.colored[w]) 
        {
			g.vertex_rates[w] = rate_list[w];
			if (temp_rate < g.vertex_rates[w]) 
            {
				temp_rate = g.vertex_rates[w];
				biggest = w;
			}
		}
	//coloring biggest one first
	g.colors[biggest] = colors[counter];
	std::cout << g.vertex_id[biggest] <<":color "<< g.colors[biggest]<<std::endl;
	//coloring which doesn't have path with biggest one
	for (int e=0;e < x;e++)
		if (!g.adj[biggest][e] && biggest!=e && !g.colored[e]) 
        {
			for (int t = 0; t < x;t++) 
            {
				if(g.adj[e][t] &&g.colors[t]==g.colors[biggest]) problem = true;
					if (t == x - 1 && !problem) 
                    {
						g.colors[e] = colors[counter];
						std::cout << g.vertex_id[e] <<":color "<< g.colors[e] << std::endl;
						g.colored[e] = true;
						problem = false;
					}
					else if (t == x - 1) problem = false;
			}
		}
		g.colored[biggest] = true;
	if (std::all_of(std::begin(g.colored), std::end(g.colored), [](bool i) { return i; })) {
		std::cout << "Graph full colored" << std::endl;
		system("pause");
		exit(EXIT_SUCCESS);
	}
	else colorIt(g); //recusive because too lazy to sort :)
}
int main()
{
	Graf graf1;
	//init color
	for (int y = 0; y < x; y++) 
    {
		graf1.colors[y] = 99;
		graf1.colored[y] = false;
	}
	//init graph
	memcpy(&graf1.adj, &graf, sizeof(graf1.adj));
	memcpy(&graf1.vertex_id, &vertex_names, sizeof(graf1.vertex_id));
	colorIt(graf1);
	return 0;
}

Complexity

  • The complexity of algorithm is $ O(N^2) $

Applications


  1. Making Schedule or Time Table: Suppose we want to make am exam schedule for a university. We have list different subjects and students enrolled in every subject. Many subjects would have common students (of same batch, some backlog students, etc). How do we schedule the exam so that no two exams with a common student are scheduled at same time? How many minimum time slots are needed to schedule all exams? This problem can be represented as a graph where every vertex is a subject and an edge between two vertices mean there is a common student. So this is a graph coloring problem where minimum number of time slots is equal to the chromatic number of the graph.

  2. Mobile Radio Frequency Assignment: When frequencies are assigned to towers, frequencies assigned to all towers at the same location must be different. How to assign frequencies with this constraint? What is the minimum number of frequencies needed? This problem is also an instance of graph coloring problem where every tower represents a vertex and an edge between two towers represents that they are in range of each other.

  3. Sudoku: Sudoku is also a variation of Graph coloring problem where every cell represents a vertex. There is an edge between two vertices if they are in same row or same column or same block.

  4. Register Allocation: In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers. This problem is also a graph coloring problem.

  5. Bipartite Graphs: We can check if a graph is Bipartite or not by coloring the graph using two colors. If a given graph is 2-colorable, then it is Bipartite, otherwise not. See this for more details.

  6. Map Coloring: Geographical maps of countries or states where no two adjacent cities cannot be assigned same color. Four colors are sufficient to color any map.

Check Our Link For more details
Check Our Link For more details