C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Perform Edge Coloring to the Line Graph of an Input Graph



Perform Edge Coloring to the Line Graph of an Input Graph

- This algorithm performs edge coloring to the line graph of an input graph.
- A line graph can be generated from the given graph by assuming edge as vertex and vertex as edges between the vertex to form line graph.

- This algorithm takes the input of the number of vertexes and the number of edges in the graph.
- It takes the input of vertex pairs for the given number of edges.
- It generates a line graph for the given graph.
- Then for the generated line graph, it assigns a color to edges without assigning the same color to two adjacent edges.
- Exit.

 #include<iostream>
 
using namespace std;
 
// A function to generate line graph from a given graph.
int GenerateLineGraph(int edge[][2], char LineEdge[][3], int e)
{
	int i, count = 0, j, NOV;
	char ch;
	// Loop to assign a valid color to every edge 'i'.
	for(i = 0; i < e; i++)
	{
		for(j = i+1; j < e; j++)
		{
			// 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])
			{
				LineEdge[count][0] = 'a'+i;
				LineEdge[count][1] = 'a'+j;
				LineEdge[count][2] = 0;
				count++;
			}
		}
	}
	NOV = count;
 
	// Print the adjacency list representation of the graph.
	cout<<"\n\nThe adjacency list representation for the given graph: ";
	for(i = 0; i < e; i++)
	{
		count = 0;
		// For each vertex print, its adjacent vertex.
		ch = 'a'+i;
		cout<<"\n\t"<<ch<<"-> { ";
		for(j = 0; j < NOV; j++)
		{
			if(LineEdge[j][0] == i+'a')
			{
				cout<<LineEdge[j][1]<<"  ";
				count++;
			}
			else if(LineEdge[j][1] == i+'a')
			{
				cout<<LineEdge[j][0]<<"  ";
				count++;
			}
			else if(j == e-1 && count == 0)
				cout<<"Isolated Vertex!";
		}
		cout<<" }";
	}
	return NOV;
}
 
// A function to color edges of the graph.
void EdgeColoring(char 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, max = -1;
	char ch = 'a';
 
	// take the input of the number of vertex and edges.
	cout<<"Enter the number of vertexes of the graph: ";
	cin>>v;
	cout<<"Enter the number of edges of the graph: ";
	cin>>e;
 
	int edge[e][2];
	char LineEdge[e*e][3];
 
	// Take the input of the adjacent vertex pairs of the given graph.
	for(i = 0; i < e; i++)
	{
		cout<<"\nEnter the vertex pair for edge '"<<ch++<<"'";
		cout<<"\nV(1): ";
		cin>>edge[i][0];
		cout<<"V(2): ";
		cin>>edge[i][1];
	}
 
	// Generate line graph.
	e = GenerateLineGraph(edge, LineEdge, e);
 
	// Color The line graph.
	EdgeColoring(LineEdge , e);
 
	// Print the color of edges of line graph.
	for(i = 0; i < e; i++)
		cout<<"\nThe color of the edge between vertex V(1):"<<LineEdge[i][0]<<" and V(2):"<<LineEdge[i][1]<<" is: color"<<0+LineEdge[i][2]<<".";
}