問題タブ [graph]

このアルゴリズムは、グラフ内のノードをトラバースするのに最適です。

これを使用して、グラフ内のターゲットノードを見つけることができます。ワークリストは、ワークリストが処理されるときにアイテムをデキュー（またはポップ）します。ターゲットを見つけたら、どうすればノードへのフルパスを返すことができますか？

更新 ルートへのパスを逆にする方法を理解しようとしています。このメソッドはルートノードで呼び出されます。その後、子には2つの親が存在する可能性があるため、各ノードで親プロパティを呼び出して元に戻すほど簡単ではありません。

このメソッドの目的は、パスを見つけることであり、すべてのノードを反復することではなく、ノードが存在するかどうかを確認することです。

グラフの隣接行列を作成したい。matrix[x][y]範囲をチェックしないため、形式の配列を使用するのは安全ではないことを読んだので、stl のベクトル テンプレート クラスを使用することにしました。マトリックスに格納する必要があるのはブール値だけです。だから私の質問は、使用std::vector<std::vector<bool>* >*するとオーバーヘッドが多すぎる場合、またはマトリックスのより簡単な方法と、それを適切に初期化する方法があるかどうかです。

編集：素早い回答をありがとう。もちろん、ポインターは必要ないことに気付きました。行列のサイズは最初に初期化され、プログラムの最後まで変更されません。これは学校のプロジェクト用なので、技術的にはパフォーマンスはそれほど重要ではありませんが、「いい」コードを書けばよいでしょう。STL を使用しても問題ありません。ブーストのようなものを使用することは、おそらく高く評価されていません。

サイトの更新頻度（たとえば、過去5年間にブログに投稿した頻度）を表すグラフを作成したいと思います。これを行うための明白な方法の1つは、過去60か月の「1か月に投稿されたエントリの数」をプロットすることですが、これは満足のいくものではありません。代わりに移動平均のようなものを使用することを検討する必要がありますか？この種のデータを表示するための優れた視覚化手法は何ですか？

グラフに対して深さ優先検索を実行しながら、ダイヤモンドの依存関係を確認する方法について誰かがいくつかの指針を提供できるかどうか疑問に思っていました...次のグラフがありますA -> B, A -> F, B -> C, B-> E, C -> D, E -> D。

指定されたグラフを表すコンテナーの階層構造を構築しようとしていますが、ダイヤモンドの依存関係に到達したときに何をすべきかわかりません。たとえば、私のグラフでは、CとEは両方とも の子コンテナでありB、 を解決するときにDと を参照する必要がCありEます。ダイヤモンドの依存関係を検出し、結合CしEて 1 つのコンテナーにすることはできますか?

私はテーブルを持っています:

それを棒グラフにしたいと思います。

ネット上に lib がないわけではありませんが、プロトタイプまたはフラッシュ xml ファイルです。

--

私が取り組んでいるソリューションは、Googleチャートのhtmlリンクを生成するjqueryプラグインです...きれいではありませんが、KISS（本当にシンプル）で醜いです。

--

これが私のインスピレーションの 1 つです: http://www.dumpsterdoggy.com/articles/?jquery-horizo​​ntal -bar-graph

boost::graph を使用して情報を保存する方法を理解しようとしています。ただし、各頂点に関連付けたい情報があります。ライブラリのドキュメントをじっと見ると、(a)ドキュメントの書き方が悪いか、(b)思ったほど C++ が得意ではないことがわかります。2つ選んでください。

簡単な使用例を探しています。

私はいくつかのことをいじっていて、 Kevin Baconの数を理解しようとするアイデアを思いつきました。この目的のためにソーシャルネットワークと見なすことができるサイトのデータがあります。Facebook だとしましょう (議論を簡単にするため)。私には人々がいて、彼らの友達のリストを持っているので、彼らの間のつながりがあります。ある人から別の人への距離 (基本的には、ケビン ベーコン数) を計算するにはどうすればよいですか?

私の最善のアイデアは、深さ制限のある双方向検索です（計算の複雑さを制限し、グラフで接続できない人々の問題を回避するため）が、これはかなり力ずくであることに気付きました。

小さなサブグラフ (Facebook のグループに相当するようなもの) を作成し、それらの間の最短距離を (おそらく前もって) 計算してから、THOSE を使用してリンクを見つけようとする方がよいでしょうか? これには事前計算が必要ですが、より少ないノードを検索できる可能性があります (ノードは個人ではなくグループである可能性があり、グラフがはるかに小さくなります)。ただし、これは依然として双方向検索になります。

また、特定の目的地の個人に接続する可能性が最も高い可能性があるため、最初に「人気のある」人々のノードを検索して、個人が接続している人の数を事前に計算することもできます。これは、可能な最短経路に対する速度のトレードオフになることを認識しています。他のケースで使用する予定の幅優先検索の代わりに、深さ優先検索も使用したいと思います。

誰かがこれを行うためのより簡単で高速な方法を考えられますか? 2 人の間の最短の長さを見つけられるようにしたいので、終点が常に同じであるほど簡単ではありません (Kevin Bacon の問題など)。

200人のチェーンを取得できるなどの問題があることは認識していますが、検索する深さに制限があるため、それは解決できます。

私はmuninがどのように機能するかについてあまりよく知らないので、これが明白であるならば、私は謝罪します。

私は現在、いくつかのプロジェクトでmuninを使用していますが、これに2回遭遇し、過去のイベントから生成されたmuninグラフがすべて失われます。これは今日の午後私に起こったばかりです。現在、私は今日の午後以降のすべてのシステムイベントの実績しか持っていません。

これらのグラフは回復可能ですか？これらのグラフを生成するために使用されるデータがどこかに保存されていますか？

回復不能な場合は、何が原因でこれが発生した可能性があるのか​​を知りたいと思います。確かに、これが発生するたびに、私はmunin構成設定をいじっていました。この場合、muninによってログに記録される新しいサーバーを追加していました...これを行うと、muninが他のサーバー上のすべてのデータを失う原因になるのかわかりません。

ありがとう。

ソーシャル ネットワーク グラフ内のノードのいくつかのメトリックを組み合わせて、ノードをランク​​付けするための単一の値にしたいと考えています。

in_degree + betweenness_centrality = informal_power_index

問題は、in_degreeとbetweenness_centralityが異なるスケールで測定されていることです。たとえば、0 ～ 15 対 0 ～ 35000 であり、べき乗分布に従っています (少なくとも正規分布ではないことは間違いありません)。

を決定する際に一方が他方を支配しないように、変数を再スケーリングする良い方法はありinformal_power_indexますか?

3 つの明白なアプローチは次のとおりです。

• 変数の標準化 ( で減算meanおよび除算stddev)。これは、分布を押しつぶしすぎて、ロングテールの値とピーク付近の値の大きな差を隠してしまうようです。
• min(variable)で減算して除算することにより、変数を [0,1] の範囲に再スケーリングしますmax(variable)。これは分布の形状を変更しないため、問題の修正に近づいているように見えますが、実際には問題に対処しないのでしょうか? 特に手段が異なります。
• 各値を で割って平均を等しくしますmean(variable)。これはスケールの違いに対処しませんが、おそらく比較には平均値の方が重要ですか?

他のアイデアはありますか？