問題タブ [graph-layout]

cytoscape.jsでグラフレイアウトを作っています。一部のノードの位置を固定したい。したがって、現在のソリューションでは、サイトスケープの cose レイアウトを使用し、これらのノードの位置を設定しています。それは機能しますが、私のレイアウトにはいくつかのノードが重なっています。固定ノードに関係なく、cos レイアウトはノードを配置すると思います。どうすればこれを修正できるか考えている人はいますか? ありがとう

MSAGL をテストするために簡単なサンプル アプリケーションを作成していますが、グラフが表示された後にエッジを追加すると KeyNotFoundException が発生します。

これは、どういうわけかデータを更新する必要があることに関係していると思います-または、おそらく別のアプローチを使用しますが、方法がわかりません。

サンプル：

例外の詳細:

Boost Kamada-Kawai-spring-layout アルゴリズムを使用してグラフをレイアウトしようとしています。問題は、一部のグラフで頂点が互いに衝突することです。すべてのエッジを重み 1.0 で追加します。

次に、次のようにグラフをレイアウトします。

一部のグラフは正常に機能しますが、他のグラフはこのような出力を生成します

レイアウトは問題ないと思いますが、エッジの長さを増やす必要がありますが、方法がわかりません

数千のノードとエッジのグラフがあり、強制指向の JavaScript レイアウト アルゴリズム (cose と cola) を使用した Cytoscape.js のパフォーマンスが不足していることに気付きました。

他のライブラリやアルゴリズムを探すために時間を費やすべきなのか、それともそれらのアルゴリズムの複雑さが一般的に高すぎるのか疑問に思います。単純なアルゴリズムでは、すべてのノードを他のすべてのノードと比較する必要があるため、二次的な複雑さが必要になると思いますが、接続性の低いデータを巧妙にフィルタリングすることで、適切な近似を想像することができました (数学的に完全な結果は必要ありません) 、ユーザーにとって直感的なものです）。

私の目標は、典型的なユーザー マシンで 10 秒以内にグラフをレイアウトすることです。

私が見つけた出版物（「強制指向の複雑さ」のためのGoogle Scholar）：

• 無向グラフの高速適応レイアウト アルゴリズム (1995 年)は、 O(|V|^3) を推定します。
• The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawingsは、正確に計算するのは難しいと言います (?、私はグラフ理論家ではありません)。
• 大きなグラフの強制指向レイアウトへの多次元アプローチは、 「サブ二次時間と空間で 2 次元、3 次元、およびそれ以上の次元で描画を生成する」ため、その JavaScript 実装を見つけようとします。

サイトスケープを使用して出力を置き換え、インタラクティブにしようとしていますdot(ノードとコンパウンドの移動、コンパウンドの展開/折りたたみなど)。ただし、グラフが最初にロードされると、ユーザーにはデフォルトのレイアウトが表示されます。ただし、何dotを呼び出すかをサポートするレイアウト/構成を見つけるのに苦労していますrank。

私のグラフには、コンポーネントを表す複合ノードがあります。コンポーネントには、他のコンポーネントや状態、遷移、変数が含まれます。各コンポーネントはinputsおよびを指定できますoutputs。ドットでは、 を左 ( )に、 を右 ( )rankdir=LR;に配置することで、システム ( )内に何らかの形式の流れを追加しようとしました。他の要素は存在しないため、自由に配置できます。次に、すべての再帰コンポーネントを含むサブグラフを指定しました。inputsrank=source;outputsrank=sink;rankcluster

さて、これが私がドットで持っているものです。私が最終的に何をしたいのかを説明してくれることを願っています。

まず、私はすでにこの質問を見ましたが、私が理解している限りでは、レイアウトではなく手動で配置するためのものです。

コンパウンド内のノードの配置を完全にサポートするレイアウトが見つかりません。次のオプションを使用して cytoscape.js-cola レイアウトを使用することを検討しました。

ご覧のとおり、ある程度の流れは ありますが、 ほどきれいではありませんdot。

パラメータに関数を追加してみましたalignmentが、わかる限り絶対座標しか指定できません（例：return {'x': 0};）。これにより、基本的に、コンパウンドのすべての入力ではなく、すべての入力を揃えることができます。

これが私の例の CodePen です: https://codepen.io/anon/pen/GEaOQQ Javascript では、

特定のノード セットとエッジの (GraphViz) "ドット" ファイルを生成しています。ノードは、ランク内の x 次元で、rank=same の y 次元で順序付けられます。エッジは、描画する順序で並べ替えられます。残念ながら、「ドット」は x 次元の順序を尊重しません。もしそうなら、平面有向グラフの交差のないレイアウトを実現します。それらが環状であろうと非環状であろうと関係ありません。

私の質問:

1. ノードとエッジの相対的な順序を尊重するように「ドット」に指示するにはどうすればよいですか
2. 相対的な順序を尊重する、つまりレイアウトを受け入れ、物理的なレンダリングを行う「ドット」に代わるものはありますか。

申し訳ありませんが、ドット ファイルをアップロードできませんでした。サンプルドットファイル