0

C++ でのグラフの簡潔で正確な隣接リスト表現を探しています。私のノードは単なるノード ID です。これが私がやった方法です。専門家がそれについてどう考えているか知りたいだけです。より良い方法はありますか？

これはクラスの実装です (特別なことは何もありません。現在は public/private メソッドは気にしません)

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>

using namespace std;

class adjList {
public:
    int head;
    vector<int> listOfNodes;
    void print();
};

void adjList :: print() {
    for (int i=0; i<listOfNodes.size(); ++i) {
        cout << head << "-->" << listOfNodes.at(i) << endl;
    }
}

class graph {
public:
    vector<adjList> list;
    void print();
};

void graph :: print() {
    for (int i=0; i<list.size(); ++i) {
        list.at(i).print();
        cout << endl;
    }
}

メイン関数は、入力ファイルを 1 行ずつ解析します。各行は次のように解釈されます。

<source_node> <node1_connected_to_source_node> <node2_connected_to_source_node <node3_connected_to_source_node> <...>

主なものは次のとおりです。

int main()
    {
        fstream file("graph.txt", ios::in);
        string line;
        graph g;
        while (getline(file, line)) {
            int source;
            stringstream str(line);
            str >> source;
            int node2;
            adjList l;
            l.head = source;
            while (str >> node2) {
                l.listOfNodes.push_back(node2);
            }
            g.list.push_back(l);
        }
        file.close();
        g.print();
        getchar();
        return 0;
    }

main() から変数を直接変更するのではなく、adjList クラス内に addEdge() 関数を追加する必要があることはわかっていますが、今のところ、最適な構造について疑問に思っています。

編集: 私のアプローチには1つの欠点があります。多数のノードを持つ複雑なグラフの場合、ノードは確かに構造体/クラスになり、その場合、オブジェクト全体を格納して値を複製します。その場合、ポインタを使用する必要があると思います。たとえば、無向グラフの場合、ノード オブジェクトのコピーを adjList に格納します (ノード 1 と 2 の間の接続は、1 の隣接リストが 2 になることを意味し、その逆も同様です)。オブジェクト全体ではなく、adjList にノード オブジェクトのポインターを格納することで、これを回避できます。このアプローチの恩恵を受ける dfs 実装を確認してください。そこでは、各ノードが 1 回だけアクセスされるようにする必要があります。同じノードの複数のコピーがあると、私の人生はより困難になります。番号？

この場合、クラス定義は次のように変更されます。

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>

using namespace std;

class node {
public:
    node() {}
    node(int id, bool _dirty): node_id(id), dirty(_dirty) {}
    int node_id;
    bool dirty;
};

class adjList {
public:
    node *head;
    vector<node*> listOfNodes;
    void print();
    ~adjList() { delete head;}
};

void adjList :: print() {
    for (int i=0; i<listOfNodes.size(); ++i) {
        cout << head->node_id << "-->" << listOfNodes.at(i)->node_id << endl;
    }
}

class graph {
public:
    vector<adjList> list;
    void print();
    void dfs(node *startNode);
};

void graph::dfs(node *startNode) {
    startNode->dirty = true;
    for(int i=0; i<list.size(); ++i) {
        node *stNode = list.at(i).head;
        if (stNode->node_id != startNode->node_id) { continue;}
        for (int j=0; j<list.at(i).listOfNodes.size(); ++j) {
            if (!list.at(i).listOfNodes.at(j)->dirty) {
                dfs(list.at(i).listOfNodes.at(j));
            }
        }
    }
    cout << "Node: "<<startNode->node_id << endl;
}

void graph :: print() {
    for (int i=0; i<list.size(); ++i) {
        list.at(i).print();
        cout << endl;
    }
}

そして、これが main() 関数を実装した方法です。オブジェクトの重複を避けるために map<> を使用しています。以前に定義されていない場合にのみ、新しいオブジェクトを作成します。ID によるオブジェクトの存在の確認。

int main()
{
    fstream file("graph.txt", ios::in);
    string line;
    graph g;
    node *startNode;
    map<int, node*> nodeMap;
    while (getline(file, line)) {
        int source;
        stringstream str(line);
        str >> source;
        int node2;
        node *sourceNode;
        // Create new node only if a node does not already exist
        if (nodeMap.find(source) == nodeMap.end()) {
                sourceNode = new node(source, false);
                nodeMap[source] = sourceNode;
        } else {
                sourceNode = nodeMap[source];
        }
        adjList l;
        l.head = sourceNode;
        nodeMap[source] = sourceNode;
        while (str >> node2) {
            // Create new node only if a node does not already exist
            node *secNode;
            if (nodeMap.find(node2) == nodeMap.end()) {
                secNode = new node(node2, false);
                nodeMap[node2] = secNode;
            } else {
                secNode = nodeMap[node2];
            }
            l.listOfNodes.push_back(secNode);
        }
        g.list.push_back(l);
        startNode = sourceNode;
    }
    file.close();
    g.print();
    g.dfs(startNode);
    getchar();
    return 0;
}

