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]<<"."; }