4

サブディビジョン サーフェスのライブラリに取り組んでいます。メッシュ トポロジを表すために、一種の分割頂点ラス データ構造を使用しています (左側の図を参照)。

メッシュのデータ構造

グラフとしても見られるメッシュの構築中に、まだ存在しない別のノードを指すノードを作成します (右側の図を参照 - 破線の矢印は将来のリンクを表します)。古典的な解決策は、空のポインターでノードを作成し、別のポインターが作成されたときにそれを更新することです。私はHaskellに取り組んでいるので:)そしてコードの暗い面（不純物）に行きたくないので、データを更新せずにメッシュ（グラフ）を構築できるかどうか疑問に思っています。CPS（Continuation Passing Style）でうまくいくと思いますが、方法がわかりません。

それはただの夢ですか？

アップデート

私の質問を少し明確にさせてください。直接リンク (ポインター) を使用してノードを作成する方法を探しています。直接リンクとは、中間テーブルやマップがないことを意味します。そのような単純なデータ定義:

data Mesh = Edge Vertex Mesh Mesh Vertex | Ground

私が間違っておらず、実行可能である場合、CPS はグラフの効率的な作成 (ノードの更新なし) と効率的な横断 (マップのルックアップなし) を可能にします。一方、グラフは完全に不変になります。つまり、リストの末尾を変更するなど、単一の変更をグラフ全体に伝播する必要があります。

私が間違っている？いいえの場合、どうすればよいですか？

4

3 に答える 3

4

必要なのは、結び目と呼ばれるテクニックです。遅延評価を利用して仕事を完了させます。CPS は必要ありません。

各ノードを一意の ID (文字列、整数など) で識別できるとします。また、ノードを作成するときに、既に作成されているかどうかに関係なく、ノードが指すすべてのノードの ID がわかっているとします。次に、この手法を使用できます。

nodes :: Data.Map NodeID Nodeグラフ作成関数を使用してa をストリングします (さらに便利なように状態モナドを使用します)。ノードを作成したら、それをマップに追加します。という名前のノードを指すエッジを作成するときxは、fromMaybe $ lookup nodes x. x という名前のノードがすでに作成されているか、将来作成されるかは問題ではありません。ある時点で作成されている限り、設定は完了です。必要なときにのみマップから取得されます。

これは、テキストの説明からグラフを作成するために使用した方法です。おそらく他にもっと良い方法があるでしょう。

ノードを作成するときに、ノードが指すすべてのノードの ID がわからない場合は、この手法を少し変更する必要があります。たとえば、ノード ID からその近隣のリストへのマップを渡し、ビルドします各リストは段階的に。

グラフの作成を完了する前に、慎重に遅延値を評価しないようにする必要があります。

于 2011-09-15T10:33:36.027 に答える
2

CPSを使用していません...しかし、私はHaskellの平面グラフライブラリに取り組んでおり、上記で説明したものと同様のスキームを使用しています。エッジは、どの既存のエッジがその前または後に来るかを指定することによって追加されます。

実際のグラフの実装が完了しました。残っているのは、バイナリシリアル化を機能させてパフォーマンスを向上させることです（初心者にはPLANAR_CODEを使用し、おそらくGraph6とSparse6も使用します）。

現在、別の関数で双対グラフ（これも描画したようです）を取得しますが、エッジを追加するたびに双対グラフを計算することを検討しています（接続されたグラフを想定）。

コードは;から取得できます。サンプルの使用法（これは私がこのライブラリを開発しているものです）はにあります。darcs get http://code.haskell.org/~ivanm/planar-graph/http://code.haskell.org/~ivanm/dangd/

使用例としてHaddockのドキュメントから引用：

たとえばg、次のグラフを参照してみましょう（ここで n1、などはラベルと変数名の両方です）。

     ====                    ====
    ( n1 )                  ( n2 )
     ====                    ====





                             ====
                            ( n3 )
                             ====

n1との間にエッジを追加できます（現在、どちらのノードにもエッジがないため、 EdgePosとしてAnywheren2を使用します）。

 ((e1,e2),g') = addEdge n1 Anywhere n2 Anywhere "e1" "e2" g

これにより、次のグラフが作成されます。

                  e2
     ====  <---------------  ====
    ( n1 )                  ( n2 )
     ====  --------------->  ====
                  e1




                             ====
                            ( n3 )
                             ====

n2との間にエッジを追加する場合は、次n3の場所に3つのオプションがありますn2。

  • 使用Anywhere：他のエッジは1つしかないため、2番目のエッジの埋め込みに関しては違いはありません。

  • 新しいエッジを配置しますBeforeEdge e2（時計回りに回りますn2）。

  • 新しいエッジを配置しますAfterEdge e2（時計回りに回りますn2）。

n2現在、エッジは1つしかないため、3つのEdgePos値すべてが同じグラフになり、任意に1つを選択できます。

 ((e3,e4),g'') = addEdge n2 (BeforeEdge e2) n3 Anywhere "e3" "e4" g'

ただし、エッジが多い場合は、どのEdgePos 値を使用するかについて注意する必要があります。結果のグラフは次のとおりです。

                  e2
     ====  <---------------  ====
    ( n1 )                  ( n2 )
     ====  --------------->  ====
                  e1         |  ^
                             |  |
                          e3 |  | e4
                             |  |
                             v  |
                             ====
                            ( n3 )
                             ====

同じグラフ（実際のエッジ値まで。したがって、それは満たされません ==）は次のように取得されます。

 ((e4,e3), g'') = addEdge n3 Anywhere n2 (BeforeEdge e2) "e4" "e3" g'
于 2011-09-15T11:48:21.093 に答える
0

NextA および NextB エッジへのリンクを Edge 内に保存する必要はないようです。これらは現在の Edge からトラバースすることで計算できるものであるため、Edge を受け取り、Edge の A 部分と B 部分の時計回りの方向に基づいた図と同じように、その NextA / NextB エッジを返す関数を作成しないでください。

于 2011-09-15T10:27:40.540 に答える