問題タブ [graph]

Stevey Yegge のGet That Job At Googleの記事を読んだ後、次の短い引用が興味深いものであることがわかりました。

誰かがあなたに問題を与えるときはいつでも、グラフを考えてください。それらは、あらゆる種類の関係を表現する最も基本的で柔軟な方法です。そのため、興味深いデザインの問題にグラフが関係しているのは、50 ～ 50 ショット程度です。他のソリューション タイプに移る前に、グラフを使用してそれを解決する方法を思いつかないことを絶対に確認してください。このヒントは重要です！

グラフのデータ構造/アルゴリズムによって最もよく表現および/または解決される問題の例は何ですか?

私が考えることができる 1 つの例: 現在の場所から別の場所への道順を提供するナビゲーション ユニット (ala Garmin、TomTom) は、グラフと高度なパス アルゴリズムを利用します。

他のいくつかは何ですか？

私はグラフ/ネットワーク愛好家であり、これは単なる好奇心のためです:)

StackOverflow コミュニティをグラフ/ネットワークとしてモデル化しようとしています。SO コミュニティの人々がノードであり、質問のいずれかに与えられた回答がこれらのノード間の関係を確立すると仮定します。関係は、有向 (回答からのリンク -> 質問) または無向であると見なすことができます。グラフには重みを付けることができ、ノードの重みは投票数の増減を表すことができます (0 から 1 のスケールで正規化)。

任意の時間のスナップショットで、最終的にどのようなグラフ/ネットワークになるのでしょうか? スケールフリーですか？それは小さな世界ですか？グラフは一定期間にわたって継続的に進化しており、その構造とダイナミクスを理解したい.

この関係データを取得する方法はありますか? SO API または SO の誰かが (サンプル) データで私を助けることができますか?

明確化の編集: スケールフリー ネットワーク: 次数分布が累乗則に漸近的に従うネットワーク スモールワールド: サブネットワーク内のほぼ任意の 2 つのノード間の接続の存在を特徴とするサブネットワークを持ち、ノードのほとんどのペアが で接続されているネットワーク少なくとも 1 つの短いパス。

Perl のGD::Graphモジュールを使用してグラフを描画しています。

グラフはうまく描画できますが、描画された画像では、描画されたグラフ画像の上部にテキストを追加したいと考えています。基本的には、この描画された画像にテキストを追加したいだけです。ただし、それを行うオプションはありません。

これが実行可能かどうか誰かが知っていますか?

これがプログラミングに関連していないことはわかっていますが、悲惨な状況から抜け出すのに役立つフィードバックを期待しています.

私たちは実際には、何年も前にさかのぼる、Web アプリケーションからのさまざまなデータをたくさん持っています。

たとえば、

• Apache ログファイル
• 追跡ソフトウェア (CSV) からの毎日の統計ファイル
• 全国広告ランキングの日別統計（CSV）
• ..そして、おそらく他のソースからも新しいデータを生成できます。

2005 年に開始されたデータ レコードもあれば、2006 年に開始されたデータ レコードもあります。

私が夢に見ているのは^H^H^H^H検索は、すべてのデータを理解するためのアプリケーションであり、それらを読み込んで、個々のデータセットとタイムラインを (グラフで) 比較し、同じ期間内の異なるデータセットを比較します。フィルタリングする (特に Apache ログファイル); もちろん、これはすべてインタラクティブにする必要があります。

BZ2 で圧縮された Apache ログファイルだけですでに合計 21GB になり、毎週増加しています。

awstats、Nihu Web Log Analyzer、または同様のツールなどで実際に成功したことはありません。それらは静的な情報を生成するだけですが、情報をインタラクティブにクエリしたり、フィルターを適用したり、他のデータに重ねたりする必要があります。

また、RapidMiner などのデータ マイニング ツールも試してみましたが、うまくいきませんでした (つまり、頭がいっぱいです)。

念のため言っておきますが、これは商用アプリケーションになる可能性があります。しかし、本当に役立つものを見つけなければなりません。

どういうわけか、存在しないものを探しているか、アプローチが間違っているという印象を受けます。どんなヒントでも大歓迎です。

アップデート：

結局、私はそれが次のことの混合物でした：

• 多くのフィルタリング機能を含む、ログファイルの解析と解析を管理するためのbashおよびPHPスクリプトを作成しました
• Excel に読み込むプレーンな古い CSV ファイルを生成しました。私は幸運にも Excel 2007 を使用できました。固定されたデータ セットを操作しているにもかかわらず、Excel 2007 のグラフィカルな機能は非常に役に立ちました。
• Amazon EC2 を使用してスクリプトを実行し、CSV をメールで送信しました。約 200 GB のデータをクロールする必要があったため、大きなインスタンスの 1 つを使用して解析を並列化しました。データを正しく取得するために多数の解析試行を実行する必要があり、全体の処理時間は 45 分でした。Amazon EC2 がなければ何ができたのかわかりません。それは私が支払ったすべての価値がありました。

Graphvizを使用して格子を描画しています。
ノードは数字のセットです。

ラティスなので、ノードの高さ位置（y）は、ノードによって表されるセット内の要素の数を表すようにします。次に、表現をよりクリーンにするために、x位置をgraphvizで定義する必要があります。

出来ますか？

ドットのドキュメントによると、ノードの位置を定義する属性posが必要です。しかし、さまざまな方法で何度も試しましたが、ノードの位置が定義されているグラフを取得できませんでした。誰かがこれで成功しましたか？

以下は私が使用する古典的なドットファイルです：

1つのノードの高さが定義されているファイルの例を誰かが書くことができれば、私は非常に感謝しています。

有向グラフのノードを並べ替えて、(並べ替え順序に反して) 逆方向に流れる矢印の数が最小限になるようにする必要があります。

アルゴリズムは考えられますが (スワップがなくなるまでノードをスワップし続けるなど)、アルゴリズムの実行速度や最適なソリューションに到達するかどうかはわかりません。

この問題の名前と複雑さは何ですか?

時間の経過とともに収集された数値統計データがたくさんあります。

HTMLページでユーザーに折れ線グラフとして表示する必要があります。クライアントでグラフをレンダリングしたい。グラフがインタラクティブであれば完璧です (ユーザーがスケール、スクロール、グラフの線の可視性の切り替えなどを行えるようにする)。

Flash / Flex (または、おそらく Canvas を使用した JavaScript) 用のまともな無料のグラフ描画ライブラリはありますか?

私は gnuplot のようなものを好みますが、十分に正気であれば何でも扱います。

更新: Flare以外の 何か。

Google Charts APIでx軸ラベルを垂直にする方法を知っている人はいますか?

小さなチャートに多くのラベルを収める必要があります。

ありがとう

入力を取っています、例えば 4 1 3 1 2 2 4

最初の行はノードの数で、その後の行はエッジです。グラフに色を付けようとする必要があります。できない場合は、エラーの原因となっているグラフ内のサイクルをリストする必要があります。

グラフの 1 つに 1,000,000 ノードが含まれていることを除いて、これはこれまでのところ問題ありません。それを使用しようとするたびに、スタック オーバーフロー エラーが発生します。さらに合理化し、Eclipse の最大ヒープ サイズを 1024m に上げたにもかかわらずです。

私はコードを求めているのではなく、エラーが発生し続けるために露骨に間違ったことをしているかどうかを尋ねているだけです。