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.

advertisement
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.

advertisement
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn