2

と を使用してグラフを作成し875713 nodesてい5105039 edgesます。セグメンテーション違反を使用vector<bitset<875713>> vec(875713)またはarray<bitset<875713>, 875713>スローします。パス回復を使用して、すべてのペアの最短パスを計算する必要があります。どのような代替データ構造がありますか?

このSO スレッドを見つけましたが、私の質問には答えません。

編集

提案を読んだ後、これを試してみましたが、うまくいくようです。私を助けてくれてありがとう。

vector<vector<uint>> neighboursOf; // An edge between i and j exists if
                                   // neighboursOf[i] contains j
neighboursOf.resize(nodeCount);

while (input.good())
{
    uint fromNodeId = 0;
    uint toNodeId = 0;

    getline(input, line);

    // Skip comments in the input file
    if (line.size() > 0 && line[0] == '#')
        continue;
    else
    {
        // Each line is of the format "<fromNodeId> [TAB] <toNodeId>"
        sscanf(line.c_str(), "%d\t%d", &fromNodeId, &toNodeId);

        // Store the edge
        neighboursOf[fromNodeId].push_back(toNodeId);
    }
}
4

3 に答える 3

3

あなたのグラフはまばらです、つまり|E| << |V|^2、したがって、おそらく疎行列を使用して隣接行列を表すか、同等に、次のように、各ノードに隣接するノードのリストを格納する必要があります(結果はギザギザ配列になります)。

vector<vector<int> > V (number_of_nodes);
// For each cell of V, which is a vector itself, push only the indices of adjacent nodes.
V[0].push_back(2);   // Node number 2 is a neighbor of node number 0
...
V[number_of_nodes-1].push_back(...);

このように、予想されるメモリ要件はO(|E| + |V|)ではなくO(|V|^2)、あなたの場合、膨大な数の MB ではなく約 50 MB になるはずです。

これにより、各ステップでノードの隣接ノードのみを考慮する必要があるため、ダイクストラ (またはその他の最短パス アルゴリズム) も高速になります。

于 2012-07-15T12:29:24.150 に答える
2

ノードごとのエッジのリストを単一の配列に格納できます。ノードごとのエッジ数が可変の場合、リストをヌル エッジで終了できます。これにより、多くの小さなリスト (または同様のデータ構造) のスペース オーバーヘッドが回避されます。結果は次のようになります。

enum {
    MAX_NODES = 875713,
    MAX_EDGES = 5105039,
};

int nodes[MAX_NODES+1];         // contains index into array edges[].
                                // index zero is reserved as null node
                                // to terminate lists.

int edges[MAX_EDGES+MAX_NODES]; // contains null terminated lists of edges.
                                // each edge occupies a single entry in the
                                // array. each list ends with a null node.
                                // there are MAX_EDGES entries and MAX_NODES
                                // lists.

[...]

/* find edges for node */
int node, edge, edge_index;
for (edge_index=nodes[node]; edges[edge_index]; edge_index++) {
    edge = edges[edge_index];
    /* do something with edge... */
}

膨大な数の小さなデータ構造があるため、スペースのオーバーヘッドを最小限に抑えることは非常に重要です。ノードの各リストのオーバーヘッドは 1 つの整数にすぎません。これは、stl ベクトルなどのオーバーヘッドよりもはるかに小さくなります。また、リストはメモリ内に連続的に配置されます。つまり、2 つのリストの間に無駄なスペースがありません。可変サイズのベクトルでは、これは当てはまりません。

任意のノードのエッジはメモリに継続的に格納されるため、任意のノードのすべてのエッジの読み取りは非常に高速です。

このデータ配置の欠点は、配列を初期化してエッジ リストを構築するときに、ノードのすべてのエッジを手元に用意する必要があることです。これは、エッジがノードでソートされている場合は問題ありませんが、エッジがランダムな順序になっている場合はうまく機能しません。

于 2012-07-15T13:51:36.867 に答える
1

Node を以下のように宣言すると:

struct{
int node_id;
vector<int> edges; //all the edges starts from this Node.
} Node;

次に、すべてのノードを次のように表現できます。

array<Node> nodes;
于 2012-07-15T12:38:03.877 に答える