問題タブ [directed-graph]

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

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

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

PHPで有向グラフを描く方法を探しています。（http://upload.wikimedia.org/wikipedia/commons/0/08/Directed_acyclic_graph.pngのように）。GDが画像を出力できるように、グラフの画像を作成してほしい。

私はこれについて多くのことをグーグルで検索しましたが、有向グラフではなく、一般的なグラフ（バーなどを含む）を描画するためのライブラリをたくさん見つけることができます。

PS system（）を介してdot（Linuxプログラム）を使用してみましたが、残念ながらサーバー上でそれを実行する権限がありません。また、私にはPHP拡張機能などをサーバーにインストールする権限がないため、通常のPHPで動作するはずです（理想的にはファイルを含めるだけです）。

前もって感謝します。

有向循環グラフがあります。一部のエッジは固定されており、削除できない場合があります。他のエッジは、サイクルを壊すために削除される場合があります。

このグラフのサイクルを削除する最善の方法は何ですか? トラバーサルは、可能な限り DFS であり、特定のノードから開始する必要があります。

ドット有向グラフ言語を使用して、異なるランクディレクトリでサブグラフを作成することは可能ですか?

次のことを試しましたが、うまくいきませんでした。サブグラフに rankdir="TB" が存在するにもかかわらず、両方のグラフは左から右に表示されます。

同じダイアグラムで上/下および左/右グラフを取得するための他の構文はありますか、それとも不可能ですか?

.NET アプリケーションで最大 4 次元の疎行列が必要です。マトリックスのサイズ (.NET 配列として表される場合) は、400MB を超える可能性があります。

配列は非常にまばらである可能性が高く、インスタンス化して非常に迅速に破棄できるようにする必要があります (ただし、それは不可能ではありません)。したがって、私は.NET 3.5から消費可能なスパース配列ライブラリを求めています（Managed C ++からBGLを使用することは除外されていると思いますか？）。低コストでキャッシュできる密度の高い形式にシリアライズ可能である必要があります。

そのようなものは (まだ) .NET に存在しますか? フォス? 成熟した？

ティア

アンドリュー・マシューズ

1 つの特別なノードを含む有向グラフをモデル化する方法について意見を求めています。

特別なノード:

1. それにつながるエッジを持つことはできません。
2. 削除できません。

現在のデザイン:

テーブル: ノード、エッジ。Edges には 2 つの列があります。from_node_id と to_node_id で、それぞれ Nodes テーブルのレコードを参照します。

特別なノードを Nodes テーブルの最初のレコードとして保存するのではなく、データベース クエリとは別に作成して、そのレコードをまったく保持しないことにしました。Edges テーブルでは、NULL は from_node_id 列で特別な意味を持ち、中心ノードを参照します。

この設計を使用する動機は、センター ノード レコードを削除/変更から保護したり、Edges テーブルの to_node_id 列で参照されたりすることを心配する必要がないことです。これにより、エッジが同じノードとの間を行き来することも自動的に防止されます。from_node_id と to_node_id を複合主キーにできないなど、この設計にはいくつかの欠点があることを認識しています。

私は現在、センターノードを実際のレコードにし、関連するデータベースメソッドでそのノードのチェックを作成することに傾いています。このデザインの最善の方法は何ですか?