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.

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.