C++ Program to Perform Edge Coloring of a Graph

This is a C++ Program to Perform Edge Coloring of a Graph.

Problem Description

In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color.

Problem Solution

1. Any two edges connected to same vertex will be adjacent.
2. Take a vertex and give different colours, to all edges connected it, remove those edges from graph (or mark them as coloured).
3. Traverse one of its edges.
4. And repeat the step 2 with the new vertex.

Program/Source Code

Here is source code of the C++ Program to Perform Edge Coloring of a Graph. The program is successfully compiled and tested under Linux platform. The program output is also shown below.

#include<bits/stdc++.h>
 
using namespace std;
 
int n,e,i,j;
vector<vector<pair<int,int> > > graph;
vector<int> color;
bool vis[100011];
 
void colour(int node)
{
	queue<int> q;
	int c=0;
	set<int> already_colored;
	if(vis[node])
		return;
	vis[node]=1;
 
	for(i=0;i<graph[node].size();i++)
	{
		if(color[graph[node][i].second]!=-1)
		{
			already_colored.insert(color[graph[node][i].second]);
		}
	}
 
	for(i=0;i<graph[node].size();i++)
	{
		if(!vis[graph[node][i].first])
		{
			q.push(graph[node][i].first);
		}
		if(color[graph[node][i].second]==-1)
		{
			while(already_colored.find(c)!=already_colored.end())
			c++;
			//cout<<graph[node][i].second+1<<" "<<c<<"\n";
			color[graph[node][i].second]=c;
			already_colored.insert(c);
			c++;
		}
	}
	while(!q.empty())
	{
		int temp=q.front();
		q.pop();
		colour(temp);
	}
	return;
}
 
int main()
{
	int x,y;
	set<int> empty;
	cout<<"Enter number of vertices and edges respectively:";
	cin>>n>>e;
	cout<<"\n";
	graph.resize(n); //  Number of Vertices.
	color.resize(e,-1); // Number of Edges.
	memset(vis,0,sizeof(vis));
	for(i=0;i<e;i++)
	{
		cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
		cin>>x>>y;
		x--; y--;
		graph[x].push_back(make_pair(y,i));
		graph[y].push_back(make_pair(x,i));
	}
	colour(0);
	for(i=0;i<e;i++)
	{
		cout<<"Edge "<<i+1<<" is coloured "<<color[i]+1<<"\n";
	}
}

Program Explanation

1. User must first enter the number of vertices, N, and then number of edges, E, in the graph.
2. It should be followed by E lines, denoting A and B, if there is an edge between A and B.
3. The graph is stored as adjacency list.
4. Then BFS is implemented using queue and colours are assigned to each edge.
5. Numbers have been used instead of colours, for simplicity of source code.

Runtime Test Cases

 
Case 1:
Enter number of vertices and edges respectively:4 6
 
 
Enter edge vertices of edge 1 :1 2
 
Enter edge vertices of edge 2 :2 3
 
Enter edge vertices of edge 3 :3 4
 
Enter edge vertices of edge 4 :1 4
 
Enter edge vertices of edge 5 :2 4
 
Enter edge vertices of edge 6 :1 3
 
Edge 1 is coloured 1
Edge 2 is coloured 2
Edge 3 is coloured 1
Edge 4 is coloured 2
Edge 5 is coloured 3
Edge 6 is coloured 3

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

« Prev - C++ Program to Perform Greedy Coloring

» Next - C++ Program to Check whether a Given Graph is Bipartite or not

Related Posts:

Recommended Articles: