19

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

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

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

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

4

3 に答える 3

7

各ノードをrefでラップして、ポイントするための安定したハンドルを与えることができます（そして、nilとして開始できる参照を変更できるようにします）。そうすれば、巡回グラフを作成することができます。もちろん、これには「余分な」間接参照があります。

しかし、これはあまり良い考えではないと思います。2番目のアイデアは、より一般的な実装です。RDFグラフを保持するためにこのようなものを構築しました。コアデータ構造とその上にあるレイヤーインデックスから、あまり労力をかけずに構築することができます。

于 2011-01-03T02:30:28.723 に答える
6

私はここ数日これで遊んでいます。

最初に、各ノードにエッジへの参照のセットを保持させ、各エッジにノードへの参照のセットを保持させてみました。ある種の操作では、それらを互いに等しく設定します(dosync... (ref-set...))。1つのノードを変更するには大量の更新が必要であり、グラフの印刷には少し注意が必要だったため、これは気に入らなかった。私はオーバーライドする必要がありましたprint-methodreplがオーバーフローをスタックしないようにマルチメソッド。また、既存のノードにエッジを追加したいときはいつでも、最初にグラフから実際のノードを抽出してから、あらゆる種類のエッジの更新を実行し、全員が最新バージョンを保持していることを確認する必要がありました。他のものの。また、物事が参照されていたため、何かが他の何かに接続されているかどうかを判断することは、線形時間の操作であり、エレガントではないように見えました。この方法で有用なアルゴリズムを実際に実行するのは難しいと判断するまで、私はそれほど遠くまでは行きませんでした。

次に、他の場所で参照されているマトリックスのバリエーションである別のアプローチを試しました。グラフはclojureマップであり、キーはノード（ノードへの参照ではない）であり、値はキーが隣接ノードであり、各キーの単一の値がそのノードへのエッジである別のマップであり、次のいずれかで表されます。エッジの強度を示す数値、または他の場所で定義したエッジ構造。

このように見えます1->2, 1->3, 2->5, 5->2

(def graph {node-1 {node-2 edge12, node-3 edge13},
            node-2 {node-5 edge25},
            node-3 nil ;;no edge leaves from node 3
            node-5 {node-2 edge52}) ;; nodes 2 and 5 have an undirected edge

ノード1のネイバーにアクセスするには、(keys (graph node-1))他の場所で定義されている関数にアクセスするか呼び出します。または、からエッジを取得する(neighbors graph node-1)と言うこともできます。((graph node-1) node-2)1->2

いくつかの利点：

  1. グラフ内のノードと隣接ノードの一定時間のルックアップ、または存在しない場合はnilを返します。
  2. シンプルで柔軟なエッジ定義。マップ内のノードエントリにネイバーを追加すると、有向エッジが暗黙的に存在し、その値（または詳細情報の構造）が明示的に提供されるか、nilになります。
  3. 何かをするために既存のノードを検索する必要はありません。不変なので、グラフに追加する前に一度定義すれば、状況が変わったときに最新バージョンを取得するために追跡する必要はありません。グラフの接続が変更された場合は、ノード/エッジ自体ではなく、グラフの構造を変更します。
  4. これは、マトリックス表現の最良の機能（グラフトポロジは、ノードとエッジでエンコードされていないグラフマップ自体にあり、一定時間のルックアップ、および非変化ノードとエッジ）と隣接リスト（各ノードは「隣接ノードのリスト。正規のスパース行列のような「空白」がないため、スペース効率が良い）。
  5. ノード間に複数のエッジを設定できます。すでに正確に存在するエッジを誤って定義した場合は、マップ構造が重複していないことを確認します。
  6. ノードとエッジのIDはclojureによって保持されます。インデックススキームや共通の参照ポイントを考え出す必要はありません。マップのキーと値はそれらが表すものであり、他の場所でのルックアップや参照ではありません。ノード構造はすべてnilにすることができ、一意である限り、グラフで表すことができます。

私が目にする唯一の大きな欠点は、特定の操作（追加、削除、アルゴリズム）について、開始ノードを渡すことができないことです。グラフマップ全体と開始ノードを渡す必要があります。これは、全体を単純にするために支払うのにおそらく公正な価格です。もう1つの小さな欠点（またはそうでない場合もあります）は、無向エッジの場合、各方向のエッジを定義する必要があることです。エッジの値が方向ごとに異なる場合があり、このスキームではそれが可能になるため、これは実際には問題ありません。

ここで私が見る他の唯一のことは、エッジがマップ内のキーと値のペアの存在に暗黙的に存在するため、ハイパーエッジ（つまり、3つ以上のノードを接続するもの）を定義できないことです。私が遭遇したほとんどのグラフアルゴリズム（すべて？）は2つのノードを接続するエッジのみを処理するため、これは必ずしも大したことではないと思います。

于 2012-04-20T08:27:23.803 に答える
3

私は以前にこの課題に遭遇し、現在 Clojure で真に不変のデータ構造を使用することは不可能であると結論付けました。

ただし、次のオプションの 1 つまたは複数が受け入れられる場合があります。

  • ":unsynchronized-mutable" で deftype を使用して、構築中に一度だけ変更する可変の :edges フィールドを各ノードに作成します。それ以降は、追加の間接オーバーヘッドなしで読み取り専用として扱うことができます。このアプローチはおそらく最高のパフォーマンスを発揮しますが、ちょっとハックです。
  • アトムを使用して :edges を実装します。少し余分な間接性がありますが、私は個人的にアトムの読み取りが非常に効率的であることを発見しました。
于 2011-01-03T18:07:19.917 に答える