事前に作成されたグラフ/ノード ネットワーク ライブラリを使用するか、自分で作成するかを決定しようとしています。
ノードやエッジのクラス構造に大幅なカスタマイズが必要になる可能性のあるグラフ検索アルゴリズムをいくつか実装しています。
何をすればよいかわからない理由は、既製のものをカスタマイズする方が、そもそも自分で作るよりも費用や手間がかかる可能性があるかどうかわからないからです。パフォーマンスのトレードオフについても興味がありますが、それほど興味はありません。
ライブラリの 1 つを直接使用した経験があり、成功または失敗の話に基づいてアドバイスを持っている人はいますか? 最悪の事態を聞きたいので、何を選んでも、自分が何に夢中になっているのかがわかります。
これまでの検索で見つかったのは、Boost Graph Library (BGL)とGOBLINの 2 つだけです。これらのいずれかに関する具体的なアドバイス、または他の人への提案も大歓迎です。BGLはかなり難解なようです。苦労する価値はありますか？
私はおそらくBGLについて少しガイダンスを提供することができます。
ライブラリは非常に柔軟です。これの代償は、すべての可能性に対応するために、構文が非常にバロックになる可能性があることです。ただし、簡単なことを簡単に実行できるほど十分な柔軟性があります。
残念ながら、ブーストのドキュメントは完全に傾いており、完全な複雑さの説明のみを提供し、物事がいかに単純であるかについてのヒントはありません。
（「十分に高度な技術は魔法と見分けがつかない」-アーサーC.クラーク。彼が言うべきことは、「十分に文書化されていない高度な技術は魔法と見分けがつかない」ということです。
検討：
typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
std::cout << index[*vp.first] << " ";
}
これは、「クイックツアー」がグラフの頂点のリストを印刷することを提案する方法です。ただし、少し調べてみると、頂点は整数インデックスにすぎず、コードは次のように大幅に簡略化できます。
for (int v = *vertices(g).first; v != *vertices(g).second; ++v)
std::cout << v << " ";
おそらく、この単純化されたコードでは達成できない魔法のようなことがいくつかありますが、毎日、BGLを覆う構文を大幅に整理して、コーディング内容を確認できるようにするのが妥当です。
複雑な構文を削除できない場合があります。（または、おそらく私は根本的な真実に気づいていません）。次に、私は通常、小さなユーティリティ関数を使用して複雑さをカプセル化し、作業中のアルゴリズムから遠ざけます。
たとえば、頂点の子をループする必要があることがよくあります
vector<int> getVertexChildren( int v )
{
vector<int> vc;
typedef std::pair<graph_traits<graph_t>::out_edge_iterator, graph_traits<graph_t>::out_edge_iterator> out_edge_iter_pair_t;
for( out_edge_iter_pair_t ep = out_edges(v,m_tree);
ep.first != ep.second; ++(ep.first))
{
vc.push_back( target( *ep.first, m_tree ) );
}
return vc;
}
#define FOR_ALL_CHILDREN( v ) vector<int> vc=getVertexChildren(v); BOOST_FOR_EACH( int child, vc )
要点は次のとおりです。先に進み、BGLを使用します。簡単なことをするために単純化することができますが、それを使用することを学んだら、あなたがそれを必要とするときはいつでもすべての計り知れない柔軟性が利用可能になります。
「ノードやエッジのクラス構造を大幅にカスタマイズする必要があります。」</p>
BGL の「バンドルされたプロパティ」機能を見たことがありますか?
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html
これは強力であり、少しも難しいものではありません。
エッジと頂点のクラスを定義します
class cMyVertex
{
…
};
class cMyEdge
{
…
};
次に、クラスを使用するグラフ タイプを定義します。
typedef boost::adjacency_list<
boost::listS, boost::vecS, boost::bidirectionalS,
cMyVertex, cMyEdge > graph_t;
これで、クラスが何であれ、頂点とエッジにクラスを使用するこのタイプのグラフを作成できます。
完全に自然な方法でクラスの属性とメソッドにアクセスできます
Graph_t g(10) // create a graph with 10 vertices
g[1].setA1( “alpha” ); // invoke an accessor on node #1
私は最近、ブーストグラフライブラリにダイクストラ最短経路問題の試行を行いました。結果：
非常に高性能
必要なコードはごくわずかです
非常に柔軟で拡張可能
理解またはデバッグが難しい
アドバイス：それを使用しますが、使用する前に、Boost Graph Library：ユーザーガイドおよびリファレンスマニュアルをお読みください。
グラフ トラバーサル アルゴリズムを活用できるのであれば、Boost Graph を使用する価値があると思います。カスタム頂点の作成と使用は非常に簡単です。BGL に含まれている例は、その使用方法を学習するのに役立ちました。
私は Clifford に同意します。GraphViz を使用して開発中にグラフを視覚化しましたが、非常に便利であることがわかりました。
これは実際には簡潔な答えではなく、すでに言われていることに追加するものです。
この問題の解決策は、問題のコンテキストによって異なります。グラフアルゴリズムとソフトウェアがどのように機能するかをよく理解したい場合。自分で書いてください。グラフのアルゴリズムと構造に関する高度な知識を取得したい場合、またはそれらを独自のプログラムに実装したい場合は、標準のグラフライブラリを学習してください。（再利用可能なコードを使用する理由を参照してください）
両方の長所。両方を行います。時間に追われている場合は、これに関する本を入手するか、チュートリアルと例に従ってください。
別の提案：{非常に一般的な問題を説明する}ための{最良、最も信頼性が高く、最も習得しやすい}グラフライブラリとは何かについて、新しい指摘された質問をしますか？これは、ニーズに合った最適なものをランダムに見つけるのではなく、何を学ぶかを選択するのに役立ちます。誰かがすでにこの問題を見たことがあります、アドバイスを求めてください。
再利用可能なコードの使用：
独自のグラフ ライブラリを構築することを決定する前に、igraph ( http://igraph.sourceforge.net/ ) をよく調べます。これは C で書かれており、非常に高速で、幅広い基本および高度なグラフ アルゴリズム (視覚化を含む) を提供します。さらに、高速コーディング用の python ラッパーがあるため、このソリューションはコーディングの速度と実行の速度を兼ね備えていると思います。
自分で巻きました。絶対にそうする必要があると確信していない限り、その例に従うべきではありません。
それでも、グラフ理論が苦手な人にとっては、素晴らしい学習体験です。
EBNF 演算子を使用して有向グラフを結合し、イプシロンの消去と Hopcroft ベースの最小化を行うことで、多くの「楽しみ」がありました。特に最小化では、良い情報を見つけて、それがどのように機能するかを理解しようと必死に電話をかけることができれば、「楽しい」:-(
独自のロールを作成する場合は、高レベルの操作を低レベルの digraph データ構造から分離することをお勧めします。異なるメソッドだけでなく、異なるクラスです。私はそうしませんでした-そして、その悪い決定のために、すぐに大幅にリファクタリングすることになります。
ノードに注釈を付けるグラフもあれば、エッジに注釈を付けるグラフもあれば、両方に注釈を付けるグラフもあります。一部の外部データの単なる外部キーであっても、2 つの注釈が役立つ場合があります。たとえば、有限状態マシンでは、エッジに入力と出力の注釈を付けることができます。出力ではなく入力の決定論に興味がある可能性が高いため、両方を単一の ID の背後に隠すのは面倒です。これは、what-does-this-ID-refer のセカンダリ コンテナーの問題全体に加えて、 -ルックアップへ。
また、ダイグラフ IYSWIM として明示的に設計されていないもの (相互にリンクするデータ構造ノードの束など) を操作したい場合もあります。
IOW、さまざまな有向グラフ表現をプラグインできると便利ですが、多くの操作に同じ高レベルのツールを使用できます。
IMOツリービューの順序とXML要素タグの順序で反復および添字付けなどを行う「ツリーツール」クラスを作成したとき、私はそれを正しく理解しました。基礎となるツリー表現はプラグ可能です (ポリシー ベースのテンプレート)。有向グラフで、私は台無しにしました。
とにかく、Boost やその他のグラフ ライブラリが実際に何を提供しているかはわかりませんが、必要なものが提供されている場合は、それを使用してください。それは多くの頭痛を救うでしょう。
私は BGL をよく使用しますが、BGL で気になるのは、エッジと頂点の接続、最小コスト フロー、一般的な最大ウェイトの完全なマッチングなどの基本的なアルゴリズムの欠如です。
LEMON はそのすべてを提供し、構文も単純です。LEMON で私を悩ませているのは、WINDOWS プラットフォームでのインストールとコンパイルの問題ですが、これらの問題にもかかわらず、おそらく LEMON に切り替えるでしょう。