グラフから適切なフィードバックアークセットを見つけるC++プログラム

有向グラフにおいて、特定の辺を取り除くだけでグラフが非巡回有向グラフ（DAG：Directed Acyclic Graph）に変わるような辺の集合は、「フィードバックアークセット（Feedback Arc Set）」と呼ばれます。本記事では、C++を使ってグラフからこのフィードバックアークセットを見つけるプログラムを紹介します。

フィードバックアークセットとは

有向グラフに閉路（サイクル）が含まれている場合、その閉路を構成する辺をいくつか取り除くことで、グラフをDAGへと変換できます。このとき取り除いた辺の集合がフィードバックアークセットです。スケジューリング問題や依存関係の解析など、循環参照を解消したい場面で活用される重要な概念です。

アルゴリズム

以下は、グラフがDAGかどうかを判定し、必要に応じてフィードバックアークセットを検出する手順です。

開始
関数 checkCG(int n)：
n：頂点の数。
arr：struct graph 型の変数。
cnt = 0、size = (n-1) で初期化する。
i = 0 から n-1 まで繰り返す：
　　if (cnt == size)
　　　　return 0
　　if (arr[i].ptr == NULL)
　　　　cnt を1増やす。
　　　　j = 0 から n-1 まで繰り返す：
　　　　　　while (arr[j].ptr != NULL)：
　　　　　　　　if ((arr[j].ptr)->des == (arr[i].ptr)->des)
　　　　　　　　　　(arr[j].ptr)->des = -1
　　　　　　　　arr[i].ptr = (arr[i].ptr)->next
　　　　　　（while終了）
　　　　（for終了）
　　（if終了）
（for終了）
visited[n + 1] を初期化する。
i = 0 から n-1 まで繰り返す：
　　while (arr[i].ptr != NULL)：
　　　　(arr[i].ptr)->des を出力する。
　　　　visited[i] = 1
　　　　j = 0 から n-1 まで繰り返す：
　　　　　　while (arr[j].ptr != NULL)：
　　　　　　　　(arr[j].ptr)->des を出力する。
　　　　　　　　if (visited[arr[j].v] == 1)
　　　　　　　　　　arr[i].v << " - " << arr[j].v を出力する。
　　　　　　　　arr[j].ptr = (arr[j].ptr)->next
　　　　　　（while終了）
　　　　（for終了）
　　　　arr[i].ptr = (arr[i].ptr)->next
　　（while終了）
（for終了）
return 1
終了

C++による実装例

次のコードでは、隣接リスト形式でグラフを構築し、各頂点の出次数を確認しながらDAG判定を行います。

#include<iostream>
using namespace std;
int c = 0;
struct ad_list {
    int des;
    ad_list *next;
}*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
struct Graph {
    int v;
    ad_list *ptr;
} arr[6];
void addRevEdge(int sr, int des) { // 逆辺をグラフに追加する
    np1 = new ad_list;
    np1->des = sr;
    np1->next = NULL;
    if (arr[des].ptr == NULL) {
        arr[des].ptr = np1;
        q = arr[des].ptr;
        q->next = NULL;
    } else {
        q = arr[des].ptr;
        while (q->next != NULL) {
            q = q->next;
        }
        q->next = np1;
    }
}
void addEd(int sr, int des) { // 辺をグラフに追加する
    np = new ad_list;
    np->des = des;
    np->next = NULL;
    if (arr[sr].ptr == NULL) {
        arr[sr].ptr = np;
        p = arr[sr].ptr;
        p->next = NULL;
    } else {
        p = arr[sr].ptr;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = np;
    }
}
void print_graph(int n) { // グラフを表示する
    for (int i = 0; i < n; i++) {
        cout << "Adjacency List of " << arr[i].v << ": ";
        while (arr[i].ptr != NULL) {
            cout << (arr[i].ptr)->des << " ";
            arr[i].ptr = (arr[i].ptr)->next;
        }
        cout << endl;
    }
}
// グラフが非巡回有向グラフ（DAG）かどうかを判定する
int checkCG(int n) {
    int cnt = 0;
    int size = n - 1;
    for (int i = 0; i < n; i++) {
        if (cnt == size) {
            return 0;
        }
        if (arr[i].ptr == NULL) {
            cnt++;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    if ((arr[j].ptr)->des == (arr[i].ptr)->des) {
                        (arr[j].ptr)->des = -1;
                    }
                    arr[i].ptr = (arr[i].ptr)->next;
                }
            }
        }
    }
    cout<<"after checking dag";
    int visited[n + 1];
    for (int i = 0; i < n; i++) {
        while (arr[i].ptr != NULL) {
            cout << (arr[i].ptr)->des << " ";
            visited[i] = 1;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    cout << (arr[j].ptr)->des << " ";
                    if (visited[arr[j].v] == 1) {
                        cout << arr[i].v << " - " << arr[j].v;
                    }
                    arr[j].ptr = (arr[j].ptr)->next;
                }
                cout << endl;
            }
            arr[i].ptr = (arr[i].ptr)->next;
        }
        cout << endl;
    }
    return 1;
}
int main() {
    int n = 5;
    cout << "Number of vertices: " << n << endl;
    for (int i = 0; i < n; i++) {
        arr[i].v = i;
        arr[i].ptr = NULL;
    }
    addEd(1, 2);
    addEd(2, 1);
    addEd(0, 1);
    addEd(2, 3);
    addEd(2, 0);
    addEd(5, 4);
    addEd(4, 2);
    print_graph(n);
    cout << "Feedback arc Set: ";
    if (checkCG(n) == 0)
        cout << " None";
}

コードのポイント

• addEd関数： 指定された始点から終点への有向辺を隣接リストに追加します。
• addRevEdge関数： 逆向きの辺を追加するための補助関数です。
• checkCG関数： 出次数が0の頂点（シンク）を順に処理し、グラフ全体がDAGとして成立しているかを確認します。条件を満たさない場合はフィードバックアークセットとして該当する辺を出力します。

実行結果

Number of vertices: 5
Adjacency List of 0: 1
Adjacency List of 1: 2
Adjacency List of 2: 1 3 0
Adjacency List of 3:
Adjacency List of 4: 2
Feedback arc Set: None

この実行例では、入力されたグラフに対してフィードバックアークセットが存在しない、つまりグラフが既にDAGとして扱える状態であることが判定されています。頂点数や辺の組み合わせを変更することで、閉路を含むグラフにおけるフィードバックアークセットの検出も試すことができます。