問題タブ [directed-graph]

Clojure で有向グラフを表現する必要があります。:edgesグラフ内の各ノードを、現在のノードから直接到達可能なノードのコレクションであるというフィールドを含むオブジェクト (おそらくレコード) として表現したいと思います。言うまでもありませんが、これらのグラフが不変であることを望みます。

トポロジカルソートを行い、各グラフを「葉から」構築する限り、このアプローチで有向非巡回グラフを構築できます。

ただし、このアプローチは循環グラフでは機能しません。私が考えることができる 1 つの回避策は、グラフ全体のすべてのエッジの個別のコレクション (おそらくマップまたはベクトル) を持つことです。各ノードの:edgesフィールドには、グラフのエッジのコレクションへのキー (またはインデックス) があります。キー (またはインデックス) が参照する (参照される) ものが存在する前にキー (またはインデックス) を作成できるため、この余分なレベルの間接化を追加することは機能しますが、面倒な作業のように感じます。隣接するノードにアクセスするたびに追加のルックアップを実行する必要があるだけでなく、グローバル エッジ コレクションも渡さなければならず、これは非常に扱いにくいと感じます。

一部の Lisp には、ミューテーション関数に頼らずに循環リストを作成する方法があると聞いたことがあります。Clojure で不変の循環データ構造を作成する方法はありますか?

何百万もの頂点とエッジを持つ有向グラフがあります。頂点のセットが与えられています。それらが「START_POINTS」と呼ばれていると仮定しましょう。「END_POINTS」と呼ばれる別の頂点のセットも示されています。問題は、どのSTART_POINTSからどのEND_POINTSに到達できるかを見つけることです。

次に例を示します。

アルゴリズムは次のことを伝えることができるはずです。

一部のEND_POINTSは、どのSTART_POINTからも到達できない可能性があります。

さて、問題は次のとおりです。それを実装するための最も効率的な方法は何ですか？

各START_POINTから1つずつ開始し、深さ優先探索を使用して到達可能なEND_POINTSを見つけてみました（またはBFS、実行時間を大幅に変更します）。ただし、START_POINTSが非常に多い（END_POINTSも多い）ため、時間がかかります。

START_POINTSのトレースされたパス間には大きな重複があるため、検索を最適化できます。どのパスがどのEND_POINTSに到達できるかを覚えておく必要があります。これを達成するための最も効率的な方法は何ですか？これはよく知られている問題かもしれませんが、私はまだ解決策を見つけることができませんでした。

1月6日に編集：

highBandWidthのアイデアを実装しようとしました（Keith Randallが提案した方法と同様の方法で）：各ノードについて、このノードがSTARTポイントまたはENDポイントでない場合は、すべての入力を出力に接続してから、ノードを削除します。

これは非常に速く始まり、すぐに非常に遅くなります。これは主に、残りのノードの入出力カウントが非常に大きくなり、forループがネストされてパフォーマンスが低下するためです。それをより効率的にする方法はありますか？

可変数の要素を持つリストがいくつかあります。各リストはソートされていますが、ソートのアルゴリズムは不明です。リストを、すべてのリストを同じ順序で、重複することなく含む 1 つの大きなリストにマージしたいと思います。

入力例:

1. XS、M、L、XL
2. S、M、XXL
3. XXS、XS、S、L

期待される結果：

• XXS、XS、S、M、L、XL、XXL

期待される結果は、次のように、各入力シーケンスの要素を正しい順序で含むマージ結果を取得するために、入力シーケンスを照合することによって取得されます。

あいまいな位置を持つ要素がある場合、関数は通知する必要があります。ここでは、XXL (M、L、または XL の後に残る可能性があります) になり、XL の後にその位置を手動で指定する必要があります (ここでは、並べ替えアルゴリズムを知っていて、役立つ可能性があるため)。元のリストのように、各ペアを順番に 2 つの要素ごとにペアを定義することを考えました。これから、完全なリストを作成できます。

これは私の問題です。学校のプロジェクトで、有向グラフを作成し、それを典型的な html Web サイトに適合させようとしています。Java アプレットはオプションではないため、javascript で記述する必要があることがわかりました。したがって、これは次のようになります。

グラフに視覚化されたデータは、いくつかの xml ファイルから収集されます。フレアと他のいくつかのパッケージを調べましたが、実際には、グラフ内のノード (矢印の太さは重要度を表します) 間に双方向のリンクを作成しています。全体を動かせるようにすることも必要です。何か案は？ありがとうございました。

無向グラフしか作れません。監督されたものを作る方法がわかりません。

何か案が？

事前のお詫びは、私が用語を誤用していることです、そして訂正はありがたいです。私は有向グラフに魅了されていますが、数学/計算機科学のバックグラウンドでそれらが実際に何であるかを知ることはできません。便利な図を作成できるので、技術が好きです。

動的有向グラフをブラウザにレンダリングするWebアプリケーション機能を作成しようとしています。最近、使用したいcavasベースのxdotレンダラーであるCanvizを発見しました。

Canvizは素晴らしいですが、xdotファイルをレンダリングします。ファイルには、複雑なポジショニングロジックがすべて含まれているように見えます。

アプリケーションで生成しているファイルはdotファイルであり、このポジショニングロジックは含まれていません

私dotのファイルxdotをCanvizで使用できるファイルに変換できるPHPライブラリを探しています。コマンドラインプログラムdotでこれを実行できることはわかっていますが、これは再配布可能なPHP Webアプリケーション用であり、依存関係としてのバイナリは避けたいと思います。

私の主な問題：dot単純な有向関係に基づいてファイルを生成していて、ブラウザーでエンドユーザーに視覚的なグラフを表示したい。サーバー上の特定のバイナリプログラムの存在に依存することなく、これを実行したいと思います。これに対する最善の解決策は、Canviz+PHPでxdotファイルを生成することだと思います。これができるPHPライブラリを探しています。しかし、私は他の解決策を受け入れる以上のことをしています。

タイトルが示すように..接続されたグラフをJavaに保存する最も効率的な方法は何ですか?

たとえば、さまざまな方法で相互に接続している複数の場所があり、接続されているかどうかを確認するためにグラフをトラバースする必要があるとしましょう..ヘルプ/コメントは役に立ちます!

ノードの削除が可能な限り高速になるように、有向グラフ (必ずしも非循環的である必要はありません) を保存する必要があります。ノードが削除されたときにどのエッジに移動する必要があるかを正確に知るために、追加のデータを保存してもかまいません。

エッジのリストを (ノード インデックスのペアとして) 格納する場合、いくつかのノード n を強制終了するときに、ソースまたはターゲットが n であるエッジのリスト全体を検索する必要があります。これは私のアプリケーションにはコストがかかりすぎます。ノードに追加のデータを保存することで、この検索を回避できますか?

1 つのアイデアは、各ノードに独自のソースとターゲットを 2 つの別個のリストとして保存させることです。ノード n が強制終了されると、そのリストも強制終了されます。しかし、ノード n にリンクされたすべてのターゲット/ソースは、どのようにして自身のリストを更新するか (つまり、機能していないノードをリストから削除するか) を知るのでしょうか? これには、コストのかかる検索が必要になります...

回避できますか？

どうも。

DBIx::Class サブクラス foo への直接的および間接的な外部キー依存関係を持つテーブルのリストを取得する最も速い方法はどれですか? DBIx::Class::Schema に基づく MySQL データベースがあります。DBIx::Class を直接使用できますか、または SQL::Translator は有向グラフを生成することによって役立ちますか?

次のクラスがあるとします。

入力 Foo の場合、出力は [ Bar, Baz ] になります。

次のような有向グラフでエッジを保持するテーブルがあるとします。

特定のノードの個別の無向リンクの数を取得するための最も良い方法は何ですか？重複する有向エッジはなく、ノード自体に直接リンクされていません。重複する無向エッジ（となど）を2回カウントすることは避けたいだけ(1,2)です(2,1)。

これは機能しますが、私にはNOT IN悪臭がします：

これにはPostgreSQL固有のソリューションで十分です。