2番目の編集ノードクラスに隣接リストを配置するというUlrich Eckhardtの提案の 後、グラフを保存し、dfs()、dijkstra()のような操作を実行するためのより良いデータ構造であると私が思うものは次のとおりです。隣接リストはノード クラスにマージされることに注意してください。

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>

using namespace std;

class node {
public:
    node() {
    }
    node(int id, bool _dirty): node_id(id), dirty(_dirty) {
        //cout << "In overloaded const\n";
    }
    int node_id;
    bool dirty;
    vector<node*> listOfNodes;
};

class graph {
public:
    vector<node*> myGraph;
    void dfs(node* startNode);
};

void graph::dfs(node* startNode) {
    startNode->dirty = true;
    for (int j=0; j<startNode->listOfNodes.size(); ++j) {
            if (!startNode->listOfNodes.at(j)->dirty) {
                dfs(startNode->listOfNodes.at(j));
            }
        }

    cout << "Node: "<<startNode->node_id << endl;
}

これよりもうまくできるでしょうか？

4

1 に答える 1

1

改善できる点がいくつかありますが、一般的に、あなたのアプローチは合理的です。ノート：

  • intコンテナのサイズが として表現できるサイズを超える可能性があるため、一部のコンパイラから警告が表示されますint。代わりに、を使用してsize_tください。
  • for (int i=0; i<list.size(); ++i)に書き換えますfor(size_t i=0, size=list.size(); i!=size; ++i)。!=の代わりに使用する<と、イテレータで機能します。サイズを一度読み取って保存すると、デバッグが容易になり、おそらくさらに効率的になります。
  • 印刷するループ内には、list.at(i).print();. はlist.at(i)、インデックスが有効であることを確認し、有効でない場合は例外を発生させます。この非常に単純なケースでは、インデックスが有効であると確信しているため、list[i]代わりに使用する方が高速です。また、インデックスが無効であることを期待するのではなく、インデックスが有効であることを暗黙的に文書化します。
  • print()関数は定数でなければなりません。
  • が何なのかわかりませんint head。これはノードのある種の ID ですか? そして、ID は単に中のインデックスではありませんgraph::listか? それがインデックスの場合、要素のアドレスから最初の要素のアドレスを差し引いたものを使用してオンデマンドで計算できるため、重複して保存する必要はありません。また、読み取り時にそのインデックスを検証することを検討してください。これにより、存在しない頂点に向かうエッジがなくなります。
  • ノード レベルでのカプセル化を気にしない場合 (これは合理的です!)、これを構造体にすることもできます。これにより、入力の手間が省けます。
  • インデックスの代わりにポインターを格納するのは難しいですが、速度を向上させることができます。問題は、読み取りのために、まだ存在しない頂点へのポインターが必要になる場合があることです。追加のストレージを使用せずにそれを可能にするハックがあります。最初にポインター値にインデックスを格納し (reinterpret_cast を使用)、読み取り後に、これらの値を実際のアドレスに調整するデータに 2 回目のパスを作成する必要があります。もちろん、2 番目のパスを使用して、まったく存在しない頂点に向かうエッジがないことを検証することもできます (これはat(i)関数が役立つ場所です) 。どうでもいいこと。

明示的な要求に応じて、ポインターにインデックスを格納する方法の例を次に示します。

// read file
for(...) {
    size_t id = read_id_from_file();
    node* node_ptr = reinterpret_cast<node*>(id);
    adjacency_list.push_back(node_ptr);
}

/* Note that at this point, you do have node* that don't contain
valid addresses but just the IDs of the nodes they should finally
point to, so you must not use these pointers! */

// make another pass over all nodes after reading the file
for(size_t i=0, size=adjacency_list.size(); i!=size; ++i) {
    // read ID from adjacency list
    node* node_ptr = adjacency_list[i];
    size_t id = reinterpret_cast<size_t>(node_ptr);
    // convert ID to actual address
    node_ptr = lookup_node_by_id(id);
    if(!node_ptr)
        throw std::runtime_error("unknown node ID in adjacency list");
    // store actual node address in adjacency list
    adjacency_list[i] = node_ptr;
}

これが一般的に機能すると確信していますが、これが機能することが保証されているかどうかは 100% 確信が持てません。ただし、これにより、正確に「頭」とは何かを尋ねている理由も明確になることを願っています. コンテナー内の単なるインデックスである場合は、ファイル内でもメモリ内でもほとんど必要ありません。ファイルから取得したノードの名前または識別子のようなものである場合、それは絶対に必要ですが、インデックスとして使用することはできません。その値は ID を 1 または 1000 で開始することもできます。クラッシュせずにキャッチして処理する必要があります。

于 2013-05-19T07:58:57.170 に答える