C++ Program to Perform Edge Coloring for the Complete Graph

This is a C++ program to perform edge coloring on a complete graph.

Problem Description

1. This algorithm performs edge coloring on a complete graph.
2. A complete graph is a graph which has a connecting edge between any pair of vertexes.

Problem Solution

1. This algorithm takes the input of the number of vertexes.
2. Construct a complete graph for v vertex.
3. It assigns a color to edges without assigning the same color to two adjacent edges.
4. Exit.

Program/Source Code

This is a C++ program to perform edge coloring on complete graph.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
 
using namespace std;
 
// A function to color edges of the graph.
void EdgeColoring(int edge[][3], int e)
{
	int i, col, j;
	// Loop to assign a valid color to every edge 'i'.
	for(i = 0; i < e; i++)
	{
		col = 1;
		flag:
		// Assign a color and then check its validity.
		edge[i][2] = col;
		for(j = 0; j < e; j++)
		{
			if(j == i)
				continue;
 
			// Check the colors of the edges adjacent to the edge i.
			if(edge[j][0] == edge[i][0] || edge[j][0] == edge[i][1] || edge[j][1] == edge[i][0] || edge[j][1] == edge[i][1])
			{
				// If the color matches then goto line 11 and assign next color to the edge and check again.
				if(edge[j][2] == edge[i][2])
				{
					col++;
					goto flag;
				}
			}
		}
	}
}
 
int main()
{
	int i, v, e, j, count = 0;
 
	// take the input of the number of vertex and edges.
	cout<<"Enter the number of vertexes for the complete graph: ";
	cin>>v;
 
	e = (v*(v-1))/2;
	int edge[e][3];
 
	// Construct a complete graph for the given number of edges.
	for(i = 1; i <= v; i++)
	{
		for(j = i+1; j <= v; j++)
		{
			edge[count][0] = i;
			edge[count][1] = j;
			edge[count][2] = -1;
			count++;
 		}
	}
 
	// Color the edges of the graph.
	EdgeColoring(edge , e);
 
	// Print the color of each edge.
	for(i = 0; i < e; i++)
		cout<<"\nThe color of the edge between vertex V(1):"<<edge[i][0]<<" and V(2):"<<edge[i][1]<<" is: color"<<edge[i][2]<<".";
}

Program Explanation

1. Take the input of the number of vertexes ‘v’.
2. Construct a complete graph having e=v*(v-1)/2 edges, in edge[][].
3. Using EdgeColoring(), Color the graph edges.
4. Inside EdgeColoring(), assign color to current edge as col i.e. 1 initially.
5. If any of the adjacent edges have the same color then discard this color and go to flag again and try next color.
6. Return to main and print the color for each edge.
7. Exit.

Runtime Test Cases

Case 1:
Enter the number of vertexes for the complete graph: 5
 
The color of the edge between vertex V(1):1 and V(2):2 is: color1.
The color of the edge between vertex V(1):1 and V(2):3 is: color2.
The color of the edge between vertex V(1):1 and V(2):4 is: color3.
The color of the edge between vertex V(1):1 and V(2):5 is: color4.
The color of the edge between vertex V(1):2 and V(2):3 is: color3.
The color of the edge between vertex V(1):2 and V(2):4 is: color2.
The color of the edge between vertex V(1):2 and V(2):5 is: color5.
The color of the edge between vertex V(1):3 and V(2):4 is: color1.
The color of the edge between vertex V(1):3 and V(2):5 is: color6.
The color of the edge between vertex V(1):4 and V(2):5 is: color7.
 
Case 2:
Enter the number of vertexes for the complete graph: 7
 
The color of the edge between vertex V(1):1 and V(2):2 is: color1.
The color of the edge between vertex V(1):1 and V(2):3 is: color2.
The color of the edge between vertex V(1):1 and V(2):4 is: color3.
The color of the edge between vertex V(1):1 and V(2):5 is: color4.
The color of the edge between vertex V(1):1 and V(2):6 is: color5.
The color of the edge between vertex V(1):1 and V(2):7 is: color6.
The color of the edge between vertex V(1):2 and V(2):3 is: color3.
The color of the edge between vertex V(1):2 and V(2):4 is: color2.
The color of the edge between vertex V(1):2 and V(2):5 is: color5.
The color of the edge between vertex V(1):2 and V(2):6 is: color4.
The color of the edge between vertex V(1):2 and V(2):7 is: color7.
The color of the edge between vertex V(1):3 and V(2):4 is: color1.
The color of the edge between vertex V(1):3 and V(2):5 is: color6.
The color of the edge between vertex V(1):3 and V(2):6 is: color7.
The color of the edge between vertex V(1):3 and V(2):7 is: color4.
The color of the edge between vertex V(1):4 and V(2):5 is: color7.
The color of the edge between vertex V(1):4 and V(2):6 is: color6.
The color of the edge between vertex V(1):4 and V(2):7 is: color5.
The color of the edge between vertex V(1):5 and V(2):6 is: color1.
The color of the edge between vertex V(1):5 and V(2):7 is: color2.
The color of the edge between vertex V(1):6 and V(2):7 is: color3.

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

« Prev - C++ Program to Find the Median of Two Sorted Arrays using Binary Search

» Next - C++ Program to Generate All the Set Partitions of n Numbers Beginning from 1 and so on

Related Posts:

Recommended Articles: