4

I am working on a library for subdivision surfaces. In order to represent the mesh topology I'm using a kind of split-vertex lath data structure (see the diagram on the left side).

Mesh data structure

During the construction of a mesh, that also can be seen as a graph, it create nodes that should point to another ones that don't exist yet (see diagram on the right side - dashed arrow represent future links). The classical solution is to create a node with an empty pointer and then update it when the other one is created. Since I'm working on Haskell :) and I don't want to go to the dark side of the code (impurity) I'm wondering if it is possible to construct a mesh (graph) without update the data. I guess that CPS (Continuation Passing Style) could do the job but I can't figure out a way.

Is it just a dream?

UPDATE

Let me clarify my question a little bit. I am looking for a method to create nodes with direct links (pointers) and by direct link I mean no intermediate tables or maps. Just a plain data definition like that:

data Mesh = Edge Vertex Mesh Mesh Vertex | Ground

If I'm not wrong and if it is doable, CPS would allow an efficient creation (without node updates) and efficient transverse (without lookups on maps) of a graph. On the other hand the graph would become totally immutable i.e. a single change needs to be propagated through the whole graph e.g. changing the tail of a list.

Am I wrong? If no, how to do it?

4

3 回答 3

4

你需要的是一种称为打结的技术。它利用惰性评估来完成工作。不需要 CPS。

假设您可以通过某个唯一 ID（字符串、整数或其他）来识别每个节点。还假设当您创建一个节点时，您已经知道它指向的所有节点的 ID，无论它们是否已经创建。然后你可以使用这种技术。

您通过图形创建函数将 a 字符串nodes :: Data.Map NodeID Node化（使用 state monad 以获得额外的便利）。创建节点时，将其添加到地图中。当您创建应该指向节点的边时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 )
                             ====

我们可以在n1and之间添加一条边n2（使用Anywhere作为 EdgePos，因为当前任一节点上都没有边）：

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

这将产生以下图表：

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




                             ====
                            ( n3 )
                             ====

如果我们想在 和 之间添加边n2，n3我们有 3 个位置选项n2：

  • 使用Anywhere：由于只有一条其他边，因此在第二条边所在的嵌入方面没有区别。

  • 放置新的边缘BeforeEdge e2（顺时针旋转n2）。

  • 放置新的边缘AfterEdge e2（顺时针旋转n2）。

由于n2目前只有一条边，所有三个EdgePos值都会产生同一张图，所以我们可以任意选择一个：

 ((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 内。由于这些是可以通过从当前边缘遍历来计算的，为什么不编写一个函数来获取边缘并返回其 NextA / NextB 边缘，这些边缘与基于 Edge 的 A 和 B 部分的顺时针方向的图表一样。

于 2011-09-15T10:27:40.540 回答