問題タブ [cyclic-graph]

ツリー レイアウトを使用して、JUNG でグラフ (ツリーではない) を視覚化したいと思います。少し奇妙に思えるかもしれませんが、問題は次のとおりです。アプリケーションは、Neo4J データベースに支えられています。それらにはたくさんのノードがあり、すべてがいくつかのタイプの関係を介して接続されています。つまり、巡回グラフがあります。

リレーションシップ タイプ *IS_PARENT* を除くすべてのリレーションシップを想像力で削除すると、完全なツリーが残ります。つまり、私のデータにはツリー構造がありますが、JUNG はそれを循環させる他の関係のために見ることができません。

私がこれをやりたいと思った主な理由は2つあります。

1. 読みやすさ。私のデータには論理構造があり、それを視覚化したいと思っています。
2. これにより、アプリケーションのパフォーマンスが向上すると確信しています。現時点では、頂点とエッジが大量にあるため、パフォーマンスが非常に低下しています。また、Prefuse という別の視覚化ツールを調べたところ、ツリー レイアウトの方がはるかに扱いやすいことがわかりました。少なくとも Prefuse の場合はそうでした。JUNG でも同じことが当てはまることを願っています。

ですから、私にとってはメリットがたくさんあります。何かを見つけることができなかったので、ここの誰かが私を助けてくれることを願っています。

入力は無向循環平面グラフで、各頂点には最大で 8 つのエッジがあります。

2 つの頂点 v_0、v_1 間のすべてのパスを最短から最長の順に列挙する方法は何ですか? 計算複雑度とは

上記が不可能な場合、K 以下の長さのすべてのパスを生成する方法は何ですか?

私は現在、このJacksonプラグインを使用しています

私の循環グラフをシリアル化しました。次に、クライアントでJSOGを使用して {@ref} オブジェクトを次のようにデコードします。

問題は、json をサーバーに送り返そうとしているときに発生します。データに対して何もしないと、「最大コール スタック サイズを超えました」というメッセージが表示されます。これは明らかに、js オブジェクトが周期的であるためです。私は使用してみます：

しかしその後、Jackson はすべての @id と @ref を窒息させます。

これを行う方法を理解している人はいますか？

このSO 投稿に出くわしました。有向グラフで DFS を使用したサイクル検出は、バックトラッキングのために高速であることが示唆されています。ここで私はそのリンクから引用します：

深さ優先検索は、幅優先検索よりも早くバックトラックできるため、メモリ効率が高くなります。コール スタックを使用すると実装も簡単になりますが、これはスタックをオーバーフローしない最長パスに依存します。

また、グラフが方向付けされている場合は、ノードにアクセスしたかどうかだけでなく、どのようにしてそこに到達したかを覚えておく必要があります。そうでなければ、サイクルを見つけたと思うかもしれませんが、実際には 2 つの別個のパス A->B しかありませんが、それはパス B->A があるという意味ではありません。深さ優先検索を使用すると、下降するときにノードを訪問済みとしてマークし、バックトラックするときにそれらのマークを解除できます。

バックトラックが不可欠な理由

与えられた例で何を意味するのか、誰かが例のグラフで説明できますかA->B?

最後に、DFSバックトラッキングを使用しない有向グラフでのサイクル検出のコードがありますが、それでもサイクルで検出されO(E+V)ます。

でサイクルを検出する方法

1. 有向グラフ
2. 無向グラフ。

無向グラフの場合..私が考えたアルゴリズムの1つは、互いに素な集合を使用することです。

• G の各頂点 v
  • メイクセット(v)
• G の各エッジ e(u,v) に対して 1 つずつ取得
  • 検索セット (u) == 検索セット (v) の場合
    • return true // サイクルが存在する
• false を返す