1

私はグラフ/ネットワークの問題に取り組んできましたが、最終的に自分が何をしたいのかがわかったと思います。実装に取り​​掛かった今、使用するライブラリを決定する際に問題が発生しています。グラフ自体は非常に単純で、各ノードは文字列でラベル付けされ、それぞれが 2 つのノード (変数) 間の確率/相関係数であり、無向です。グラフで実行したい操作は次のとおりです。

  • 新しいノード/エッジの挿入 (高速)
  • すべてのペアの最短 (1/確率) パスを見つけ、パス内のノードを記憶する - おそらくジョンソンのアルゴリズム
  • k 個の特定の頂点に対する最小重みシュタイナー ツリーの構築
    • ジョンソンのアルゴリズムを使用して最短経路を構築する
    • パス p の現在のノードを繰り返し処理し、k の残りのノードへの最短ルートを見つけます。
  • グラフの平均度を見ると
  • ノード間の中間性の評価
  • クラスタリング係数の取得
  • グラフのモジュール性を見つける

これらの多くについて、帰無仮説としてテストして、結果を Erdos-Renyi モデルと比較したいと思います。また、マルコフ フィールドを介して統計力学の定義を使用できると、同一ではない 2 つのノード間の相関関係を計算し、エントロピーなどについてグラフに質問することができるため、役立ちます。ある種のマルコフ体ライブラリに追加することも役立ちます。

現時点での問題の核心は、動作する C++ ライブラリを見つけようとしていることです。R を調べましたが、より堅牢で高速なものが必要です。私が検討している3つのライブラリは次のとおりです。

  • レモン
    • 使用とインストールが簡単
    • 簡単なドキュメント
    • 欲しい機能がすでにある
    • テキスト ファイルを読み込んでグラフを動的に作成し、ノードの重複がないことを確認することは、私には理解できない悪夢です。
  • ブースト グラフ ライブラリ
    • オブジェクトの難解で難解な定義とその使用方法
    • ドキュメンテーションはコードが行うことと必ずしも一致しません
    • 必要なアルゴリズムの多くと、テキスト ファイルからグラフを作成する非常に簡単な方法があります。
  • マルチスレッド グラフ ライブラリ
    • すでに組み込まれている並列処理
    • BGLより読みやすい
    • それほど多くの機能はありません
    • まだ難解

さらに先には、分散ストレージ (hadoop など) を備えた分散ネットワーク上にグラフが存在することを想像しています。グラフ全体がメモリに収まらないと思われるため、グラフの一部を確認するためのキャッシュ シナリオを考え出す必要があります。

私が説明した問題に対して、人々はどのライブラリを提案しますか? BGL だけを使用して、独自の関数を作成する方がよいでしょうか? マルチスレッド版はどうですか？私がやりたい作業の種類、特に計算したい量にもっと簡単に役立つライブラリはありますか?

元の投稿

ありがとう！

Edit1 だから私はBGLにひどく不満を感じています。私は隣接リスト グラフを持っており、グラフ上で独自のバージョンのジョンソン (またはフロイド、この時点では好き嫌いはありません) を実行し、距離行列を返して確認したいと考えています。私がそれを機能させることができないことを除いて。これまでの私の完全なコード実装は次のとおりです。

using namespace boost;

int main()
{
//Read in the file
std::ifstream datafile("stuff");
if (!datafile)
{
    std::cerr << "No Stuff file" << std::endl;
    return EXIT_FAILURE;
}

//Build the graph
typedef adjacency_list < vecS, vecS, undirectedS, property < vertex_name_t,
    std::string >, property < edge_weight_t, double > > Graph;
Graph g;

//Build the two properties we want, string and double
//Note, you have to nest properties for more
typedef property_map< Graph, vertex_index_t >::type vertex_index_map_t;
vertex_index_map_t vertex_index_map = get(vertex_index, g);
typedef property_map < Graph, vertex_name_t >::type name_map_t;
name_map_t name_map = get(vertex_name, g);
typedef property_map < Graph, edge_weight_t >::type probability_map_t;
probability_map_t probability = get(edge_weight, g);

//Map of of the vertices by string
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::map < std::string, Vertex > NameVertexMap;
NameVertexMap AllNodes;

//Load the file into the graph
for (std::string line; std::getline(datafile, line);)
{
    char_delimiters_separator < char >sep(false, "", ";");
    tokenizer <> line_toks(line, sep);
    tokenizer <>::iterator i = line_toks.begin();
    std::string conditionA = *i++;
    NameVertexMap::iterator pos;
    bool inserted;
    Vertex u, v;

    boost::tie(pos, inserted) = AllNodes.insert(std::make_pair(conditionA, Vertex()));
    if (inserted)
    {
        u = add_vertex(g);
        name_map[u] = conditionA;
        pos->second = u;
    }
    else
    {
        u = pos->second;
    }

    std::string correlation = *i++;
    std::istringstream incorrelation(correlation);
    double correlate;
    incorrelation >> correlate;

    boost::tie(pos, inserted) = AllNodes.insert(std::make_pair(*i, Vertex()));
    if (inserted) {
        v = add_vertex(g);
        name_map[v] = *i;
        pos->second = v;
    }
    else
    {
        v = pos->second;
    }

    graph_traits < Graph >::edge_descriptor e;
    boost::tie(e, inserted) = add_edge(u, v, g);
    if (inserted)
        probability[e] = 1.0/correlate;
}

typedef boost::graph_traits<Graph>::edge_iterator edge_iter;
std::pair<edge_iter, edge_iter> edgePair;
Vertex u, v;
for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first)
{
    u = source(*edgePair.first, g);
    v = target(*edgePair.first, g);
    std::cout << "( " << vertex_index_map[u] << ":" << name_map[u] << ", ";
    std::cout << probability[*edgePair.first] << ", ";
    std::cout << vertex_index_map[v] << ":" << name_map[v] << " )" << std::endl;
}  
}

入力ファイルの形式は NodeA;correlation;NodeB です。上に貼り付けたコードは機能しますが、johnson_all_pairs_shortest_paths 機能を含めようとすると深刻な問題が発生します。本当に私が欲しいのは、DistanceMatrix Dだけではありません(正しく構築できないようです。doubles double D[V][V]、V = num_vertices(g)の正方行列にしたいのですが、それは私に返してくれます関数を正しく呼び出していないこと) だけでなく、そのパスに沿って取得されたノードのリストも表示されます。これは、フロイドのアルゴリズムに関する wiki の記事と同様です。パスの再構築。機能があるかどうかわからないので (関数呼び出しの方法は言うまでもありません)、この問題に対して独自のアルゴリズムをロールしようとする必要がありますか? BGL のドキュメントは実装と同じくらいわかりにくいので、最新の例はまだありません。

4

0 に答える 0