1

無向グラフを読み取るテキスト ファイルがあります。形式は次のとおりです。

1 2 3
2 1
3 1

行の最初の要素はすべて頂点に対応し、残りは基本的に頂点の隣接リストです。

だから私の2つの質問は次のとおりです。

  • 1) C++ でこの情報を読む最良の方法は何ですか? 次のコード セグメントを使用すると、結果としてすべての情報を読み取ることができますが、もちろん、それは最終的に達成したいことではありません。適切な方法で異なる行の情報を分離できるようにしたい (この部分は、以下に示すように、実際には 2 番目の質問と密接に関連しています)

    void inputHandle(ifstream& f, int arr[], string fileName)
{

    f.open(fileName);

    if (!f) {
        cout << "Unable to open file";
        exit(1); // terminate with error
    }

    string temp;
    int i = 0, numTemp;

    while(f >> temp){
        numTemp= atoi(temp.c_str());
        arr[i] = numTemp;
        cout<<arr[i];
        i++;
    }

    f.close();
}

  • 2) このグラフを保存するのに最適なデータ構造は何ですか? mincut アルゴリズムを実装するため、反復ごとにグラフを変更します (行の削除/変更)。

助けてくれてありがとう。

4

1 に答える 1

2

グラフをadjacency listまたはmatrixとして保存します。C++ では、これをコーディングする 1 つの方法を次に示します。パフォーマンス/ストレージの要件によっては、これを微調整する必要がある場合があります。

vector< list<int> > graph;

または、隣接行列を使用できます。

vector< vector<bool> > graph;

ファイル形式の読み取りに関してgetline()は、ファイルを1行ずつ読み取り、各行を整数値で解析します（おそらく を使用istringstream）。おそらく次のようになります。

ifstream f;

vector< list<int> > graph;

f.open(fileName);
while(!f.eof() && !f.fail())
{
    char line[1024]; // Reserve enough space for longest line
    f.getline(line, 1024);

    istringstream iss(line, istringstream::in);

    int vertex;
    iss >> vertex;
    if(!f.fail())
    {
        if(vertex > graph.size()) // Max number of vertex is unknown
        {
            graph.resize(vertex); 
        }
        vertex--; // From your 1-base to zero-based
        list<int>& vertex_list = graph[vertex];
        do
        {
            int to_vertex;
            iss >> to_vertex;
            if(!iss.fail())
            {
               vertex_list.push_back(to_vertex - 1);
            }
        } while(!iss.eof() && !iss.fail());
    }
}
于 2012-04-09T21:50:55.737 に答える