1

何百万ものエッジを含む無向エッジ リストがあります。10x10 疎隣接行列の無向辺リストの単純化された例:

0 2
0 9
2 8
6 9

エッジ リストを圧縮されたスパース行 (定義) 形式に変換したい。これは、エッジ リストを読み取り、Value (私の場合は常に "1")、Column_Index、Row_Pointer の 3 つの配列に書き込むことを意味します。

例のエッジ リストを読み取ると、0 番目の行を簡単に再構築できます。2 番目と 9 番目の列に「1」があります。次に、1 行目にゼロ以外のエントリはありません。

問題

2 行目では、エッジが無向であるため、列 0 と 8 に "1" があるはずですが、"2 0" エントリはリストにありません。この情報はすでに「0 2」エントリにエンコードされていると思います。

部分的に構築された圧縮されたスパース行配列を読み取って、「2 0」エントリが存在するかどうかを確認できますが、何百万ものエントリを含む大きなエッジリストの場合、これは機能しません。

質問

これを解決するにはどうすればよいですか? それとも私のアプローチが間違っていますか？

4

2 に答える 2

0

エッジ リストをスキャンし、インデックスを交換して、それぞれ(i, j)について常に true になるようにすることができますi < j。これは O(N) で行います。

並べ替えられたエッジ リストも必要です。これは O(N log N) です。並べ替えられたエッジ リストを取得したら、それを Symmetric-CSR 形式で保存できます。cell を読み取るとき(y,x)に、 if y > xthen と を交換yしxます。row_pointer[y]次にandを読みrow_pointer[y+1]、それらをPaand とし、 と の間でi のPbスキャンを開始します。>= (= または > の場合に応じて見つかったか見つからない)、または if (見つからない)の場合は終了します。CSR[i]PaPbxCSR[i]i == Pb

また、2 番目のエッジ リスト where を生成しj > i、それを並べ替えることもできます。この時点で、両方のエッジを同時にスキャンし、対称性を必要とせずに CSR リストを生成できます。

j0 = j1 = N+1
# i-th row:
    # we are scanning NodesIJ[ij] and NodesJI[ji].
    If NodesIJ[ij][0] == i
        j0 = NodesIJ[ij][1]
    If NodesJI[ji][0] == i
        j1 = NodesIJ[ji][1]
    if (j0 < j1)
        j = j0
        j0 = N+1
        ij++
    else
        if (j1 == N+1)
           # Nothing more on this row, and j0 and j1 are both N+1.
           i++;
           continue
        j = j1
        j1 = N+1
        ji++
    # We may now store (i,j) in CSR
    if (-1 == row_ind[i])
        row_ind[i]     = csr;
    col_ind[csr++] = j

前者のリストは右上の三角形を記述し、後者は左下の三角形を記述しているため、上記のアルゴリズムは、任意の に対して、 および が存在する場合、それは常に存在することを観察して改善できiます。したがって、i になるまで NodesJI をスキャンしてから、 に進むことができます。pqNodesIJ[p] = iNodesJI[q] = iNodesIJ[p][1] > NodesJI[q][1]NodesJI[p][0]NodesJI[q]

また、インデックスが変更されない場合、行が空になり、対応する値が -1 (または N+1、または必要な「無効な」値) になる可能性があることにrow_ind注意して、初期化を常にチェックすることを避けることもできます。csrの前の値csr。

    scsr = csr;
    while NodesIJ[ij][0] == i
        col_ind[csr++] = NodesIJ[ij++][1]
    while NodesJI[ji][0] == i
        col_ind[csr++] = NodesJI[ji++][1]
    row_ind[i++] = (csr == scsr) ? -1 : scsr;

上記は O(N log N) で実行されます。

別の方法は、行列を割り当て、エッジ リストを行列にデコードし、それを解析して CSR にすることです。これは O(N) ですが、必要なメモリが多すぎる可能性があります。リスト サイズが N の場合、最大 N^2 (または (N/a)^2、a は接続の平均数) のセルを持つことができます。何百万ものエッジのリストには、数十ギガバイトのストレージが簡単に必要になる場合があります。

于 2012-10-19T09:12:49.680 に答える