0

大きなグラフで強いコンポーネントを計算するために、DFS ベースのアルゴリズムを使用します。アルゴリズムは小さなグラフでは問題なく動作しますが、大きなグラフでは問題が発生します。したがって、約 28 K の DFS 関数プログラムの再帰呼び出しの後、ハングします。VS2010 はメッセージ VS is busy, no crashes no errors を表示します。何が起こっているのかを把握するために、いくつかの情報を出力しました (低速のためデバッグで実行できません)。そして、プログラムが位置4でハングし、位置1に到達しないことがわかりました(コードを見てください)。

// Main DFS function
void DFS(vector<Edge>& graph, int source_node, bool *vertex_visited, pair<int, int>& direction){

    cout << "\r" << "Position 1" << std::flush;
    // mark vertex as visited
    vertex_visited[source_node - 1] = false;
    // array for all neighbour edges 
    vector<vector<Edge>::iterator> all_neighbours;

    // doesent matter 
    if (direction.second){
        size_of_scc++;
    }

    // binary search of edges incident with source vertex
    pair<vector<Edge>::iterator, bool> itera = find_if_binary_for_edges(graph.begin(), graph.end(), source_node);
    cout << "\r" << "Position 2" << std::flush;

    // push all incident edges to all_neighbours vector
    if (itera.second){
        pair<vector<Edge>::iterator, vector<Edge>::iterator> bounds = find_all_in_range(itera.first, graph);
        vector<Edge>::iterator it = bounds.first;
        while (it != bounds.second){
            all_neighbours.push_back(it++);
        }
    }

    cout << "\r" << "Position 3" << std::flush;

    // if this vertex wasn't visited in the past cal DFS from neighbour vertex
    for (vector<vector<Edge>::iterator>::iterator it = all_neighbours.begin(); it != all_neighbours.end(); ++it){
        if (vertex_visited[(**it)[1] - 1]){
            cout << "\r" << "Position 4" << std::flush;
            DFS(graph, (**it)[1], vertex_visited, direction);
        };
    }

    // need this stuff for SCC computation
    cout << "\r" << "Position 5" << std::flush;
    if (direction.first)
        finishing_times[finishing_times_counter++] = source_node;
}

次に何をすればよいかわかりません。次にどのデバッグ手順を実行する必要がありますか? 位置 4 の後、プログラムは DFS を再度呼び出してから「位置 1」を出力する必要がありますが、それは起こりません。それが何であるかのために？グラフには、約 857K の頂点と 5 * 10^6 のエッジがあります。ありがとう。

4

1 に答える 1

0

それはstackoverflowエラーでした。最初は取得できませんでしたが、DFSリストからいくつかの引数を削除した後、stackoverflowerrorが発生しました。

于 2013-02-19T09:48:33.123 に答える