Continuation Passing Style (CPS) during graph construction

4
votes

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?

3
haskellgraphcontinuationscontinuation-passing
You should be careful of the limitations of your representation. The principles of Haskell will forbid you from determining the intensional identity of a Mesh; i.e. you want to tie the knot, but you will not be able to determine that, if you go somewhere and back, you actually got back instead of somewhere else in an infinite cyclic structure. In mathematics, graphs are defined over an arbitrary "carrier set" of vertices; I suggest doing the same for pure functional graphs. - luqui

3 Answers

4
votes

What you need is a technique known as tying the knot. It exploits lazy evaluation to get the job done. No CPS is necessary.

Suppose you can identify each node by some unique ID (string, integer or whatever). Suppose also that when you create a node, you already know IDs of all the nodes it points to, whether they are already created or not. Then you can use this technique.

You string a nodes :: Data.Map NodeID Node through your graph creation functions (use a state monad for extra convenience). When you create a node, you add it to the map. When you create an edge that should point to node named x, you use a fromMaybe $ lookup nodes x. It does not matter whether a node named x is already created, or will be created in the future. As long as it is created at some point, you are set. It will only be fetched from the map when you need it.

This is how I used to create a graph from its textual description. Perhaps there are other, better ways.

If, when creating a node, you don't know IDs of all the nodes that your node will point to, you need to modify this technique a bit, e.g. pass around a map from node ID to a list of its neighbours, and build each list incrementally.

You should be careful and avoid evaluating the lazy values before you finish building the graph.

2
votes

It's not using CPS... but I'm working on a planar graph library for Haskell, using a similar scheme to what you've described above. Edges are added by specifying which existing edge comes before or after it.

The actual graph implementation is done, what's left is to get the binary serialisation working and performant (using PLANAR_CODE for starters, maybe Graph6 and Sparse6 as well) and a few other extra things.

Currently you get the dual graph (which seems to be what you've also drawn in) with a separate function, though I am considering having the dual calculated each time you add an edge (assuming a connected graph).

The code can be obtained from darcs get http://code.haskell.org/~ivanm/planar-graph/; a sample usage (which is what I'm developing this library for) is at http://code.haskell.org/~ivanm/dangd/.

Taken from the Haddock documentation as an example of using it:

For example, let g refer to the following graph (where n1, etc. are both the labels and the variable names):

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





                             ====
                            ( n3 )
                             ====

We can add an edge between n1 and n2 (using Anywhere as the EdgePos since there are currently no edges on either node):

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

This will result in the following graph:

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




                             ====
                            ( n3 )
                             ====

If we want to add edges between n2 and n3, we have three options for the location on n2:

  • Use Anywhere: since there is only one other edge, it makes no difference in terms of the embedding where the second edge goes.

  • Put the new edge BeforeEdge e2 (going clockwise around n2).

  • Put the new edge AfterEdge e2 (going clockwise around n2).

Since n2 currently only has one edge, all three EdgePos values will result in the same graph, so we can arbitrarily pick one:

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

However, with more edges care must be taken on which EdgePos value is used. The resulting graph is:

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

The same graph (up to the actual Edge values; so it won't satisfy ==) would have been obtained with:

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

It seems you don't need to store the link to the NextA and NextB edge inside a Edge. As these are something that can be calculated by traversing from the current Edge why not write a function that take a Edge and return its NextA / NextB edge which are as par the diagram based of clockwise direction of Edge's A and B part.