Expected output for EDGE COLORING - BiPartite graph in C language below is the output required. & I'll also pasted the input data Please try if any programmer can!
Output::
Case 1: edge 0 (0 0) gets color 0
Case 1: edge 1 (0 1) gets color 1
Case 1: edge 2 (0 2) gets color 2
Case 1: edge 3 (0 3) gets color 3
Case 1: edge 4 (0 4) gets color 4
Case 1: edge 5 (0 5) gets color 5
Case 1: edge 6 (0 6) gets color 6
Case 1: edge 7 (1 0) gets color 1
Case 1: edge 8 (1 1) gets color 0
Case 1: edge 9 (1 2) gets color 3
Case 1: edge 10 (1 3) gets color 2
Case 1: edge 11 (1 4) gets color 5
Case 1: edge 12 (1 5) gets color 4
Case 2: edge 13 (1 6) gets color a=6, swaps with b=0 r:6 l:0 r:0
Case 1: edge 14 (2 0) gets color 0
Case 1: edge 15 (2 1) gets color 2
Case 1: edge 16 (2 2) gets color 1
Case 1: edge 17 (2 3) gets color 4
Case 1: edge 18 (2 4) gets color 3
Case 1: edge 19 (2 5) gets color 6
Case 1: edge 20 (2 6) gets color 5
Case 1: edge 21 (3 0) gets color 2
Case 1: edge 22 (3 1) gets color 3
Case 1: edge 23 (3 2) gets color 0
Case 1: edge 24 (3 3) gets color 1
Case 1: edge 25 (3 4) gets color 6
Case 2: edge 26 (3 5) gets color a=4, swaps with b=0 r:5 l:1 r:1
Case 2: edge 27 (3 6) gets color a=5, swaps with b=1 r:6 l:2 r:2
Case 1: edge 28 (4 0) gets color 3
Case 1: edge 29 (4 1) gets color 0
Case 1: edge 30 (4 2) gets color 1
Case 1: edge 31 (4 3) gets color 5
Case 1: edge 32 (4 4) gets color 2
Case 2: edge 33 (4 5) gets color a=4, swaps with b=1 r:5 l:3 r:3 l:2 r:6
Case 2: edge 34 (4 6) gets color a=6, swaps with b=1 r:6 l:1 r:0 l:0 r:1
0 0 1
0 1 6
0 2 2
0 3 3
0 4 4
0 5 5
0 6 0
1 0 6
1 1 4
1 2 3
1 3 2
1 4 5
1 5 0
1 6 1
2 0 0
2 1 2
2 2 5
2 3 1
2 4 3
2 5 6
2 6 4
3 0 2
3 1 3
3 2 0
3 3 4
3 4 6
3 5 1
3 6 5
4 0 3
4 1 0
4 2 1
4 3 5
4 4 2
4 5 4
4 6 6
INPUT::
5 7 35
0 0
0 1
0 2
0 3
0 4
0 5
0 6
1 0
1 1
1 2
1 3
1 4
1 5
1 6
2 0
2 1
2 2
2 3
2 4
2 5
2 6
3 0
3 1
3 2
3 3
3 4
3 5
3 6
4 0
4 1
4 2
4 3
4 4
4 5
4 6
Question:
Requirements:
- Write (and test) a C program to edge color a provided bipartite graph.
The input to your program will be:
a. , , and m, the numbers of left column vertices, right column vertices, and edges. and
.
b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - - Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur.
The output from your program will be:
a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident
vertices, or 2) using an alternating (a, b) path. For (1), simply indicate the free color that is used for the edge. For
(2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path.
b. A list of the edges (input order) and the final color for each edge.