C++でのマップの設計

Question

私はshortest path problemで作業しています。つまり、mapをシミュレートするデータ型またはクラスを作成する必要があります。これを行うには現在map<string, map<string, int>>を使用しています。最初のstringはノードの名前（ノードAと呼ぶ）であり、2番目のパラメータはAがAまでの距離に接続するノードのマップです。

これはうまく動作しますが、私はそれを私のノードに対処するにはやや面倒な方法を見つけると、マップを作成するより実際のアルゴリズムよりも時間がかかります。誰でもthisのようなものを優雅にC++のデータ構造で表現するためのまともな方法を提案できますか？

申し訳ございませんが、ご了承ください。まず、両方の構文が管理可能ですが、誰かがよりエレガントなものを提案できれば大歓迎です。大マップ上の各ペア内の「サブマップ」を繰り返し処理する必要があるため、マップを反復することは非常に不快です。第2に、10ノードのマップを作成する時間を測定し、実際のアルゴリズムを実行するのにかかる時間と比較しました。作成するのに時間がかかりました。

Answer 1

非常に簡単なアプローチの1つがテーブルです。これはかなり自明実装することができ

+---+---+-- 
    | A | B | 
+---+---+---+-- 
| A | 0 |100| 
+---+---+---+-- 
| B |100| 0 | 
+---+---+---+-- 

、あなたは、単にセンチネル値を使用して行うことができ、接続の不在を表現する方法を考案する必要があります。

第2に、ノードを表現する方法はあまり適切ではありません。弦は重量級の獣です。実際の名前から単純な数値へのマッピングを作成し、テーブル内の数字のみを使用することをお勧めします。

は、たとえば、あなたがこのようなアプローチを使用することができます：あなたはすぐにノードをエンコードし、唯一の積分を扱っている場合もちろん

class Graph { 
public: 
    Graph() {} 

    void addEdge(std::string const& left, 
       std::string const& right, 
       unsigned weight) 
    { 
    unsigned const leftIndex = this->getNode(left); 
    unsigned const rightIndex = this->getNode(right); 

    if (_graph.size() <= leftIndex) { 
     _graph.resize(leftIndex + 1, Sentinel); 
    } 

    std::vector<unsigned>& leftEdges = _graph[leftIndex]; 
    if (leftEdges.size() <= rightIndex) { 
     leftEdges.resize(rightIndex + 1, Sentinel); 
    } 

    unsigned& edge = leftEdges[rightIndex]; 
    if (edge != Sentinel) { 
     std::cerr << "There was already a weight for '" 
       << left << "' -> '" << right "'\n"; 
    } else { 
     edge = weight; 
    } 
    } 

    // Returns (weight, true) if the edge exists and (0u, false) otherwise 
    std::pair<unsigned,bool> getWeight(std::string const& left, 
            std::string const& right) const 
    { 
    unsigned const leftIndex = this->getNode(left); 
    unsigned const rightIndex = this->getNode(right); 

    try { 
     unsigned const weight = _graph.at(leftIndex).at(rightIndex); 
     return weight == Sentinel ? std::make_pair(0u, false) : 
            std::make_pair(weight, true); 
    } catch(std::out_of_range const&) { 
     return std::make_pair(0u, false); 
    } 
    } 

private: 
    static unsigned const Sentinel = (unsigned)-1; 

    unsigned getNode(std::string const& node) const { 
    std::map<std::string, unsigned>::const_iterator it = _nodes.find(node); 
    return it == _nodes.end() ? _graph.size() : it->second; 
    } 

    unsigned getNode(std::string const& node) { 
    return _nodes.insert(std::make_pair(node, _nodes.size())); 
    } 

    std::map<std::string, unsigned> _nodes; 
    std::vector< std::vector<unsigned> > _graph; 
}; 

が、それははるかに簡単になります（これは、このすべてを削除しますはstring->クラス内からの符号なし変換）。

はまた、私はグラフが指示されていない場合、選択したなければならない、有向グラフのクラスを作成したことに注意の間：両エッジ表す

• （A - > BとB - > A）
を単一のエッジ、例えば、のみ（A - > B）を表す
• は、あなただけに任意に選択でき、例えば、より高いindiceに