C++-এ লাইন গ্রাফে এজ কালারিং বাস্তবায়ন

একটি অনির্দেশিত গ্রাফ G-এর লাইন গ্রাফ L(G) হলো এমন একটি গ্রাফ যা G-এর এজগুলোর মধ্যে অ্যাডজেসেন্সি (সন্নিহিততা) রিপ্রেজেন্ট করে। এই প্রোগ্রামে ইনপুট গ্রাফ থেকে লাইন গ্রাফ তৈরি করে তার এজগুলো কালার করা হয়েছে।

এলগরিদম

শুরু
  নোড সংখ্যা 'n' এবং এজ সংখ্যা 'e' ইনপুট নিন
  'e' টি এজের ভার্টেক্স জোড়া ed[][]-এ ইনপুট নিন
  Function GenLineGraph():
    লাইন গ্রাফের এজ LineEd[][] তৈরি করুন
    প্রতিটি এজকে তার অ্যাডজেসেন্ট এজlerle কানেক্ট করুন
  Function EdgeColor():
    লাইন গ্রাফের এজগুলো কালার করুন
    বর্তমান এজকে কালার col (শুরু ১) দিন
    যদি কোনো অ্যাডজেসেন্ট এজে একই কালার থাকে:
      কালার বাতিল করুন, পরবর্তী কালার ট্রাই করুন (goto flag)
    প্রতিটি এজের কালার প্রিন্ট করুন
শেষ

উদাহরণ কোড

#include <iostream>
using namespace std;

int GenLineGraph(int ed[][2], char LineEd[][3], int e) {
    int i, cnt = 0, j, N;
    char c;
    for (i = 0; i < e; i++) {
        for (j = i + 1; j < e; j++) {
            if (ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] ||
                ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
                LineEd[cnt][0] = 'a' + i;
                LineEd[cnt][1] = 'a' + j;
                LineEd[cnt][2] = 0;
                cnt++;
            }
        }
    }
    N = cnt;
    cout << "\n\nThe adjacency list representation for the given graph: ";
    for (i = 0; i < e; i++) {
        cnt = 0;
        c = 'a' + i;
        cout << "\n\t" << c << "-> { ";
        for (j = 0; j < N; j++) {
            if (LineEd[j][0] == i + 'a') {
                cout << LineEd[j][1] << " ";
                cnt++;
            } else if (LineEd[j][1] == i + 'a') {
                cout << LineEd[j][0] << " ";
                cnt++;
            } else if (j == e - 1 && cnt == 0)
                cout << "Isolated Vertex!";
        }
        cout << " }";
    }
    return N;
}

void EdgeColor(char ed[][3], int e) {
    int i, col, j;
    for (i = 0; i < e; i++) {
        col = 1;
        flag:
        ed[i][2] = col;
        for (j = 0; j < e; j++) {
            if (j == i) continue;
            if (ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] ||
                ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
                if (ed[j][2] == ed[i][2]) {
                    col++;
                    goto flag;
                }
            }
        }
    }
}

int main() {
    int i, n, e, j, max = -1;
    char c = 'a';
    cout << "Enter the number of vertices of the graph: ";
    cin >> n;
    cout << "Enter the number of edges of the graph: ";
    cin >> e;
    int ed[e][2];
    char LineEd[e * e][3];

    for (i = 0; i < e; i++) {
        cout << "\nEnter the vertex pair for edge '" << c++ << "'";
        cout << "\nV(1): "; cin >> ed[i][0];
        cout << "V(2): "; cin >> ed[i][1];
    }

    e = GenLineGraph(ed, LineEd, e);
    EdgeColor(LineEd, e);

    for (i = 0; i < e; i++)
        cout << "\nThe color of the edge between vertex n(1):"
             << LineEd[i][0] << " and n(2):" << LineEd[i][1]
             << " is: color" << (0 + LineEd[i][2]) << ".";
}

নমুনা আউটপুট

Enter the number of vertices of the graph: 4
Enter the number of edges of the graph: 3
Enter the vertex pair for edge 'a'
V(1): 1 V(2): 2
Enter the vertex pair for edge 'b'
V(1): 3 V(2): 2
Enter the vertex pair for edge 'c'
V(1): 4 V(2): 1

The adjacency list representation for the given graph:
a-> { b c }
b-> { a }
c-> { a }

The color of the edge between vertex n(1):a and n(2):b is: color1.
The color of the edge between vertex n(1):a and n(2):c is: color2.

নোট: এই কোডে goto ব্যবহার করা হয়েছে যা আধুনিক C++-এ এড়ানো উচিত। লাইন গ্রাফের এজ কালারিং হলো মূল গ্রাফের ভার্টেক্স কালারিং সমস্যা। গ্রেডি অ্যালগরিদম সবসময় অপ্টিমাল কালার দেয় না।